AVL自平衡树

た入场券 2022-12-31 11:22 28阅读 0赞

因为AVL自平衡树是建立在二叉排序树的基础上的，所以这里我先简单描述一下二叉排序树和代码实现。

### 二叉排序树(Binary Sort(Search) Tree)(BST) ###

二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。 特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点

比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70][]

因为二叉排序树的插入比较简单，下面就直接代码实现了

首先创建一个节点类(因为后面的自平衡也会使用这个节点，只是在节点中添加新的方法，后面就不再过多赘述了)

class Node{
        public int val;
        public Node left;
        public Node right;
    
        public Node(int val){
            this.val = val;
        }
    
        public void add(Node node){
            if(node == null)
                return;
            if(node.val < this.val){
                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);
                }
            }
        }
    
        public void infixOrder(){
            if(this.left != null){
                this.left.infixOrder();
            }
            System.out.println(this);
            if(this.right != null){
                this.right.infixOrder();
            }
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    '}';
        }
    }

创建二叉搜索树

class BinarySortTree{
        private Node root;
    
        public void setRoot(Node root) {
            this.root = root;
        }
    
        public void add(Node node){
            if(root == null){
                root = node;
                return;
            }
            root.add(node);
        }
    
        public void infixOrder(){
            if(root != null){
                root.infixOrder();
                return;
            }
            System.out.println("二叉排序树为空~~~");
        }
        
    }

二叉搜索树和节点类已经创建好了，如果需要添加节点，主需要遍历数组添加节点

![20201229162026881.gif][]

BinarySortTree binarySortTree = new BinarySortTree();
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        for (int i = 0; i < arr.length; i++) {
        binarySortTree.add(new Node(arr[i]));

下面实现二叉排序树的删除节点功能

因为删除一个节点需要拿到这个节点和这个和节点的双亲节点所以在节点类中添加search()和searchParent()方法，并封装在树类中

public Node search(int val){
        if(this.val == val){
            return this;
        }
        if(val < this.val){
            if (this.left != null){
                return this.left.search(val);
            }else
                return null;
        }else {
            if (this.right != null){
                return this.right.search(val);
            }else
                return null;
        }
    }

public Node search(int val){
        if(root != null){
            return root.search(val);
        }
        return null;
    }

public Node searchParent(int val){
        if(this.left != null && this.left.val == val ||
                this.right != null && this.right.val == val){
            return this;
        }
        if(val < this.val && this.left != null){
            return this.left.searchParent(val);
        }else if(val > this.val && this.right != null){
            return this.right.searchParent(val);
        }
        return null;
    }

public Node searchParent(int val){
        if(root != null){
            return root.searchParent(val);
        }
        return null;
    }

二叉排序树的删除情况比较复杂，有下面三种情况需要考虑

![20201229153902568.png][]

1、删除叶子节点 (比如：2, 5, 9, 12)

![20201229162200203.gif][]

if(target.left == null && target.right == null){//叶子节点
        if (parent.left != null && parent.left.val == val){
            parent.left = null;
            return;
        }
        if(parent.right != null && parent.right.val == val){
            parent.right = null;
            return;
        }

2、删除只有一颗子树的节点 (比如：1)

![20201229162348851.gif][]

else {//有一个子树的叶子节点
       if(parent.left.val == val){
           if(target.left != null){
               parent.left = target.left;
               return;
           }
           if(target.right != null){
               parent.left = target.right;
               return;
           }
       }else {
           if(target.left != null){
               parent.right = target.left;
               return;
           }
           if(target.right != null){
               parent.right= target.right;
               return;
           }
       }

3、删除有两颗子树的节点. (比如：7, 3，10 )

![20201229162525260.gif][]

![20201229162536203.gif][]

这里有两种方式，要么是删除右子树的最小值，要么是删除左子树的最大值，两种方法我都是实现，实际中只需要调用一种

public int delLeftMax(Node node){
        Node target = node;
        while (target.right != null){
            target = target.right;
        }
        delNode(target.val);
        return target.val;
    }

public int delRightTreeMin(Node node){
        Node target = node;
        while(target.left != null){
            target = target.left;
        }
        delNode(target.val);
        return target.val;
    }

else if(target.left != null && target.right != null){//两颗子树的非叶子节点
       int minVal = delRightTreeMin(target.right);
       target.val = minVal;

删除节点代码总结

public void delNode(int val){
        if (root == null){
            return;
        }
        if (root.val == val && root.left == null && root.right == null){
            root = null;
            return;
        }
        Node target = search(val);
        if (target == null)
            return;
        Node parent = searchParent(val);
        if (target.left == null && target.right == null){
            if (parent.left != null && parent.left.val == val){
                parent.left = null;
                return;
            }else{
                parent.right = null;
                return;
            }
        }else if (target.left != null && target.right != null){
            int maxVal = delLeftMax(target.left);
            target.val = maxVal;
        }else {
            if (parent.left != null && parent.left.val == val){
                if (target.left != null){
                    parent.left = target.left;
                    return;
                }else {
                    parent.left = target.right;
                    return;
                }
            }else {
                if (target.left != null){
                    parent.right = target.left;
                    return;
                }else {
                    parent.right = target.right;
                    return;
                }
            }
        }
    }

以上就是二叉排序树的实现过程。分析二叉排序可能的问题

给你一个数列\{1,2,3,4,5,6\}，要求创建一颗二叉排序树(BST), 并分析问题所在.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 1][]

左边BST 存在的问题分析:

1、左子树全部为空，从形式上看，更像一个单链表.

2、插入速度没有影响

3、查询速度明显降低(因为需要依次比较), 不能发挥BST 的优势，因为每次还需要比较左子树，其查询速度比 单链表还慢

4、解决方案-平衡二叉树(AVL)

### 平衡二叉树 ###

平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。

具有以下特点：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

因为这里需要讨论树的深度，所以在节点类中添加了三个方法，height()、leftHeight()、rightHeight()

public int leftHeight(){
        if (left != null){
            return left.height();
        }
        return 0;
    }
    public int rightHeight(){
        if (right != null){
            return right.height();
        }
        return 0;
    }
    public int height(){
        return Math.max(left == null ? 0 : left.height(),
                right == null ? 0 : right.height()) + 1;
    }

AVL树左旋转

![20201229162858673.gif][]

问题：当插入8 时 rightHeight() - leftHeight() > 1 成立，此时，不再是一颗avl树了.

怎么处理--进行左旋转.

1、 创建一个新的节点 newNode (以4这个值创建) ,创建一个新的节点，值等于当前根节点的值

//把新节点的左子树设置了当前节点的左子树

2、 newNode.left = left //把新节点的右子树设置为当前节点的右子树的左子树

3、newNode.right =right.left; 把当前节点的值换为右子节点的值

4、value=right.value;

//把当前节点的右子树设置成右子树的右子树

5.、right=right.right;

把当前节点的左子树设置为新节点

6、 left=newLeft;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 2][]

左旋转代码实现

public void leftRotate(){
        Node newNode = new Node(val);
        newNode.left = left;
        newNode.right = right.left;
        val = right.val;
        right = right.right;
        left = newNode;
    }

AVL右旋转

![20201229163032739.gif][]

问题：当插入6 时 leftHeight()  - rightHeight()  > 1 成立，此时，不再是一颗avl树了.

怎么处理--进行右旋转.\[就是降低左子树的高度\], 这里是将 9 这个节点，通过右旋转，到右子树

1.、创建一个新的节点 newNode (以10这个值创建) ,创建一个新的节点，值等于当前根节点的值

//把新节点的右子树设置了当前节点的右子树

2、 newNode.right = right

//把新节点的左子树设置为当前节点的左子树的右子树

3、newNode.left =left.right;

把当前节点的值换为左子节点的值

4、value=left.value;

//把当前节点的左子树设置成左子树的左子树

5、 left=left.left;

把当前节点的右子树设置为新节点

6、 right=newLeft;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 3][]

右旋转代码实现

public void rightRotate(){
        Node newNode = new Node(val);
        newNode.right = right;
        newNode.left = left.right;
        val = left.val;
        left = left.left;
        right = newNode;
    }

双旋转分析

前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列 int\[\] arr = \{ 10, 11, 7, 6, 8, 9 \};  运行原来的代码可以看到，并没有转成 AVL树. int\[\] arr = \{2,1,6,5,7,3\}; // 运行原来的代码可以看到，并没有转成 AVL树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 4][]

所以这里应该先对根节点的左节点进行左旋，再进行右旋，重写add方法

![20201229163257167.gif][]

public void add(Node node){
        if (node.val < val){
            if (left != null){
                left.add(node);
            }else {
                left = node;
            }
        }else {
            if (right != null){
                right.add(node);
            }else {
                right = node;
            }
        }
        if((leftHeight() - rightHeight()) > 1){
            if (left != null && (left.rightHeight() - left.leftHeight()) > 1){
                left.leftRotate();
                rightRotate();
            }else {
                rightRotate();
                return;
            }
        }
        if ((rightHeight() - leftHeight()) > 1){
            if (right != null && (right.leftHeight() - right.rightHeight()) > 1){
                right.rightRotate();
                leftHeight();
            }else {
                leftRotate();
                return;
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70]: /images/20221120/38ae104019a24de194673a9447e2e112.png
[20201229162026881.gif]: /images/20221120/f8fbf3d3c6d8400bb9677768d866590d.png
[20201229153902568.png]: /images/20221120/e8fe05321d8b4c749f73810247aad040.png
[20201229162200203.gif]: https://img-blog.csdnimg.cn/20201229162200203.gif
[20201229162348851.gif]: https://img-blog.csdnimg.cn/20201229162348851.gif
[20201229162525260.gif]: https://img-blog.csdnimg.cn/20201229162525260.gif
[20201229162536203.gif]: https://img-blog.csdnimg.cn/20201229162536203.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201229154930920.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[20201229162858673.gif]: https://img-blog.csdnimg.cn/20201229162858673.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201229155600381.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[20201229163032739.gif]: https://img-blog.csdnimg.cn/20201229163032739.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201229155828697.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201229155947431.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[20201229163257167.gif]: https://img-blog.csdnimg.cn/20201229163257167.gif