本文共 3933 字，大约阅读时间需要 13 分钟。

平衡二叉树（AVL树）

引入

问题：给一个数列{1，2，3，4，5，6，7}，要求创建一棵二叉排序树（BST）

分析：

上述BST存在问题的分析：

1. 左子树全部为空，且更像一个单链表
2. 插入速度没有影响，但是查询速度降低，因为查询速度明显降低，每一次还得比较左边空的子树
3. 解决方案：平衡二叉树（AVL）

基本介绍

1. 平衡二叉树，又名平衡二叉搜索树（Self- balancing binary search tree),又称之为AVL树，保证查询效率较高
2. AVL平衡二叉树又称之为自动平衡二叉树，在其添加和删除节点的过程中自动进行左旋转和右旋转。
3. 特点：空树或者是左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
4. 平衡二叉树的常用实现方法：红黑树，AVL，替罪羊树，Treap，伸展树等等。

构建平衡二叉树

应用案例——单旋转（左旋转）

思路分析：

用{4，3，6，5，7，8}创建对应的平衡二叉树

左旋转适用条件

1. 满足左子树和右子树的高度差为1，左低右高才可适用
2. 右子节点不为空
3. 右子树的右子树高度大于右子树左子树的高度

1. 创建一个新的结点newNode，值为当前根节点的值
   
2. 新节点的左子树设置为当前节点的左子树
   
3. 把新节点的右子树设置为当前节点的右子树的左子树
   
4. 将当前节点的值设置为右子节点的值
   
5. 把当前节点的右子树设置为右子树的右子树
   
6. 把当前节点的左子树设置为新节点
   
   左旋转左子树的高度增加，右子树的高度减小

代码实现

5. 计算当前子树的层数的方法
   class Node类里面的

//返回左子树的高度    public int leftHeight(){
           if(left == null){
               //左子树为空，说明已经到达底部            return 0;        }        return left.height();    }    //返回右子树的高度    public int rightHeight(){
           if(right == null){
               return 0;        }        return right.height();    }    //返回以该节点为根节点的这棵子树的高度    /**     * 计算以调用该方法的结点为根节点的子树的高度，从一开始计算     * @return 返回的是整型，     */    public int height(){
           return Math.max(left == null ? 0:left.height(),right == null ? 0:right.height()) + 1;        //加上自身的递归条件，每增加一层就在原来的基础上再增加一    }  public void leftRotate(){
           //创建新的结点，以当前根节点值为创建点        Node newNode = new Node(value);        //将新的节点的左子树指向当前节点的左子树        newNode.left = this.left;        //将新的结点的右子树指向当前节点右子树的左子树        newNode.right = this.right.left;        //将当前节点的值变为当前节点右子树的值        this.value = this.right.value;        //将当前节点的右子树指向原右子树的右子树        this.right = this.right.right;        //将当前结点的左子树指向新建结点        this.left = newNode;    }

应用案例——单旋转（右旋转）

同左旋转，仅仅只是方向有了改变。

右旋转适用的条件

1. 左子树的高度，减去右子树的高度差大于2
2. 左子树不为空
3. 左子树的右子树高度小于左子树的左子树高度

代码实现

1. 以当前节点的值创建新节点
2. 新节点的右子树为当前节点的右子树
3. 新节点的左子树为当前节点的左子树右子树
4. 当前节点的值为左子树的左节点的值
5. 当前节点指向左子树的左节点

public void rightRotate(){
           // 新建节点，其值等于当前结点        Node newNode = new Node(this.value);        //新建节点的左子树，等于当前节点的左子树        newNode.right = this.right;        //新建节点的右子树指向当前节点的右子树的左子树        newNode.left = this.left.right;        //将当前结点的右子树指向右子树的右子树        this.right = this.right.right;        //当前节点的值等于左子节点的值        this.value = this.left.value;        //将当前节点的左子树指向新建结点        this.left = newNode;    }

两种旋转方式的综合分析

右旋转：原数组整体偏左，左边的高度大于右边，同时左子树也是整体偏左，即左子树的左子树高度大于左子树的右子树高度

左旋转：原数组整体偏右，右边的高度大于左边，同时右子树也是整体偏右，即右子树的右子树高于右子树的左子树。 然而当原来的二叉树整体偏左局部偏右或者是整体偏右局部偏左就没有用 整体偏左，局部偏右 相对于根节点而言，左子树的高度大于右子树的高度，但是向相对于根节点的左子树，是右子树的高度大于左子树的高度。 整体偏右，局部偏左 相对于根节点而言，右子树的高度大于左子树，相对于根节点的右子树，左子树的高度大于右子树。

修改与完善（双旋转）

1. 原则：从下往上，从局部再到整体。
2. 以下图为例
   

• 先对框内部的子树进行右旋转，使之成为如下情况
• 然后在对整体进行左旋转，即为最终结果
  
• 改善：
  将所有的左旋和右旋判定条件放到对应的添加（addNode）和删除（delNode）语句中

代码实现

class AVLTree中的类

/**     * 添加对应的结点     *     * @param node     */    public void add(Node node) {
           if (node == null) {
               return;        }        if (node.value < this.value) {
               if (this.left == null) {
                   this.left = node;            } else {
                   this.left.add(node);            }        } else {
               if (this.right == null) {
                   this.right = node;            } else {
                   this.right.add(node);            }        }        //右高左低，向左进行旋转，中和高度        if (rightHeight() - leftHeight() > 1){
               if(right != null && right.leftHeight() - right.rightHeight() > 1){
                   right.leftRotate();                leftRotate();            }else{
                   leftRotate();            }        }        //左高右低，向右进行旋转，中和高度        if(leftHeight() - rightHeight() > 1){
               if(left != null && left.rightHeight() > left.leftHeight()){
                   left.leftRotate();                rightRotate();            }else{
                   rightRotate();            }        }        //想法，应该是从下往上进行判断，所以个人认为应该进行递归调用    }

分析与总结

1. 上述方法是AVL树，是在添加和删除结点种会自动进行平衡的二叉树，而不是将一个已经是完全的顺序二叉树进行平衡化
2. 在添加和删除节点的过程中总共有四种情况，单向偏移的单旋情况，交叉偏移的的双旋情况，具体理解请看上图
3. 个人认为在对一个完全的顺序二叉树进行平衡化的时候应采用递归的方式进行。
   

转载地址：http://eqgpb.baihongyu.com/