Java数据结构与算法解析(六)——AVL树

末蓝、 2022-05-29 06:13 141阅读 0赞

#                           Java数据结构与算法解析(六)——AVL树 #

之前我们说过普通二叉查找树的删除算法会使得左子树比右子树深，因为我们总是用右子树的一个来代替删除的节点。会造成二叉查找树，严重的不平衡。

# AVL树简介 #

而AVL树就是解决普通二叉查找树弊端的方法，他是带有平衡条件的二叉查找树，这个平衡条件必须容易保持，而且它保证树的深度必须是O(logN).

AVL树是高度平衡的而二叉树。它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。

![这里写图片描述][SouthEast]

上面的两张图片，左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3，而以8为根节点的树的高度是1)。

# AVL树的实现 #

## 1.节点 ##

// AVL树的节点(内部类)
        class AVLTreeNode<T extends Comparable<T>> { 
            T element;                // 值
            int height;         // 高度
            AVLTreeNode<T> left;    // 左孩子
            AVLTreeNode<T> right;    // 右孩子
    
            public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
                this.element = key;
                this.left = left;
                this.right = right;
                this.height = 0;
            }
        }
    
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15

AVLTree是AVL树对应的类，而AVLTreeNode是AVL树节点，它是AVLTree的内部类。AVLTree包含了AVL树的根节点，AVL树的基本操作也定义在AVL树中。AVLTreeNode包括的几个组成对象:   
(1) key – 是关键字，是用来对AVL树的节点进行排序的。   
(2) left – 是左孩子。   
(3) right – 是右孩子。   
(4) height – 是高度。

## 2.树的高度 ##

/* * 获取树的高度 */
    private int height(AVLTreeNode<T> tree) {
        if (tree != null)
            return tree.height;
    
        return 0;
    }
    
    public int height() {
        return height(mRoot);
    }
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13

有的地方将”空二叉树的高度是-1”，这里我们采用另一种定义：树的高度为最大层次。即空的二叉树的高度是0，非空树的高度等于它的最大层次(根的层次为1，根的子节点为第2层，依次类推)。

## 3.旋转 ##

如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态：LL(左左)，LR(左右)，RR(右右)和RL(右左)。

![这里写图片描述][SouthEast 1]

上图中的4棵树都是”失去平衡的AVL树”，从左往右的情况依次是：LL、LR、RL、RR。除了上面的情况之外，还有其它的失去平衡的AVL树，如下图：   
![这里写图片描述][SouthEast 2]

(1) LL：LeftLeft，也称为”左左”。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致”根的左子树的高度”比”根的右子树的高度”大2，导致AVL树失去了平衡。   
例如，在上面LL情况中，由于”根节点(8)的左子树(4)的左子树(2)还有非空子节点”，而”根节点(8)的右子树(12)没有子节点”；导致”根节点(8)的左子树(4)高度”比”根节点(8)的右子树(12)”高2。

(2) LR：LeftRight，也称为”左右”。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致”根的左子树的高度”比”根的右子树的高度”大2，导致AVL树失去了平衡。   
例如，在上面LR情况中，由于”根节点(8)的左子树(4)的左子树(6)还有非空子节点”，而”根节点(8)的右子树(12)没有子节点”；导致”根节点(8)的左子树(4)高度”比”根节点(8)的右子树(12)”高2。

(3) RL：RightLeft，称为”右左”。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。   
例如，在上面RL情况中，由于”根节点(8)的右子树(12)的左子树(10)还有非空子节点”，而”根节点(8)的左子树(4)没有子节点”；导致”根节点(8)的右子树(12)高度”比”根节点(8)的左子树(4)”高2。

(4) RR：RightRight，称为”右右”。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。   
例如，在上面RR情况中，由于”根节点(8)的右子树(12)的右子树(14)还有非空子节点”，而”根节点(8)的左子树(4)没有子节点”；导致”根节点(8)的右子树(12)高度”比”根节点(8)的左子树(4)”高2。

如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。AVL失去平衡之后，可以通过旋转使其恢复平衡，下面分别介绍”LL(左左)，LR(左右)，RR(右右)和RL(右左)”这4种情况对应的旋转方法。

LL的旋转   
LL失去平衡的情况，可以通过一次旋转让AVL树恢复平衡。如下图：   
![这里写图片描述][SouthEast 3]

图中左边是旋转之前的树，右边是旋转之后的树。从中可以发现，旋转之后的树又变成了AVL树，而且该旋转只需要一次即可完成。   
对于LL旋转，你可以这样理解为：LL旋转是围绕”失去平衡的AVL根节点”进行的，也就是节点k2；而且由于是LL情况，即左左情况，就用手抓着”左孩子，即k1”使劲摇。将k1变成根节点，k2变成k1的右子树，”k1的右子树”变成”k2的左子树”。

LL的旋转代码

/** * LL：左左对应的情况(左单旋转)。 * @param k2 * @return 旋转后的根节点 */
        private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {
            AVLTreeNode<T> k1;
    
            k1 = k2.left;
            k2.left = k1.right;
            k1.right = k2;
    
            k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
            k1.height = Math.max(height(k1.left), k2.height) + 1;
    
            return k1;
        }
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17

RR的旋转   
理解了LL之后，RR就相当容易理解了。RR是与LL对称的情况！RR恢复平衡的旋转方法如下：   
![这里写图片描述][SouthEast 4]

图中左边是旋转之前的树，右边是旋转之后的树。RR旋转也只需要一次即可完成。

private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {
            AVLTreeNode<T> k2;
    
            k2 = k1.right;
            k1.right = k2.left;
            k2.left = k1;
    
            k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
            k2.height = Math.max(height(k2.right), k1.height) + 1;
    
            return k2;
        }
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12

LR的旋转   
LR失去平衡的情况，需要经过两次旋转才能让AVL树恢复平衡。   
![这里写图片描述][SouthEast 5]

第一次旋转是围绕”k1”进行的”RR旋转”，第二次是围绕”k3”进行的”LL旋转”。

LR的旋转代码

/** * LR：左右对应的情况(左双旋转)。 * @param k3 * @return 旋转后的根节点 */
        private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {
            k3.left = rightRightRotation(k3.left);
    
            return leftLeftRotation(k3);
        }
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10

RL的旋转   
RL是与LR的对称情况！RL恢复平衡的旋转方法如下：   
![这里写图片描述][SouthEast 6]

第一次旋转是围绕”k3”进行的”LL旋转”，第二次是围绕”k1”进行的”RR旋转”。

RL的旋转代码

/** * RL：右左对应的情况(右双旋转)。 * @param k1 * @return 旋转后的根节点 */
        private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {
            k1.right = leftLeftRotation(k1.right);
    
            return rightRightRotation(k1);
        }
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10

## 4.插入 ##

public void insert(T key) {
            mRoot = insert(mRoot, key);
        }
    
        /** * 将结点插入到AVL树中，并返回根节点 * * @param tree AVL树的根结点 * @param key 插入的结点的键值 * @return 根节点 */
        private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
            if (tree == null) {
                // 新建节点
                return tree = new AVLTreeNode<T>(key, null, null);
    
            }
    
            int cmp = key.compareTo(tree.element);
            if (cmp < 0) {
        // 将key插入到"tree的左子树"的情况
                tree.left = insert(tree.left, key);
    
            } else if (cmp > 0) { // 将key插入到"tree的右子树"的情况
                tree.right = insert(tree.right, key);
            }
    
            return balance(tree);
        }
    
    
      
       
        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

插入节点后，可能会使AVL树失去平衡，通过balance()方法进行相应的调节。

private static final int ALLOWED_IMBALANCE = 1;
    
        private AVLTreeNode<T> balance(AVLTreeNode<T> tree) {
            if (tree == null) {
                return tree;
            }
            // 插入节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.left) - height(tree.right) > ALLOWED_IMBALANCE) {
    
                if (height(tree.left.left) >= height(tree.left.right)) {
                    leftLeftRotation(tree);
                } else {
                    leftRightRotation(tree);
                }
            } else if (height(tree.right) - height(tree.left) > ALLOWED_IMBALANCE) {
                if (height(tree.right.right) >= height(tree.right.left)) {
                    rightRightRotation(tree);
                } else {
                    rightLeftRotation(tree);
                }
            }
            tree.height = Math.max( height(tree.left), height(tree.right)) + 1;
    
            return tree;
        }
      
       
        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

## 5.删除 ##

public void remove(T key) {
            AVLTreeNode<T> z;
    
            mRoot = remove(mRoot, z);
        }
    
        /** * 删除结点(z)，返回根节点 * * @param tree AVL树的根结点 * @param z 待删除的结点 * @return 根节点 */
        private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {
            if (tree == null)
                return tree;
    
            int cmp = z.element.compareTo(tree.element);
            if (cmp > 0) {
                tree.right = remove(tree.right, z);
            } else if (cmp < 0) {
                tree.left = remove(tree.left, z);
            } else if (tree.left != null && tree.right != null) {
                tree.element = findMin(tree.right).element;
                tree.right = remove(tree.element, tree.right);
            } else {
                tree = (tree.left != null) ? tree.left : tree.right;
            }
            return balance(tree);
        }
    
        private AVLTreeNode<T> findMin(AVLTreeNode<T> node) {
            if (node != null) {
                while (node.left != null) {
                    node = node.left;
                }
            }
            return node;
        }
    
        public AVLTreeNode<T> remove(T t, AVLTreeNode<T> node) {
            if (node == null) {
                return node;
            }
            int compareResult = t.compareTo(node.element);
            if (compareResult > 0) {
                node.right = remove(t, node.right);
            } else if (compareResult < 0) {
                node.left = remove(t, node.left);
            } else if (node.left != null && node.right != null) {
                node.element = findMin(node.right).element;
                node.right = remove(node.element, node.right);
            } else {
                node = (node.left != null) ? node.left : node.right;
            }
            return node;
    
        }
      
       
        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

删除操作就是在原来查找二叉树的基础上，每一次删除都调用balance()方法对AVL树进行再平衡。

完整的实现代码如下：

public class AVLTree<T extends Comparable<T>> { 
    
        private AVLTreeNode<T> mRoot;    // 根结点
    
        // AVL树的节点(内部类)
        class AVLTreeNode<T extends Comparable<T>> { 
            T element;                // 值
            int height;         // 高度
            AVLTreeNode<T> left;    // 左孩子
            AVLTreeNode<T> right;    // 右孩子
    
            public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
                this.element = key;
                this.left = left;
                this.right = right;
                this.height = 0;
            }
        }
    
        /* * 获取树的高度 */
        private int height(AVLTreeNode<T> tree) {
            if (tree != null)
                return tree.height;
    
            return 0;
        }
    
        public int height() {
            return height(mRoot);
        }
    
        /* * LL：左左对应的情况(左单旋转)。 * * 返回值：旋转后的根节点 */
    
        /** * LL：左左对应的情况(左单旋转)。 * * @param k2 * @return 旋转后的根节点 */
        private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {
            AVLTreeNode<T> k1;
    
            k1 = k2.left;
            k2.left = k1.right;
            k1.right = k2;
    
            k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
            k1.height = Math.max(height(k1.left), k2.height) + 1;
    
            return k1;
        }
    
        /** * 右右对应的情况(右单旋转)。 * * @param k1 * @return 旋转后的根节点 */
        private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {
            AVLTreeNode<T> k2;
    
            k2 = k1.right;
            k1.right = k2.left;
            k2.left = k1;
    
            k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
            k2.height = Math.max(height(k2.right), k1.height) + 1;
    
            return k2;
        }
    
    
        /** * LR：左右对应的情况(左双旋转)。 * * @param k3 * @return 旋转后的根节点 */
        private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {
            k3.left = rightRightRotation(k3.left);
    
            return leftLeftRotation(k3);
        }
    
        /** * RL：右左对应的情况(右双旋转)。 * * @param k1 * @return 旋转后的根节点 */
        private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {
            k1.right = leftLeftRotation(k1.right);
    
            return rightRightRotation(k1);
        }
    
    
        public void insert(T key) {
            mRoot = insert(mRoot, key);
        }
    
        /** * 将结点插入到AVL树中，并返回根节点 * * @param tree AVL树的根结点 * @param key 插入的结点的键值 * @return 根节点 */
        private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
            if (tree == null) {
                // 新建节点
                return tree = new AVLTreeNode<T>(key, null, null);
    
            }
    
            int cmp = key.compareTo(tree.element);
            if (cmp < 0) {
        // 将key插入到"tree的左子树"的情况
                tree.left = insert(tree.left, key);
    
            } else if (cmp > 0) { // 将key插入到"tree的右子树"的情况
                tree.right = insert(tree.right, key);
            }
    
            return balance(tree);
        }
    
    
        private static final int ALLOWED_IMBALANCE = 1;
    
        private AVLTreeNode<T> balance(AVLTreeNode<T> tree) {
            if (tree == null) {
                return tree;
            }
            // 插入节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.left) - height(tree.right) > ALLOWED_IMBALANCE) {
    
                if (height(tree.left.left) >= height(tree.left.right)) {
                    leftLeftRotation(tree);
                } else {
                    leftRightRotation(tree);
                }
            } else if (height(tree.right) - height(tree.left) > ALLOWED_IMBALANCE) {
                if (height(tree.right.right) >= height(tree.right.left)) {
                    rightRightRotation(tree);
                } else {
                    rightLeftRotation(tree);
                }
            }
            tree.height = Math.max(height(tree.left), height(tree.right)) + 1;
    
            return tree;
        }
    
        public void remove(T key) {
            AVLTreeNode<T> z;
    
            if ((z = search(mRoot, key)) != null)
                mRoot = remove(mRoot, z);
        }
    
        /* * (递归实现)查找"AVL树x"中键值为key的节点 */
        private AVLTreeNode<T> search(AVLTreeNode<T> x, T key) {
            if (x == null)
                return x;
    
            int cmp = key.compareTo(x.element);
            if (cmp < 0)
                return search(x.left, key);
            else if (cmp > 0)
                return search(x.right, key);
            else
                return x;
        }
    
        public AVLTreeNode<T> search(T key) {
            return search(mRoot, key);
        }
    
        /** * 删除结点(z)，返回根节点 * * @param tree AVL树的根结点 * @param z 待删除的结点 * @return 根节点 */
        private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {
            if (tree == null)
                return tree;
    
            int cmp = z.element.compareTo(tree.element);
            if (cmp > 0) {
                tree.right = remove(tree.right, z);
            } else if (cmp < 0) {
                tree.left = remove(tree.left, z);
            } else if (tree.left != null && tree.right != null) {
                tree.element = findMin(tree.right).element;
                tree.right = remove(tree.element, tree.right);
            } else {
                tree = (tree.left != null) ? tree.left : tree.right;
            }
            return balance(tree);
        }
    
        private AVLTreeNode<T> findMin(AVLTreeNode<T> node) {
            if (node != null) {
                while (node.left != null) {
                    node = node.left;
                }
            }
            return node;
        }
    
        public AVLTreeNode<T> remove(T t, AVLTreeNode<T> node) {
            if (node == null) {
                return node;
            }
            int compareResult = t.compareTo(node.element);
            if (compareResult > 0) {
                node.right = remove(t, node.right);
            } else if (compareResult < 0) {
                node.left = remove(t, node.left);
            } else if (node.left != null && node.right != null) {
                node.element = findMin(node.right).element;
                node.right = remove(node.element, node.right);
            } else {
                node = (node.left != null) ? node.left : node.right;
            }
            return node;
    
        }
    
        /* * 打印"二叉查找树" * * key -- 节点的键值 * direction -- 0，表示该节点是根节点; * -1，表示该节点是它的父结点的左孩子; * 1，表示该节点是它的父结点的右孩子。 */
        private void print(AVLTreeNode<T> tree, T key, int direction) {
            if(tree != null) {
                if(direction==0)    // tree是根节点
                    System.out.printf("%2d is root\n", tree.element, key);
                else                // tree是分支节点
                    System.out.printf("%2d is %2d's %6s child\n", tree.element, key, direction==1?"right" : "left");
    
                print(tree.left, tree.element, -1);
                print(tree.right,tree.element,  1);
            }
        }
    
        public void print() {
            if (mRoot != null)
                print(mRoot, mRoot.element, 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
        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
        236
        237
        238
        239
        240
        241
        242
        243
        244
        245
        246
        247
        248
        249
        250
        251
        252
        253
        254
        255
        256
        257
        258
        259
        260
        261
        262
        263
        264
        265

## AVL树的测试程序 ##

public class AVLTreeTest {
        private static int arr[] = {
        3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};
    
        public static void main(String[] args) {
            int i;
            AVLTree<Integer> tree = new AVLTree<Integer>();
    
            System.out.printf("== 依次添加: ");
            for (i = 0; i < arr.length; i++) { 
                System.out.printf("%d ", arr[i]);
                tree.insert(arr[i]);
            }
            System.out.printf("\n== 前序遍历: ");
            tree.preOrder();
    
            System.out.printf("\n== 中序遍历: ");
            tree.inOrder();
    
            System.out.printf("\n== 后序遍历: ");
            tree.postOrder();
            System.out.printf("\n");
    
            System.out.printf("== 高度: %d\n", tree.height());
            System.out.printf("== 树的详细信息: \n");
            tree.print();
    
            i = 6;
            System.out.printf("\n== 删除根节点: %d", i);
            tree.remove(i);
    
            System.out.printf("\n== 高度: %d", tree.height());
            System.out.printf("\n== 中序遍历: ");
            tree.inOrder();
            System.out.printf("\n== 树的详细信息: \n");
            tree.print();
        }
    }
      
       
        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

## AVL树测试程序流程进行分析 ##

1.  新建AVL树
2.  依次添加”3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9” 到AVL树中。   
    2.01 添加3,2   
    添加3,2都不会破坏AVL树的平衡性。   
    ![这里写图片描述][SouthEast 7]   
    2.02 添加1   
    添加1之后，AVL树失去平衡(LL)，此时需要对AVL树进行旋转(LL旋转)。旋转过程如下：   
    ![这里写图片描述][SouthEast 8]   
    2.03 添加4   
    添加4不会破坏AVL树的平衡性。   
    ![这里写图片描述][SouthEast 9]   
    2.04 添加5   
    添加5之后，AVL树失去平衡(RR)，此时需要对AVL树进行旋转(RR旋转)。旋转过程如下：   
    ![这里写图片描述][SouthEast 10]  
    2.05 添加6   
    添加6之后，AVL树失去平衡(RR)，此时需要对AVL树进行旋转(RR旋转)。旋转过程如下：   
    ![这里写图片描述][SouthEast 11]  
    2.06 添加7   
    添加7之后，AVL树失去平衡(RR)，此时需要对AVL树进行旋转(RR旋转)。旋转过程如下：   
    ![这里写图片描述][SouthEast 12]  
    2.07 添加16   
    添加16不会破坏AVL树的平衡性。   
    ![这里写图片描述][SouthEast 13]  
    2.08 添加15   
    添加15之后，AVL树失去平衡(RR)，此时需要对AVL树进行旋转(RR旋转)。旋转过程如下：   
    ![这里写图片描述][SouthEast 14]  
    2.09 添加14   
    添加14之后，AVL树失去平衡(RL)，此时需要对AVL树进行旋转(RL旋转)。旋转过程如下：   
    ![这里写图片描述][SouthEast 15]  
    2.10 添加13   
    添加13之后，AVL树失去平衡(RR)，此时需要对AVL树进行旋转(RR旋转)。旋转过程如下：   
    ![这里写图片描述][SouthEast 16]  
    2.11 添加12   
    添加12之后，AVL树失去平衡(LL)，此时需要对AVL树进行旋转(LL旋转)。旋转过程如下：   
    ![这里写图片描述][SouthEast 17]  
    2.12 添加11   
    添加11之后，AVL树失去平衡(LL)，此时需要对AVL树进行旋转(LL旋转)。旋转过程如下：   
    ![这里写图片描述][SouthEast 18]  
    2.13 添加10   
    添加10之后，AVL树失去平衡(LL)，此时需要对AVL树进行旋转(LL旋转)。旋转过程如下：   
    ![这里写图片描述][SouthEast 19]  
    2.14 添加8   
    添加8不会破坏AVL树的平衡性。   
    ![这里写图片描述][SouthEast 20]  
    2.15 添加9   
    但是添加9之后，AVL树失去平衡(LR)，此时需要对AVL树进行旋转(LR旋转)。旋转过程如下：   
    ![这里写图片描述][SouthEast 21]

[SouthEast]: /images/20220529/fa0aec32495140e3bbe0a5ddf132309d.png
[SouthEast 1]: /images/20220529/85e299341ae24ee98cafc5ed05234a2f.png
[SouthEast 2]: /images/20220529/388349016ef84f90bd025078a3cc751c.png
[SouthEast 3]: /images/20220529/4956d06690a241fda65406051c06e790.png
[SouthEast 4]: /images/20220529/3c289e3584344c24b7aaedb4a41ef587.png
[SouthEast 5]: /images/20220529/10469086f93646b3ae56610428bbab1a.png
[SouthEast 6]: /images/20220529/7304632ca8a84116a175cc253bf98ed9.png
[SouthEast 7]: /images/20220529/ff80c4bbb5604e2bb8340226ff7c5b21.png
[SouthEast 8]: /images/20220529/50ea9d09d79a4fffad49efcab7aebe0f.png
[SouthEast 9]: /images/20220529/37fffa5c108c4509a8eeff308e14127d.png
[SouthEast 10]: /images/20220529/5154c1cdcac64f4a992893366baaf418.png
[SouthEast 11]: /images/20220529/d18d3b06634a4d9a81df9f7ec5b69c11.png
[SouthEast 12]: /images/20220529/c10bf26b62464efa8b64340a9fc32218.png
[SouthEast 13]: /images/20220529/c522e6d1d5214c239520324c4423e684.png
[SouthEast 14]: /images/20220529/1444a46afdc743ab8638244090b618c8.png
[SouthEast 15]: /images/20220529/d8c2493989d1477aba3d3d6e7d3d1444.png
[SouthEast 16]: /images/20220529/767e5b929e5c4af09b4bc9e15ae193ef.png
[SouthEast 17]: /images/20220529/7b18292f38f94862a9c8640bc3e4eae3.png
[SouthEast 18]: /images/20220529/cfe900e3f37347ca882c6cb51871bed1.png
[SouthEast 19]: /images/20220529/e4338038aa934d1da65d276b5154ccb6.png
[SouthEast 20]: /images/20220529/7abc563a6da1419b9ee7ed11169011cf.png
[SouthEast 21]: /images/20220529/6352e153a20f485c968129e3df01f04b.png