AVL树的JAVA实现及AVL树的旋转算法

1，AVL树又称平衡二叉树，它首先是一颗二叉查找树，但在二叉查找树中，某个结点的左右子树高度之差的绝对值可能会超过1，称之为不平衡。而在平衡二叉树中，任何结点的左右子树高度之差的绝对值会小于等于 1。

2，为什么需要AVL树呢？在二叉查找树中最坏情况下查找某个元素的时间复杂度为O(n)，而AVL树能保证查找操作的时间复杂度总为O(logn)。

对于一棵BST树而言，不仅有查找操作，也有插入、删除等改变树的形态的操作。随着不断地插入、删除，BST树有可能会退化成链表的形式，使得查找的时间复杂度变成O(N)，这种情形下，BST树的结构非常不平衡了。为了保持树的平衡，需要对树的形态做一些限制，因此，引入了AVL树，以保证树的左右子树高度之差的绝对值小于等于1。

3，AVL树的JAVA代码实现：

AVLTree 继承 BinarySearchTree 并改写添加节点的add方法，在add方法中判断插入元素后是否导致树不平衡，当不平衡时需要通过旋转进行调整。何时进行旋转调整是通过左右子树的高度之差进行判断的。这里通过rebalance方法使得某结点保持平衡：整个程序的完成代码参考最后。

private BinaryNodeInterface<T> rebalance(BinaryNodeInterface<T> nodeN){
        int heightDifference = getHeightDifference(nodeN);
        if(heightDifference > 1){//左子树比右子树高
            if(getHeightDifference(nodeN.getLeftChild()) > 0)
                nodeN = rotateRight(nodeN);//插入在左子树的左孩子中
            else
                nodeN = rotateLeftRight(nodeN);
        }
        else if(heightDifference < -1){//右子树比左子树高
            if(getHeightDifference(nodeN.getRightChild()) < 0)
                nodeN = rotateLeft(nodeN);//插入在右子树的右孩子中
            else
                nodeN = rotateRightLeft(nodeN);
        }
        return nodeN;
    }

4，AVL树的平衡保证算法

当向AVL树中插入或者删除元素时，可能打破树的平衡。这时，需要通过旋转来调整使之重新变成一颗AVL树。（这里讨论插入元素时的调整）

设 N 表示最接近新叶子的不平衡结点，由于插入元素之前树是平衡的，则插入之后不会有比 N 更高的不平衡结点。（树根的高度为 1 ）

一共有 4 种原因导致结点 N 不平衡：

①在结点 N 的左孩子的左子树中发生了插入操作

进行右旋转调整：即对结点 N 进行右旋转，算法如下：

算法 rotateRight(nodeN)
nodeL = nodeN 的左孩子
将nodeN 的左孩子置为 nodeL 的右孩子
将 nodeL 的右孩子置为 nodeN
return nodeL

②在结点N 的右孩子的右子树中发生了插入操作

进行左旋转调整：即对结点N进行左旋转，算法如下：

算法 rotateLeft(nodeN)
nodeR = nodeN 的右孩子
将 nodeN 的右孩子置为 nodeR 的左孩子
将 nodeR 的左孩子置为 nodeN
return nodeR

③在结点N 的右孩子的左子树中发生了插入操作

进行右-左旋转，即先对结点N 的孙子(孩子的孩子，"位于新插入元素的那个方向")进行右旋转；再对结点N 的新孩子进行左旋转，算法如下：

算法 rotateRightLeft(nodeN)
nodeR = nodeN 的右孩子
将 nodeN 的右孩子置为由 rotateRight(nodeN 的孩子的孩子)返回的结点
return rotateLeft(nodeN 的新的右孩子)

④在结点N 的左孩子的右子树中发生了插入操作

进行左-右旋转，即先对结点N的孙子进行左旋转，再对结点N的新孩子进行右旋转，算法如下：

算法 rotateLeftRight(nodeN)
nodeL = nodeN 的左孩子
将 nodeN 的左孩子置为由 rotateLeft(nodeN 孩子的孩子）返回的结点
return rotateLeft(nodeN 新的左孩子)

5，关于树的平衡性的进一步讨论

除了AVL树之外，还有2-3树、2-4树、红黑树等一系列带有平衡性质的树。其中2-3树和2-4树是完全平衡的，即所有的叶子位于同一层。2-3树的结点至多有两个数据元素，2-4树的结点至多有三个数据元素，这样使得在相同的结点数目下，一般，AVL树比2-3树要高，2-3树比2-4树要高，但是在查找过程中内部结点的比较次数2-4树比2-3要多，2-3树比AVL树要多。因此，总体上看，AVL树、2-3树、2-4树、红黑树的查找都是O(logn)操作。维护平衡性由难到易的排列： AVL树 > 2-3树 > 2-4树 ·= 红黑树。其次，随着对于结点含有3个以上的数据元素的查找树的性能反而会降低，因此这也是为什么没有2-5树……的原因。。。

2018.12更新

6，红黑树与AVL树的对比

不管是红黑树还是AVL树，不仅要有效地支持查找，还需要有效地支持插入和删除，插入和删除操作会改变树的形态，如果不做一定的调整，树的结构就会变得不平衡，因此不管是AVL树还是红黑树都有“旋转”操作。
但是，二者的“旋转”操作的代价是不一样的。在最坏的情况下，AVL树的旋转操作代价能达到O(logN)，而红黑树的旋转操作代价为O(1)。
由于插入、删除操作会引发树的旋转，因此：红黑树比AVL树更适合于插入、删除元素更频繁的情形，而AVL树更适合于查询非常多，插入、删除很少的场景。
另外，红黑树在JDK集合框架中应用广泛，比如HashMap就引入了红黑树，可以让HashMap在存在大量的键冲突的情况下，仍然能够保证快速地查询。
在正常情况下，HashMap的get操作时间复杂度为O(1)，在存在大量冲突时，get操作时间复杂度退化为O(logN)

AVL树的完整JAVA代码实现：

  1 package searchtree;
  2 
  3 import tree.BinaryNode;
  4 import tree.BinaryNodeInterface;
  5 
  6 public class AVLTree<T extends Comparable<? super T>> extends BinarySearchTree<T> implements SearchTreeInterface<T>,java.io.Serializable {
  7     public AVLTree(){
  8         super();
  9     }
 10     
 11     public AVLTree(T rootEntry){
 12         super(rootEntry);
 13     }
 14 
 15     /*
 16      *@Task : 在AVL树中添加元素
 17      */
 18     public T add(T newEntry){
 19         T result = null;
 20         if(isEmpty())
 21             setRootNode(new BinaryNode<T>(newEntry));
 22         else
 23         {
 24             BinaryNodeInterface<T> rootNode = getRootNode();
 25             result = addEntry(rootNode, newEntry);
 26             setRootNode(rebalance(rootNode));
 27         }
 28         return result;
 29     }
 30     
 31     private T addEntry(BinaryNodeInterface<T> rootNode, T newEntry){
 32         assert rootNode != null;
 33         T result = null;
 34         int comparison = newEntry.compareTo(rootNode.getData());//待添加元素与树中已有元素比较以确定添加的位置
 35         if(comparison == 0){//待添加元素已存在于树中
 36             result = rootNode.getData();
 37             rootNode.setData(newEntry);//将新元素替换旧元素
 38         }
 39         else if(comparison < 0){//添加到左子树中
 40             if(rootNode.hasLeftChild()){//继承递归比较
 41                 BinaryNodeInterface<T> leftChild = rootNode.getLeftChild();
 42                 result = addEntry(leftChild, newEntry);
 43                 rootNode.setLeftChild(rebalance(leftChild));
 44             }
 45             else
 46                 rootNode.setLeftChild(new BinaryNode<T>(newEntry));
 47         }
 48         else//添加到右子树中
 49         {
 50             assert comparison > 0;
 51             if(rootNode.hasRightChild()){
 52                 BinaryNodeInterface<T> rightChild = rootNode.getRightChild();
 53                 result = addEntry(rightChild, newEntry);
 54                 rootNode.setRightChild(rebalance(rightChild));
 55             }
 56             else
 57                 rootNode.setRightChild(new BinaryNode<T>(newEntry));
 58         }
 59         return result;
 60     }
 61     
 62     public T remove(T newEntry){
 63         return null;//暂未实现删除操作
 64     }
 65     
 66     /*
 67      * @Task: 在 nodeN 结点上进行右旋操作
 68      */
 69     private BinaryNodeInterface<T> rotateRight(BinaryNodeInterface<T> nodeN){
 70         BinaryNodeInterface<T> nodeL = nodeN.getLeftChild();
 71         nodeN.setLeftChild(nodeL.getRightChild());
 72         nodeL.setRightChild(nodeN);
 73         return nodeL;
 74     }
 75     
 76     private BinaryNodeInterface<T> rotateLeft(BinaryNodeInterface<T> nodeN){
 77         BinaryNodeInterface<T> nodeR = nodeN.getRightChild();
 78         nodeN.setRightChild(nodeR.getLeftChild());
 79         nodeR.setLeftChild(nodeN);
 80         return nodeR;
 81     }
 82     
 83     private BinaryNodeInterface<T> rotateRightLeft(BinaryNodeInterface<T> nodeN){
 84         BinaryNodeInterface<T> nodeR = nodeN.getRightChild();
 85         nodeN.setRightChild(rotateRight(nodeR));
 86         return rotateLeft(nodeN);
 87     }
 88     
 89     private BinaryNodeInterface<T> rotateLeftRight(BinaryNodeInterface<T> nodeN){
 90         BinaryNodeInterface<T> nodeL = nodeN.getLeftChild();
 91         nodeN.setLeftChild(rotateLeft(nodeL));
 92         return rotateRight(nodeN);
 93     }
 94     
 95     private BinaryNodeInterface<T> rebalance(BinaryNodeInterface<T> nodeN){
 96         int heightDifference = getHeightDifference(nodeN);
 97         if(heightDifference > 1){//左子树比右子树高
 98             if(getHeightDifference(nodeN.getLeftChild()) > 0)
 99                 nodeN = rotateRight(nodeN);//插入在左子树的左孩子中
100             else
101                 nodeN = rotateLeftRight(nodeN);
102         }
103         else if(heightDifference < -1){//右子树比左子树高
104             if(getHeightDifference(nodeN.getRightChild()) < 0)
105                 nodeN = rotateLeft(nodeN);//插入在右子树的右孩子中
106             else
107                 nodeN = rotateRightLeft(nodeN);
108         }
109         return nodeN;
110     }
111     
112     //获得结点nodeN的左右子树的高度之差
113     private int getHeightDifference(BinaryNodeInterface<T> nodeN){
114         int leftHeight = 0;
115         int rightHeight = 0;
116         if(nodeN.getLeftChild() != null){
117             leftHeight = nodeN.getLeftChild().getHeight();
118         }
119         if(nodeN.getRightChild() != null){
120             rightHeight = nodeN.getRightChild().getHeight();
121         }
122         return leftHeight - rightHeight;
123     }
124 }

整个实现的依赖代码参考：https://github.com/hapjin/data-structures-and-abstraction-with-java 中的tree、searchtree、list 目录下代码。