数据结构与算法分析：（十六）平衡二叉树

╰半橙微兮° 2023-03-13 12:29 27阅读 0赞

## 一、前言 ##

前面我们讲了二叉树以及二叉查找树，没有看的可以点击下面的链接看一下：

[数据结构与算法分析：（十四） 二叉树][Link 1]

[数据结构与算法分析：（十五） 二叉查找树][Link 2]

看完前两篇，今天的平衡二叉树就如鱼得水一般了。下面我们就进入正题了。

`平衡二叉树`也叫`AVL`(Adelson Velskii 和 Landis 三人的缩写)，AVL树的出现就是为了解决前面二叉查找树退化成链表导致时间复杂度为 O(n)。AVL树是高度平衡的而二叉树，必须保证树的深度是 O( log ⁡ n \\log n logn)。它的特点是：`AVL树中任何节点的两个子树的高度最大差别为1`。

我们来看下面三张我画的图你就明白了。

![在这里插入图片描述][20200513203012892.png]

左边是一棵坏的二叉树，只要求在根节点平衡是不够的。  
中间的符合任何节点的两个子树的高度最大差别为1。  
右边则相差了2了，不满足平衡二叉树的特点。

## 二、AVL的实现 ##

**1、节点的定义**

public class AVLTree<T extends Comparable<T>> { 
    
        private AVLNode<T> root; // 根结点
    
        class AVLNode<T extends Comparable<T>> { 
            T key; // 关键字(键值)
            int height; // 高度
            AVLNode<T> left; // 左孩子
            AVLNode<T> right; // 右孩子
    
            public AVLNode(T key, AVLNode<T> left, AVLNode<T> right) { 
                this.key = key;
                this.height = 0;
                this.left = left;
                this.right = right;
            }
        }
        ...
    }

`AVLTree`是`AVL`树对应的类，而`AVLNode`是`AVL`树节点，它是`AVLTree`的`内部类`，也可以单独新建`AVLNode`类。`AVLTree`包含了AVL树的根节点，AVL树的基本操作也定义在AVL树中。树中有四个属性`key`、`height`、`left`以及`right`，注释都写的很清楚了，我这里就不详细说了哈。

**2、树的高度**

/** * 获取树的高度 * @param tree * @return */
    private int height(AVLNode<T> tree) { 
        if (tree != null) return tree.height;
        return 0;
    }
    
    public int height() { 
        return height(root);
    }

**3、旋转**

我们接下来来介绍下AVL树中的难点，也就是旋转。为啥有旋转这个概念呢？

我们都知道，如果我们在AVL树中进行插入或者删除节点，这样会使得从插入点或删除点到根节点的路径上的节点的平衡可能被改变，因为只有这些节点的子树可能发生变化。我们将指出如何在第一个这样的节点(即最深的节点)重新平衡这棵树，并证明这一重新平衡保证整个树满足AVL性质。

我们把必须重新平衡的节点叫做 `α`。由于任意节点最多有两个儿子，因此出现高度不平衡就需要 `α` 点的两棵子树的高度差2。容易看出，这种不平衡可能出现在下面的四种情况中：

(1)、对 `α` 的左儿子的左子树进行一次插入。  
(2)、对 `α` 的左儿子的右子树进行一次插入。  
(3)、对 `α` 的右儿子的左子树进行一次插入。  
(4)、对 `α` 的右儿子的右子树进行一次插入。

情形(1)和(4)是关于`α` 点的镜像对称，而(2)和(3)是关于`α` 点的镜像对称。因此，理论上只有两种情况，从编程角度上来看还是四种情形。

第一种情况是插入发生在"`外边`"的情况(`即左-左或右-右的情况`)，该情况通过对树的一次`单旋转`(single rotation)而完成调整。第二种情况是插入发生在`"外边`"的情况(`即左-左或右-右的情况`)，该情况通过稍复杂的`双旋转`(double rotation)而完成调整。

是不是有点抽象？没关系，下面我们用图来表示下，你就会明白了。

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

![在这里插入图片描述][2020051321174246.png]  
上面的两张图都是为了便于理解，而列举的关于"失去平衡的AVL树"的例子。总的来说，AVL树失去平衡时的情况一定是`LL、LR、RL、RR`这4种之一，它们都由各自的定义：

(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。

**3.1、LL的旋转**

LL失去平衡的情况，可以通过一次旋转让AVL树恢复平衡。如下图：

![在这里插入图片描述][20200513212221956.png]

图中左边是旋转之前的树，右边是旋转之后的树。从中可以发现，旋转之后的树又变成了AVL树，而且该旋转只需要一次即可完成。

对于LL旋转，你可以这样理解为：LL旋转是围绕"失去平衡的AVL根节点"进行的，也就是节点k2；而且由于是LL情况，即左左情况，就用手抓着"左孩子，即k1"使劲摇。将k1变成根节点，k2变成k1的右子树，“k1的右子树"变成"k2的左子树”。

LL的旋转代码：

/** * LL：左左对应的情况(左单旋转)。 * @param p2 * @return 旋转后的根节点 */
    private AVLNode<T> leftLeftRotation(AVLNode<T> p2) { 
        AVLNode<T> p1;
        p1 = p2.left;
        p2.left = p1.right;
        p1.right = p2;
        p2.height = max(height(p2.left), height(p2.right)) + 1;
        p1.height = max(height(p1.left), p2.height) + 1;
        return p1;
    }

**3.2、RR的旋转**

理解了LL之后，RR就相当容易理解了。RR是与LL对称的情况！RR恢复平衡的旋转方法如下：

![在这里插入图片描述][20200513212545905.png]

RR的旋转代码：

/** * RR：右右对应的情况(右单旋转)。 * @param p1 * @return 旋转后的根节点 */
    private AVLNode<T> rightRightRotation(AVLNode<T> p1) { 
        AVLNode<T> p2;
        p2 = p1.right;
        p1.right = p2.left;
        p2.left = p1;
        p1.height = max(height(p1.left), height(p1.right)) + 1;
        p2.height = max(height(p2.right), p1.height) + 1;
        return p2;
    }

**3.3、LR的旋转**

LR失去平衡的情况，需要经过两次旋转才能让AVL树恢复平衡。如下图：

![在这里插入图片描述][20200513212725554.png]

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

LR的旋转代码：

/** * LR：左右对应的情况(左双旋转)。 * @param p3 * @return 旋转后的根节点 */
    private AVLNode<T> leftRightRotation(AVLNode<T> p3) { 
        p3.left = rightRightRotation(p3.left);
        return leftLeftRotation(p3);
    }

**3.4、RL的旋转**

RL是与LR的对称情况！RL恢复平衡的旋转方法如下：

![在这里插入图片描述][20200513213232654.png]

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

RL的旋转代码：

/** * RL：右左对应的情况(右双旋转)。 * @param p4 * @return 旋转后的根节点 */
    private AVLNode<T> rightLeftRotation(AVLNode<T> p4) { 
        p4.right = leftLeftRotation(p4.right);
        return rightRightRotation(p4);
    }

**4、插入**

插入节点的代码如下：

/** * 将结点插入到AVL树中，并返回根节点 * @param tree AVL树的根结点 * @param key 插入的结点的键值 * @return 根节点 */
    private AVLNode<T> insert(AVLNode<T> tree, T key) { 
        if (tree == null) { 
            // 新建节点
            tree = new AVLNode<>(key, null, null);
            if (tree == null) { 
                System.err.println("Create AVLNode failed!");
                return null;
            }
        } else { 
            int temp = key.compareTo(tree.key);
            if (temp < 0) {  // 应该将key插入到"tree的左子树"的情况
                tree.left = insert(tree.left, key);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.left) - height(tree.right) ==2) { 
                    if (key.compareTo(tree.left.key) < 0) { 
                        tree = leftLeftRotation(tree);
                    } else { 
                        tree = leftRightRotation(tree);
                    }
                }
            } else if (temp > 0) {  // 应该将key插入到"tree的右子树"的情况
                tree.right = insert(tree.right, key);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.right) - height(tree.left) ==2) { 
                    if (key.compareTo(tree.right.key) > 0) { 
                        tree = rightRightRotation(tree);
                    } else { 
                        tree = rightLeftRotation(tree);
                    }
                }
            } else {  // temp == 0
                System.out.println("Add failed, it is not allowed to add the same node!");
            }
        }
        tree.height = max(height(tree.left), height(tree.right)) + 1;
        return tree;
    }

**5、删除**

删除节点的代码如下：

/** * 删除结点(p)，返回根节点 * @param tree AVL树的根结点 * @param p 待删除的结点 * @return 根节点 */
    private AVLNode<T> remove(AVLNode<T> tree, AVLNode<T> p) { 
        // 根为空 或者 没有要删除的节点，直接返回null。
        if (tree == null || p == null) return null;
        int temp = p.key.compareTo(tree.key);
        if (temp < 0) {  // 待删除的节点在"tree的左子树"中
            tree.left = remove(tree.left, p);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.right) - height(tree.left) == 2) { 
                AVLNode<T> r = tree.right;
                tree = height(r.left) > height(r.right) ? rightLeftRotation(tree) : rightRightRotation(tree);
            }
        } else if (temp > 0) {  // 待删除的节点在"tree的右子树"中
            tree.right = remove(tree.right, p);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.left) - height(tree.right) == 2) { 
                AVLNode<T> l = tree.left;
                tree = height(l.right) > height(l.left) ? leftRightRotation(tree) : leftLeftRotation(tree);
            }
        } else {  // tree是对应要删除的节点。
            // tree的左右孩子都非空
            if (tree.left != null && tree.right != null) { 
                if (height(tree.left) > height(tree.right)) { 
                    /** * 如果tree的左子树比右子树高； * 则(01)找出tree的左子树中的最大节点 * (02)将该最大节点的值赋值给tree * (03)删除该最大节点 * 这类似于用"tree的左子树中最大节点"做"tree"的替身； * 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。 */
                    AVLNode<T> max = maxNode(tree.left);
                    tree.key = max.key;
                    tree.left = remove(tree.left, max);
                } else { 
                    /** * 如果tree的右子树比左子树高； * 则(01)找出tree的右子树中的最小节点 * (02)将该最小节点的值赋值给tree * (03)删除该最下节点 * 这类似于用"tree的右子树中最小节点"做"tree"的替身； * 采用这种方式的好处是：删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。 */
                    AVLNode<T> min = minNode(tree.right);
                    tree.key = min.key;
                    tree.right = remove(tree.right, min);
                }
            } else { 
                AVLNode<T> tempNode = tree;
                tree = (tree.left != null) ? tree.left : tree.right;
                tempNode = null;
            }
        }
        return tree;
    }

## 三、测试 ##

测试类代码如下：

public class AVLTreeTest { 
    
        private static int[] arr = { 20, 19, 11, 7, 19, 93, 3, 28, 90, 2, 21};
    
        public static void main(String[] args) { 
            int k;
            AVLTree<Integer> tree = new AVLTree<>();
            System.out.printf("=== 依次添加: ");
    
            for (int val : arr) { 
                System.out.printf(val + " ");
                tree.insert(val);
            }
    
            System.out.printf("\n=== 前序遍历: ");
            tree.preOrder();
    
            System.out.printf("\n=== 中序遍历: ");
            tree.inOrder();
    
            System.out.printf("\n=== 后序遍历: ");
            tree.postOrder();
    
            System.out.printf("\n=== 高度: " + tree.height());
            System.out.printf("\n=== 最小值: " + tree.minNode());
            System.out.printf("\n=== 最大值: " + tree.maxNode());
            System.out.printf("\n=== 树的详细信息: ");
            tree.print();
    
            k = 7;
            System.out.printf("\n=== 删除节点: " + k);
            tree.remove(k);
            System.out.printf("\n=== 高度: " + tree.height());
    
            System.out.printf("\n=== 中序遍历: ");
            tree.inOrder();
    
            System.out.printf("\n=== 树的详细信息: ");
            tree.print();
    
            // 销毁二叉树
            tree.destroy();
        }
    
    }

结果输出：

=== 依次添加: 20 19 11 7 19 Add failed, it is not allowed to add the same node!
    93 3 28 90 2 21 
    === 前序遍历: 19 7 3 2 11 28 20 21 93 90 
    === 中序遍历: 2 3 7 11 19 20 21 28 90 93 
    === 后序遍历: 2 3 11 7 21 20 90 93 28 19 
    === 高度: 4
    === 最小值: 2
    === 最大值: 93
    === 树的详细信息: 19 is root
     7 is 19's   left child
     3 is  7's   left child
     2 is  3's   left child
    11 is  7's  right child
    28 is 19's  right child
    20 is 28's   left child
    21 is 20's  right child
    93 is 28's  right child
    90 is 93's   left child
    
    === 删除节点: 7
    === 高度: 4
    === 中序遍历: 2 3 11 19 20 21 28 90 93 
    === 树的详细信息: 19 is root
     3 is 19's   left child
     2 is  3's   left child
    11 is  3's  right child
    28 is 19's  right child
    20 is 28's   left child
    21 is 20's  right child
    93 is 28's  right child
    90 is 93's   left child

完整代码在Github仓库，有需要的可以点击查看：[https://github.com/riemannChow/LeetCode/tree/master/src/main/java/com/algorithm/tree/avlTree][https_github.com_riemannChow_LeetCode_tree_master_src_main_java_com_algorithm_tree_avlTree]

[Link 1]: https://riemann.blog.csdn.net/article/details/105496071
[Link 2]: https://riemann.blog.csdn.net/article/details/105544241
[20200513203012892.png]: /images/20230312/28f2c02daf5549ec9ad2af70f9650410.png
[20200513211704733.png]: https://img-blog.csdnimg.cn/20200513211704733.png
[2020051321174246.png]: https://img-blog.csdnimg.cn/2020051321174246.png
[20200513212221956.png]: https://img-blog.csdnimg.cn/20200513212221956.png
[20200513212545905.png]: https://img-blog.csdnimg.cn/20200513212545905.png
[20200513212725554.png]: https://img-blog.csdnimg.cn/20200513212725554.png
[20200513213232654.png]: https://img-blog.csdnimg.cn/20200513213232654.png
[https_github.com_riemannChow_LeetCode_tree_master_src_main_java_com_algorithm_tree_avlTree]: https://github.com/riemannChow/LeetCode/tree/master/src/main/java/com/algorithm/tree/avlTree