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

数据结构 - (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树失衡，旋转树

> tree) {
     (tree != null) {
        
            
                tree = llRotation(tree);
            } 
                tree = lrRotation(tree);
            }

        }

        
            
                tree = rlRotation(tree);
            }  {
                tree =rrRotation(tree);
            }
        }
    }
     tree;
}

{
    ){
        (root,key);
        root = fixAfterOperation(root);
    }
}

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


{
    Node<T> result = tree.right;
    ){
        result = result.left;
    }
     result;
}

linuxboy的RSS地址：https://www.linuxboy.net/rssFeed.aspx

本文永久更新链接地址：https://www.linuxboy.net/Linux/2019-03/157249.htm