• 高阶 DS --- AVL 树

    目录

    1、 二叉搜索树回顾以及性能分析

    2、 AVL树

    1、 二叉搜索树回顾以及性能分析

    1.1、二叉搜索树的概念

    二叉搜索树又称为二叉排序树，它可以是一颗空树，或者是满足下述条件的一颗二叉树

    1、如果其左子树不为空，左子树上所有结点的数值都小于根结点值
    2、如果其右子树不为空，右子树上所有结点的数值都大于根结点值
    3、此二叉树搜素树，左右子树均为二叉搜索树
    4、二叉搜索树的中序遍历可以得到有序序列

    1.2 二叉搜索树的查找

    二叉搜索树遵守这样的原则去搜索：
    设需要查找的元素为：key，结点数值为 val
    如果根结点不为空

    1、root.val == key 此结点就是要查找的结点，返回 true
    2、root.val > key 遍历 root 的左树
    3、root.val < key 遍历 root 的右树
    4、最后搜索完毕没有返回 true 证明没有此结点返回 false

    1.3 二叉树查询性能分析

    对于 n 个结点的二叉搜索树，每一个元素查找的概率一样，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多
    那么分析两种极端情况：

    1、完全二叉树（搜素次数最少）: O(logN)
    在这里插入图片描述
    2、单枝树（搜素次数最多）：O(n)
    在这里插入图片描述

    2、 AVL树

    2.1 AVL树的概念

    二叉搜索树，在退化为单枝树时搜索效率较为低效，所以引入 AVL 数（平衡二叉树），再插入新结点的时候，调整树中的结点，使左右子树的高度差的绝对值 <= 1，减少树的高度，提高搜索效率

    2.2 AVL树节点的定义 

    static class TreeNode{
        //1、结点数值
        public int val;
        //2、左结点
        public TreeNode left;
        //3、右结点
        public TreeNode right;
        //4、父亲结点
        public TreeNode parent;
        //5、左右子树高度差 —— 平衡因子
        public int bf;
        //6、提供构造方法
        public TreeNode(int val){
            this.val = val;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    这里的父亲结点是为了记录插入位置的父亲结点，便于插入

    2.3 AVL树的插入

    插入分为两步：
    ——————————————
    ①、寻找结点插入的位置
    ②、进行插入

    • ①、寻找结点插入的位置（核心代码），这里的查找位置的过程遵循二叉搜索树的查找原则即可
    //核心代码
        TreeNode node = new TreeNode(val);
        if(root == null){
            root = node;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;

        while(cur != null){
            if(cur.val == val){
                return false;
            }else if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else {
                parent = cur;
                cur = cur.right;
            }
        }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • ②、插入结点：判断插入的数值和父节点的数值大小，比父节点数值大，插在右边，比父节点数值小，插在左边，然后修改插入结点的父节点（指向 parent）, cur 重新指向新插入的结点
    if(val > parent.val){
            parent.right = node;
        }else{
            parent.left = node;
        }

        cur = node;
        node.parent = parent;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    在这里插入图片描述

    2.4 AVL树的旋转

    AVL 树在结点插入后有一个旋转的过程，为了减小树的高度，提高搜索效率
    注意：平衡因子是右子树高度 - 左子树高度

    情况一：看这样一颗二叉树：

    在这里插入图片描述

    新节点插入较高左子树的左侧：

    在这里插入图片描述

    自下向上一边调整平衡因子，一边寻找超出范围的平衡因子

    在这里插入图片描述

    寻找过程的代码：

    ①、由于平衡因子 bf 等于右树高度减去左树高度，所以当插入结点在 parent 右侧时，bf 增 1，反之减 1
    ②、当平衡因子为 0 证明已经完全平衡，为 1 或者 -1 证明还是可能存在不平衡的地方（继续向上检查），当平衡因子不是 0 / 1 / -1 就证明找到了不平衡的位置，按照四种不同情况分别进行旋转调整

    while(parent != null){
            if(parent.left == cur){
                parent.bf--;
            }else{
                parent.bf++;
            }

            if(parent.bf == 0){
                break;
            }else if(parent.bf == 1 || parent.bf == -1){
                cur = parent;
                parent = cur.parent;
            }else{
                if(parent.bf == 2){
                    if(cur.bf == 1){
                        
                    }else{
                        
                    }
                }else{
                    if(cur.bf == -1){
                        
                    }else{
                        
                    }
                }
                //这里旋转完就平衡了 结束循环
                break;
            }
        }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    针对情况一的处理：右单旋（parent 和 cur 平衡因子同时为负数）

    在这里插入图片描述
    在这里插入图片描述

    //右单旋的代码：
private void rotateRight(TreeNode parent) {
        TreeNode curL = parent.left;
        TreeNode curLR = curL.right;

        parent.left = curLR;
        curL.right = parent;

        if(curLR != null){
            curLR.parent = parent;
        }

        TreeNode pParent = parent.parent;
        parent.parent = curL;

        if(parent == root){
            root = curL;
            root.parent = null;
        }else {
            if(pParent.left == parent){
                pParent.left = curL;
            }else {
                pParent.right = curL;
            }
            curL.parent = pParent;
        }

        curL.bf = 0;
        parent.bf = 0;

    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    情况二：看这样一颗二叉树：

    在这里插入图片描述

    新节点插入较高右子树的右侧：

    在这里插入图片描述

    采用左单旋的方式进行调整：

    在这里插入图片描述

    在这里插入图片描述

    //左单旋代码
private void rotateLeft(TreeNode parent) {
        TreeNode curR = parent.right;
        TreeNode curRL = curR.left;

        parent.right = curRL;
        curR.left = parent;

        if(curRL != null){
            curRL.parent = parent;
        }

        TreeNode pParent = parent.parent;
        parent.parent = curR;

        if(parent == root){
            root = curR;
            root.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = curR;
            }else{
                pParent.right = curR;
            }

            curR.parent = pParent;
        }

        parent.bf = 0;
        curR.bf = 0;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    情况三、看这样一颗二叉树

    在这里插入图片描述

    新节点插入较高左子树的右侧：

    在这里插入图片描述

    使用左右双旋来进行调整：

    在这里插入图片描述

    	private void rotateLR(TreeNode parent) {
        TreeNode curL = parent.left;
        TreeNode curLR = curL.right;

        int bf = curLR.bf;

        rotateLeft(parent.left);
        rotateRight(parent);

        if(bf == 1){
            curLR.bf = 0;
            curL.bf = -1;
            parent.bf = 0;
        }else if(bf == -1){
            curL.bf = 0;
            parent.bf = 1;
            curLR.bf = 0;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    情况四、看这样一颗二叉树

    在这里插入图片描述

    新节点插入较高右子树的左侧

    在这里插入图片描述

    使用右左双旋进行调整

    在这里插入图片描述

    private void rotateRL(TreeNode parent) {
        TreeNode curR = parent.right;
        TreeNode curRL = curR.left;

        int bf = curRL.bf;

        rotateRight(parent.right);
        rotateLeft(parent);

        if(bf == 1){
            curRL.bf = 0;
            curR.bf = 0;
            parent.bf = -1;
        }else if (bf == -1){
            curR.bf = 0;
            parent.bf = 0;
            curRL.bf = 1;
        }



    }


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    2.5 AVL树的验证

    AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步

    1、二叉搜索树的中序遍历结果是一个有序的序列
    2、每个节点子树高度差的绝对值不超过1，并验证平衡因子是否正确（可能平衡因子计算错误）

    ①、先实现左根右的顺序遍历
    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);

        System.out.print(root.val + " ");

        inorder(root.right);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    ②、判断是否平衡
    private int height(TreeNode root){
        if(root == null){
            return 0;
        }

        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        return Math.max(leftHeight,rightHeight) + 1;
    }

    public boolean isBalance(TreeNode root){
        if(root == null){
            return true;
        }

        int leftH = height(root.left);
        int rightH = height(root.right);

        if(rightH - leftH != root.bf){
            System.out.println("平衡因子错误，错误位置" + root.val);
            return false;
        }

        return Math.abs(rightH - leftH) <= 1 && isBalance(root.left) && isBalance(root.right);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    ③、测试两种情况的平衡二叉树
    public class Test {
    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        int[] arr = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
        
        /*
        int[] arr = {16, 3, 7, 11, 9, 26, 18, 14, 15};
        */

        for (int j : arr) {
            avlTree.insert(j);
        }
        avlTree.inorder(avlTree.root);
        System.out.println(avlTree.isBalance(avlTree.root));
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    在这里插入图片描述

    2.6 AVL树的删除（了解）

    AVL树的删除结点了解思想即可：

    1、找到需要删除的节点
    2、按照搜索树的删除规则删除节点–参考《二叉搜索树的删除》
    3、更新平衡因子，如果出现了不平衡，进行旋转。–单旋，双旋

    2.7 AVL树性能分析

           AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

    AVL树总体代码：

    ①、实现AVL

    import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2022-07-05
 * Time: 11:37
 */
public class AVLTree {
    static class TreeNode{
        //1、结点数值
        public int val;
        //2、左结点
        public TreeNode left;
        //3、右结点
        public TreeNode right;
        //4、父亲结点
        public TreeNode parent;
        //5、左右子树高度差 —— 平衡因子
        public int bf;
        //6、提供构造方法
        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root;
    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if(root == null){
            root = node;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;

        while(cur != null){
            if(cur.val == val){
                return false;
            }else if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else {
                parent = cur;
                cur = cur.right;
            }
        }

        if(val > parent.val){
            parent.right = node;
        }else{
            parent.left = node;
        }

        cur = node;
        node.parent = parent;

        while(parent != null){
            if(parent.left == cur){
                parent.bf--;
            }else{
                parent.bf++;
            }

            if(parent.bf == 0){
                break;
            }else if(parent.bf == 1 || parent.bf == -1){
                cur = parent;
                parent = cur.parent;
            }else{
                if(parent.bf == 2){
                    if(cur.bf == 1){
                        rotateLeft(parent);
                    }else{
                        rotateRL(parent);
                    }
                }else{
                    if(cur.bf == -1){
                        rotateRight(parent);
                    }else{
                        rotateLR(parent);
                    }
                }

                break;
            }
        }
        return true;
    }

    private void rotateRL(TreeNode parent) {
        TreeNode curR = parent.right;
        TreeNode curRL = curR.left;

        int bf = curRL.bf;

        rotateRight(parent.right);
        rotateLeft(parent);

        if(bf == 1){
            curRL.bf = 0;
            curR.bf = 0;
            parent.bf = -1;
        }else if (bf == -1){
            curR.bf = 0;
            parent.bf = 0;
            curRL.bf = 1;
        }


    }

    private void rotateLR(TreeNode parent) {
        TreeNode curL = parent.left;
        TreeNode curLR = curL.right;

        int bf = curLR.bf;

        rotateLeft(parent.left);
        rotateRight(parent);

        if(bf == 1){
            curLR.bf = 0;
            curL.bf = -1;
            parent.bf = 0;
        }else if(bf == -1){
            curL.bf = 0;
            parent.bf = 1;
            curLR.bf = 0;
        }
    }

    private void rotateLeft(TreeNode parent) {
        TreeNode curR = parent.right;
        TreeNode curRL = curR.left;

        parent.right = curRL;
        curR.left = parent;

        if(curRL != null){
            curRL.parent = parent;
        }

        TreeNode pParent = parent.parent;
        parent.parent = curR;

        if(parent == root){
            root = curR;
            root.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = curR;
            }else{
                pParent.right = curR;
            }

            curR.parent = pParent;
        }

        parent.bf = 0;
        curR.bf = 0;
    }

    private void rotateRight(TreeNode parent) {
        TreeNode curL = parent.left;
        TreeNode curLR = curL.right;

        parent.left = curLR;
        curL.right = parent;

        if(curLR != null){
            curLR.parent = parent;
        }

        TreeNode pParent = parent.parent;
        parent.parent = curL;

        if(parent == root){
            root = curL;
            root.parent = null;
        }else {
            if(pParent.left == parent){
                pParent.left = curL;
            }else {
                pParent.right = curL;
            }
            curL.parent = pParent;
        }

        curL.bf = 0;
        parent.bf = 0;

    }

    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);

        System.out.print(root.val + " ");

        inorder(root.right);
    }

    private int height(TreeNode root){
        if(root == null){
            return 0;
        }

        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        return Math.max(leftHeight,rightHeight) + 1;
    }

    public boolean isBalance(TreeNode root){
        if(root == null){
            return true;
        }

        int leftH = height(root.left);
        int rightH = height(root.right);

        if(rightH - leftH != root.bf){
            System.out.println("平衡因子错误，错误位置" + root.val);
            return false;
        }

        return Math.abs(rightH - leftH) <= 1 && isBalance(root.left) && isBalance(root.right);
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235

    ②、测试代码：

    /**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2022-07-06
 * Time: 9:13
 */
public class Test {
    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        int[] arr = {16, 3, 7, 11, 9, 26, 18, 14, 15};

        for (int j : arr) {
            avlTree.insert(j);
        }
        avlTree.inorder(avlTree.root);
        System.out.println(avlTree.isBalance(avlTree.root));
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
  • 相关阅读:
    Linux内核队列queue.h
    IDEA 常用技巧
    随机森林实战案例——对天气最高温度进行预测
    【笔试题】【day10】
    Java Math.acos()方法具有什么功能呢？
    配置Tomcat修改默认ROOT路径为自己的路径
    数据准备脚本：Python Pandas OR esProc SPL？
    web 面试高频考点 —— JavaScript 篇（一）【JS的三座大山 】 变量类型和计算、原型和原型链、作用域和闭包、异步
    Redis数据类型-Hash-基本使用
    C++ Qt开发：ComboBox下拉组合框组件
  • 原文地址：https://blog.csdn.net/baiyang2001/article/details/125615710