平衡树以及JAVA实现

深藏阁楼爱情的钟 2022-03-12 09:42 111阅读 0赞

### **一.平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法）。** ###

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

### **二.失衡类型、旋转平衡技巧和代码实现** ###

**LL类型：****在失衡结点的左孩子的左子树上插入** \- - -LL右旋

![20190305182829676.png][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzIwMDQ4_size_16_color_FFFFFF_t_70][]![20190305182931125.png][]

代码实现：

// LL平衡旋转(右单旋转)
        public static AVLNode LLRotate(AVLNode p){ // p为失衡点
            AVLNode lsubtree = p.lchild;
            p.lchild = lsubtree.rchild; // 将失衡点p的左孩子lsubtree的右子树成为失衡点p的左子树
            lsubtree.rchild = p; // 将失衡点作为lsubtree的右子树
            // 重新调整失衡点及其左孩子节点的高度值(只有这两个节点的高度值可能发生改变)
            p.height = Math.max(getHeight(p.lchild), getHeight(p.rchild)) + 1;
            lsubtree.height = Math.max(getHeight(lsubtree.lchild), p.height) + 1;
            return lsubtree; // 失衡点p的左孩子成为新的根节点(取代原失衡点的位置)
        }

**LR类型：在失****衡结点的右孩子的左子树上插入** \- - -LR右旋

![20190305193235981.png][]![20190305193530357.png][]![20190305193605950.png][]

// LR平衡旋转(先左后右双旋转)
        public static AVLNode LRRotate(AVLNode p){
            p.lchild = RRRotate(p.lchild); // 先将失衡点p的左子树进行RR平衡旋转
            return LLRotate(p); // 再将失衡点p进行LL平衡旋转并返回新节点代替原失衡点p
    
        }

**RL类型：在失衡结点的左孩子的右子树上插入** \- - -RL旋转

![20190305194424394.png][]![20190305194507708.png][]![20190305194544350.png][]

// RL平衡旋转(先右后左双旋转)
        public static AVLNode RLRotate(AVLNode p){
            p.rchild = LLRotate(p.rchild); // 先将失衡点p的右子树进行LL平衡旋转 
            return RRRotate(p); // 再将失衡点p进行RR平衡旋转并返回新节点代替原失衡点p
        }

**RR类型：在失衡结点的右孩子的右子树上插入** \- - -[RR][]右旋

![2019030519394764.png][]![20190305194222789.png][]![20190305194313443.png][]

// RR平衡旋转(左单旋转)
        public static AVLNode RRRotate(AVLNode p){
            AVLNode rsubtree = p.rchild;
            p.rchild = rsubtree.lchild; // 将失衡点p的右孩子rsubtree的左子树成为失衡点p的右子树
            rsubtree.lchild = p; // 将失衡点p作为rsubtree左子树
            // 重新调整失衡点及其右孩子节点的高度值
            p.height = Math.max(getHeight(p.lchild), getHeight(p.rchild)) + 1;
            rsubtree.height = Math.max(getHeight(rsubtree.lchild), getHeight(rsubtree.rchild)) + 1;
            return rsubtree; //  失衡点p的右孩子成为新的根节点(取代原失衡点的位置)
        }

### 三、平衡二叉树的定义以及插入删除 ###

平衡二叉树的插入删除和二叉树的几乎一样，但操作完之后需要判断一下高度差是否失衡，如果失衡要进行旋转调整。

下面是完整代码：

package Demo05;
    
    public class Demo05{
    public static void main(String[] args) {
            AVLNode root = null;
            int []a= {20,8,2,4,5,6,28,18,19,33,25,26};
            for(int i = 0; i <10; i++){
                root = insert(root, a[i]);
            }
            insert(root, 3);
            inOrder(root);
            System.out.println();
    //      System.out.println("height: " + (root.height + 1) + " " + (int)Math.ceil(Math.log(10)/ Math.log(2))); // 树的高度为叶子节点的最大深度加上1(根节点为第一层)
            remove(root, 18);
            inOrder(root);
        }
    
        public static AVLNode insert(AVLNode root, int data) {
            if (root == null) {
                root = new AVLNode(data);
                return root;
            }
            if (data <= root.data) { // 插入到其左子树上
                root.lchild = insert(root.lchild, data);
                if (getHeight(root.lchild) - getHeight(root.rchild) > 1) { // 由于是向当前root树的左边插入，所以左子树高度必定不小于右子树高度(条件>1实质上等价于==2)
                    if (data <= root.lchild.data) { // 最后插入的叶子结点在该root树的左孩子的左边
                        root = LLRotate(root); // 将调整后的root返回给其父节点的左子树域
                    }else{ // 最后插入的叶子结点在该root树的左孩子的右边
                        root = LRRotate(root);
                    }
                }
            }else{ // 插入到其右子树上
                root.rchild = insert(root.rchild, data);
                if(getHeight(root.rchild) - getHeight(root.lchild) > 1){
                    if(data <= root.rchild.data){
                        root = RLRotate(root);
                    }else{
                        root = RRRotate(root);
                    }
                }
            }
            // 当插入新的节点后，从这个节点到根节点的最短路径上的节点的高度值一定会发生改变，另外当出现失衡点时，这个失衡点的所有祖先节点的高度值也可能会发生改变
            root.height = Math.max(getHeight(root.lchild), getHeight(root.rchild)) + 1; // 重新调整root节点的高度值
            return root;
        }
    
        public static AVLNode remove(AVLNode root, int data){
            if(root == null){ // 没有找到删除的节点
                return null;
            }
            if(data < root.data){ // 在左子树上删除
                root.lchild = remove(root.lchild, data);
                if(getHeight(root.rchild) - getHeight(root.lchild) > 1){ // 在左子树上删除，右子树高度一定不小于左子树高度
                    if(getHeight(root.rchild.lchild) > getHeight(root.rchild.rchild)){
                        root = RLRotate(root);
                    }else{
                        root = RRRotate(root);
                    }
                }
            }else if(data == root.data){ // 找到删除的节点
                if(root.lchild != null && root.rchild != null){ // 删除的节点既有左子树又有右子树
                    root.data = findNextNode(root).data; // 将失衡点的data域更改为其直接后继节点的data域
                    root.rchild = remove(root.rchild, root.data); // 将问题转换为删除其直接后继节点
                }else{ // 只有左子树或者只有右子树或者为叶子结点的情况
                    root = (root.lchild == null) ? root.rchild : root.lchild;
                }
            }else{ // 在root的右子树上查找删除节点
                root.rchild = remove(root.rchild, data);
                if(getHeight(root.lchild) - getHeight(root.rchild) > 1){
                    if(getHeight(root.lchild.lchild) > getHeight(root.lchild.rchild)){
                        root = LLRotate(root);
                    }else{
                        root = LRRotate(root);
                    }
                }
            }
            if(root != null){ // 更新root的高度值
                root.height = Math.max(getHeight(root.lchild), getHeight(root.rchild)) + 1;
            }
            return root;
        }
    
        // LL平衡旋转(右单旋转)
        public static AVLNode LLRotate(AVLNode p){ // p为失衡点
            AVLNode lsubtree = p.lchild;
            p.lchild = lsubtree.rchild; // 将失衡点p的左孩子lsubtree的右子树成为失衡点p的左子树
            lsubtree.rchild = p; // 将失衡点作为lsubtree的右子树
            // 重新调整失衡点及其左孩子节点的高度值(只有这两个节点的高度值可能发生改变)
            p.height = Math.max(getHeight(p.lchild), getHeight(p.rchild)) + 1;
            lsubtree.height = Math.max(getHeight(lsubtree.lchild), p.height) + 1;
            return lsubtree; // 失衡点p的左孩子成为新的根节点(取代原失衡点的位置)
        }
    
        // RR平衡旋转(左单旋转)
        public static AVLNode RRRotate(AVLNode p){
            AVLNode rsubtree = p.rchild;
            p.rchild = rsubtree.lchild; // 将失衡点p的右孩子rsubtree的左子树成为失衡点p的右子树
            rsubtree.lchild = p; // 将失衡点p作为rsubtree左子树
            // 重新调整失衡点及其右孩子节点的高度值
            p.height = Math.max(getHeight(p.lchild), getHeight(p.rchild)) + 1;
            rsubtree.height = Math.max(getHeight(rsubtree.lchild), getHeight(rsubtree.rchild)) + 1;
            return rsubtree; //  失衡点p的右孩子成为新的根节点(取代原失衡点的位置)
        }
    
        // LR平衡旋转(先左后右双旋转)
        public static AVLNode LRRotate(AVLNode p){
            p.lchild = RRRotate(p.lchild); // 先将失衡点p的左子树进行RR平衡旋转
            return LLRotate(p); // 再将失衡点p进行LL平衡旋转并返回新节点代替原失衡点p
    
        }
    
        // RL平衡旋转(先右后左双旋转)
        public static AVLNode RLRotate(AVLNode p){
            p.rchild = LLRotate(p.rchild); // 先将失衡点p的右子树进行LL平衡旋转 
            return RRRotate(p); // 再将失衡点p进行RR平衡旋转并返回新节点代替原失衡点p
        }
    
        private static class AVLNode{
            private AVLNode lchild = null;
            private AVLNode rchild = null;
            private int data;
            private int height; // 记录该节点所在的高度
    
            public AVLNode(int data){
                this.data = data;
            }
        }
    
        public static int getHeight(AVLNode p){
            return p == null ? -1 : p.height; // 空树的高度为-1
        }
    
        public static void inOrder(AVLNode root){
            if(root != null){
                inOrder(root.lchild);
                System.out.print(root.data + " ");
                inOrder(root.rchild);
            }
        }
    
        // 得到p节点的后继节点(中序遍历),实际上也是p节点的右子树上的关键字值最小的节点
        public static AVLNode findNextNode(AVLNode p){
            if(p == null){
                return null;
            }
            AVLNode r = p.rchild;
            while(r != null && r.lchild != null){
                r = r.lchild;
            }
            return r;
        }
    
        // 得到p节点的直接前驱节点(中序遍历),实际上也是p节点的左子树上的关键字值最大的节点
        public static AVLNode findPreviousNode(AVLNode p){
            if(p == null){
                return null;
            }
            AVLNode l = p.lchild;
            while(l != null && l.rchild != null){
                l = l.rchild;
            }
            return l;
        }
    }

[20190305182829676.png]: https://img-blog.csdnimg.cn/20190305182829676.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzIwMDQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190305182734666.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzIwMDQ4,size_16,color_FFFFFF,t_70
[20190305182931125.png]: /images/20220312/c93dcb2e26064fbd8b21df75123345ea.png
[20190305193235981.png]: https://img-blog.csdnimg.cn/20190305193235981.png
[20190305193530357.png]: https://img-blog.csdnimg.cn/20190305193530357.png
[20190305193605950.png]: /images/20220312/f0ef5ed673314dc7a2dc8d30212074b7.png
[20190305194424394.png]: https://img-blog.csdnimg.cn/20190305194424394.png
[20190305194507708.png]: https://img-blog.csdnimg.cn/20190305194507708.png
[20190305194544350.png]: /images/20220312/5b4ee60e0f4847b39445ba0dca00085c.png
[RR]: https://www.baidu.com/s?wd=RR&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[2019030519394764.png]: https://img-blog.csdnimg.cn/2019030519394764.png
[20190305194222789.png]: https://img-blog.csdnimg.cn/20190305194222789.png
[20190305194313443.png]: /images/20220312/c3f4bad2a65542da969c887adba772ac.png