数据结构 - (AVL)平衡二叉树

AVL树本质上还是二叉树，但是比二叉搜索树多了一个条件：每个节点的左右子树高度不超过1
因为二叉搜索树在极端情况下无限趋近于链表，这种情况下不能体现二叉搜索树的高效率。如下图

{
     Node<T> root;
    
    {
         T key;
         Node<T> left;
         Node<T> right;


        {
            .key = key;
        }
    }
}

{
     height(root);
}

{
    ;
     {
        ;
    }
}

AVL树在添加或者删除后，可能导致AVL树失去平衡。
失去平衡包括四种：LL(左左)，LR(左右)，RR(右右)，RL(右左),具体参考下图

旋转方式：将k1变成根节点，k2变成k1的右子树，"k1的右子树"变成"k2的左子树"

/**
* 左左旋转
* @param tree
* @return
*/
> tree){
 ;
 tree.;
 lTree. = tree;
  lTree;
}

旋转方式：旋转方式与LL旋转类似

/**
 * 右右旋转
 * @param tree
 * @return
 */
> tree){
    ;
    tree.;
    rTree. = tree;
     rTree;
}

旋转方式：左右旋转需要经过两次调整，第一次旋转是围绕"k1"进行的"RR旋转"，第二次是围绕"k3"进行的"LL旋转"

/**
 * 左右旋转
 *  tree
 * 
 */
{
    rrRotation(tree.left);
     llRotation(tree);
}

旋转方式：右左旋转同样需要经过两次调整，第一次旋转是围绕"k3"进行的"LL旋转"，第二次是围绕"k1"进行的"RR旋转"

/**
 * 右右旋转
 *  tree
 * 
 */
{
    llRotation(tree.right);
     rrRotation(tree);
}

{
    ){
        root =  Node<>(key);
    } {
        
        root = fixAfterOperation(root);
    }
}

{
     tmp;
    ){
        tree =  Node<>(key);
    } {
        tmp = key.compareTo(tree.key);
        ){
            tree.left = (tree.left,key);
        }){
            tree.right = (tree.right,key);
        } {
             tree;
        }
    }
     tree;
}

当树添加或者删除某一节点后，如果导致AVL树失衡，旋转树