看图说话之平衡二叉排序树

    本文在看图说话之二叉排序树的基础上介绍了平衡二叉排序树，结构性较好的二叉排序树其插入和删除操作的时间复杂度接近Log(N)，但是存在某些特定的情况二叉排序树会退化到单链表的情况，比如由顺序或者逆序或者基本有序的数组构建的排序二叉树，此时插入和删除操就上升到了Log(N)的时间复杂度。下图所示就是结构性良好和退化的二叉排序树。

图1 最优BST树形结构和最差BST树形
    为了解决二叉排序树的这种退化的情况，在其基础上提出了平衡二叉排序树，实现平衡二叉排序树的方法有很多种，其中最基础就是AVL树，本文详细的介绍下AVL树实现平衡的基本原理以保证二叉排排序树具有Log(N)的时间复杂界。

一丶平衡二叉排序树

    平衡二叉排序树如其名字在二叉树上约定了平衡条件，通过下图这个平衡二叉树和非平衡二叉树来说明平衡二叉树的平衡条件。

图2 平衡和非平衡二叉树

    平衡性，是指每个节点的左子树高度和右子树高度之差不超过1，即 Math.abs(Hieght(node.left) –Height(node.right))<1。对于图2中的平衡二叉树而言，其上每个节点都满足这个性质。图2中的非平衡树，之所以不是平衡树，是因为在根节点处平衡性遭到了破坏，其左子树高度和右子树高度之差为2。

二丶AVL树平衡性调整策略

    我觉得研究AVL树调整平衡性策略的正确姿势应该包括两步，第一步研究导致二叉排序树不平衡的情况是哪几种。第二步针对具体的不平衡情况如何调整。
先研究二叉排序树的不平衡情况，然后针对二叉排序树的不平衡特点给出解决方案：

(1) 向节点的左儿子的左子树插入元素导致的平衡性破坏。

图3 第一种非平衡情况

    可以看到，插入元素1后，是节点10处的平衡性遭到了破坏。这里要强调一下，在更一般的情况下，插入元素有破坏平衡性的可能，而平衡性被破坏的节点可能发生在插入路径上的每一个节点，可能是父节点，可能是其他节点。
对于该种平衡性破坏给出的解决方法称为左旋转其过程如下图所示：

图 4Single左旋转平衡性调整
    通过图4可以清晰的看出Single左旋转调整平衡性的特点，利用文字描述过于拗口，利用伪代码描述如下：假设平衡性被破坏的节点是node。

//调整node节点平衡性
node = SingleLeftRotation(node);
//balacne函数定义如下
public node SingleLeftRotation( (Nodenode){
        if(node ==null) return null;
           Node newRoot= node.left;
           node.left = newRoot.right;
           newRoot.right = node;
           return newRoot;
}

(2)向节点的右儿子的右子树插入元素导致的平衡性破坏。

图5第二种非平衡情况

该种情况下的非平衡性情况十分清晰，并且和第一种非平衡性情况是对称的，不妨成这种非平衡性破坏为“右右“，第一种非平衡性破坏为”左左“。该种情况下的调整过程如图所示，这调整过程称为single右旋转。

图6 single右旋转调整

上述调整过程用伪代码实现如下：

//调整node节点平衡性
node = SingleRightRotation(node);
//balacne函数定义如下
public node SingleRightRotation( (Nodenode){
        if(node==null) return null;
           Node newRoot= node.right;
           node.right = newRoot.left;
           newRoot.left= node;
           return newRoot;
}

(3)向节点的左儿子的右子树插入元素导致平衡性破坏

图7 第三种平衡破坏情况

这种不平衡性的情况，形象的将其称之为“左右“不平衡，该情况的不平衡的过程如下图所示：

图 8 double左旋转调整
    图8清晰的说明了调整平衡性的过程，在掌握的single左旋转和single右旋转的基础上看懂上述过程丝毫不苦难，上述过程称为double左旋转利用伪代码描述如下：

//调整node节点平衡性
node = dounleLeftRotation (node);
//balacne函数定义如下
public node dounleLeftRotation(Nodenode){
           node.left=singleRightRotation(node.left);
           node = singleLeftRotation(node);
           return node;
}

(4)向节点的右儿子的左子树插入元素导致平衡性破坏

图9 第四种不平衡情况

该种平衡情况是向右儿子的左子树插入元素导致不平衡，这种情况形象的称之为“右左“不平衡，和”左右“不平衡是对称的处理的手段都是类似的。下图详细的描述了这种情况如何调整平衡

图10 double右旋转
通过图10可以清晰的看到调整平衡的过程，上述过程和double左旋转是对称的操作，利用伪代码描述如下：

//调整node节点平衡性
node = dounleRightRotation (node);
//balacne函数定义如下
public node dounleLeftRotation(Nodenode){
           node.left=singleLeftRotation(node.left);
           node = singleRightRotation(node);
           return node;
}

三丶AVL树完整的java实现

public classAVLTree {
    publicNode root = null;
     publicstatic void main(String []args){
       int[] elements = new int[]{1,2,3,4,5};
       AVLTree avl = new AVLTree();
       /****测试插入，建树和中序遍历操作***/
       avl.buildTree(elements);
       /********测试二叉树的高度***************/
       System.out.println(avl.root.height);
    //  bst.midTrace();
    //  System.out.println();
       /****测数删除操作之无儿子***************/
    //  bst.delete(9);
    //  bst.midTrace();
       /****测数删除操作之只有一个儿子***************/
    //  bst.delete(4);
    //  bst.midTrace();
       /****测数删除操作只有两个儿子***************/
    //  bst.delete(5);
    //  bst.midTrace();
    }
   
    //节点类型定义
    publicstatic class Node{
       publicint element;
       publicNode left;
       publicNode right;
       //平衡二叉排序树，为了保证平衡，对每个节点维护了高度信息
       publicint  height;
       publicNode(int element){
           this.element = element;
           left = null;
           right = null;
           height = 0;
       }
    }
    //外部使用的插入方法
    publicvoid insert(int element){
       root=insert(element,root);
    }
    //内部使用的插入方法
    private  Node insert(int element,Node root){
       if(root==null)
           return new Node(element);
       intdelta = element-root.element;
       if(delta<0){
           root.left = insert(element,root.left);
       }elseif(delta>0){
           root.right = insert(element,root.right);
       }else{
           //不做处理
       }
       returnbalanced(root);
    }
    //外部使用的建树方法
    publicvoid buildTree(int [] elements){
       if(root==null){
           for(int i=0;i<elements.length;i++){
              insert(elements[i]);
           }
       }else{
           //若树以存在，则不能建
       }
    }
    publicvoid delete(int element){
       delete(element,root);
    }
    publicNode delete(int element,Node root){
       //未定位到删除元素
       if(root==null) return null;
       intdelta = element-root.element;
       if(delta<0){
           root.left = delete(element,root.left);
       }elseif(delta>0){
           root.right =delete(element,root.right);
       }else{
           if(root.left!=null&&root.right!=null){
              Node node = findMin(root.right);
              root.element =node.element;
              root.right = delete(node.element,root.right);
           }else{
              root = root.left!=null?root.left:root.right;
           }
       }
       returnbalanced(root);
    }
    //中序遍历二叉树
    publicvoid midTrace(){
       if(root!=null){
           print(root);
       }
    }
    privatevoid print(Node node){
       if(node!=null){
           print(node.left);
           System.out.print(node.element+" ");
           print(node.right);
       }
    }
    //找到该节点下子树的最小节点。
    publicNode findMin(Node node){
       if(node.left==null)
           return node;
       else
          
           return findMin(node.left);
    }
    publicNode balanced(Node node){
       node.height= Math.max(getHeight(node.left),getHeight(node.right))+1;
       if(getHeight(node.left)-getHeight(node.right)>1){
           if(getHeight(node.left.left)>getHeight(node.left.right)){
              node = singleLeftRotation(node);
           }else{
              node = doubleLeftRotation(node);
           }
       }
       if(getHeight(node.right)-getHeight(node.left)>1){
           if(getHeight(node.right.left)>getHeight(node.right.right)){
              node =doubleLeftRotation(node);
           }else{
              node = singleRightRotation(node);
           }
       }
       returnnode;
    }
    publicint getHeight(Node node){
       returnnode==null?-1:node.height;
    }
    publicNode singleLeftRotation(Node node){
       Node newRoot = node.left;
       node.left = newRoot.right;
       //左右子树变化更新高度
       node.height = Math.max(getHeight(node.left),getHeight(node.right))+1;
       newRoot.right=node;
       //左右子树变化更新高度
       newRoot.height=  Math.max(getHeight(newRoot.left),getHeight(newRoot.right))+1;
       returnnewRoot;
    }
    publicNode singleRightRotation(Node node){
       Node newRoot = node.right;
       node.right = newRoot.left;
       //左右子树变化更新高度
       node.height = Math.max(getHeight(node.left),getHeight(node.right))+1;
       newRoot.left=node;
       //左右子树变化更新高度
       newRoot.height=  Math.max(getHeight(newRoot.left),getHeight(newRoot.right))+1;
       returnnewRoot;
    }
    publicNode doubelRightRotation(Node node){
       node.right = singleLeftRotation(node.right);
       returnsingleRightRotation(node);
    }
    publicNode doubleLeftRotation(Node node){
       node.left = singleRightRotation(node.left);
       returnsingleLeftRotation(node);
    }
}

Reference:
[1] 数据结构与算法 java语言描述
[2] 原文博客链接