你好赵伟

这个屌丝很懒，什么也没留下！

热门标签

【数据结构】初入数据结构中的平衡二叉搜索树(AVL树)及Java实现_给定一个2^n-1个不同的整数(1<=n<=10),构建一个平衡二叉搜索树,二叉搜索树的定义

作者：你好赵伟 | 2024-05-03 07:02:12

踩

给定一个2^n-1个不同的整数(1<=n<=10),构建一个平衡二叉搜索树,二叉搜索树的定义

初入数据结构中的平衡二叉搜索树(AVL树)

如果觉得对你有帮助，能否点个赞或关个注，以示鼓励笔者呢？！博客目录 | 先点这里

前提概念
- 什么是平衡二叉搜索树
- 平衡二叉搜索树的定义
- 平衡二叉树搜索树的作用
- 平衡二叉搜索树的实现算法
AVL树
- 什么是结点的高？
- 什么是结点的平衡因子？
- 怎么判断一棵二叉搜索树是不是AVL树？
- 什么是LL,RR,LR,RL?
- 什么是左旋，右旋
代码实践分析
- 功能
- AVLTree类定义
- AVLTree结点构造
- 判断一棵树是不是二叉搜索树
- 判断一棵树是不是平衡二叉树
- 新插入一个元素
- 删除一个元素
- 测试
完整代码
- TreeNode
- AVLTree

前提概念

什么是平衡二叉搜索树？

平衡二叉搜索树，既Self-balancing Binary Search Tree，又称为AVL树，平衡二叉树，自平衡二叉树 (之后我们就统称AVL树吧，毕竟短）

为什么又叫AVL树？

AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
因为AVL算法是最先发明的自平衡二叉搜索树算法，既是最早的平衡二叉搜索树的具体算法实现，在其他算法没有出来之前，AVL树也就称为了平衡二叉树搜索树的代名词。

简单的说，平衡二叉搜索树就是带有平衡功能的二叉搜索树

平衡二叉搜索树的定义

首先我们要区分一下平衡二叉树和平衡二叉搜索树的概念

平衡二叉树的定义

本身首先是一棵二叉树。
每个结点的左右子树的高度之差不超过1 (high <= 1) ，也可以说每个结点的平衡因子需在[-1,1]范围之内
其每一个子树均为平衡二叉树

平衡二叉搜索树的定义

本身首先是一棵二叉搜索树。
每个结点的左右子树的高度之差不超过1 (high <= 1) ，也可以说每个结点的平衡因子需在[-1,1]范围之内
其每一个子树均为平衡二叉搜索树

平衡二叉树的定义相比完全二叉树更为的宽松，只要求了每个结点的左右子树的高度之差不超过1 。而平衡二叉搜索树其实就是二叉搜索树和平衡二叉树的结合体

在这里插入图片描述

平衡二叉搜索树的作用

我们知道，对于一棵的二叉搜索树，其查找的时间复杂度是O(log2n)，所以查找效率还是很舒服的。但是在某些极端的情况下，比如在插入的序列是有序的时，二叉搜索树将退化成近似线性数据结构，既类似斜树。此时该树查询的时间复杂度将退化O(n)。此时，我们要怎么办？怎么办？

平衡二叉搜索树就派上用场了，它在二叉搜索树的基础上，加上了自平衡的功能。让二叉搜索树可以经受住各种的插入和删除，依然保持左右子树的平衡，近似完全二叉树化，让查找的时间复杂度稳定在O(log2n)。

平衡二叉搜索树的实现算法

本身平衡二叉搜索树仅仅是一个概念，既带有平衡功能的二叉搜索树。那它具体去怎么保持平衡呢？就要看它使用了那些具体的算法去实现了

平衡二叉搜索树算法 (引用至平衡二叉树 - @百度百科)

AVL算法
红黑树算法
Treap算法
伸展树算法
Size Balanced Tree算法

而我们本章节主要说的就是平衡二叉搜索树的AVL算法。 也因为AVL算法是平衡二叉树的最早具体算法实现，所以AVL树也就为了平衡二叉搜索树的代名词

AVL树

什么是结点的高？

在学习AVL树之前，我们得先来了解一下，什么是结点的高。我们知道哈，树有度和高的概念，结点有度和层级的概念，那么什么是结点的高呢？

在这里插入图片描述

从上图中，我们可以得出一个结论啊。什么是结点的高呢？就是以当前该结点为根结点的子树的高，就是当前结点的高

什么是结点的平衡因子？

平衡二叉搜索树的定义中，有一条是说二叉搜索树的每个结点的平衡因子需要满足在[-1,1]范围之内。所以当我们了解了什么是结点的高之后，我们再来了解一下什么是结点的平衡因子？

平衡因子是AVL树中为了防止二叉搜索树退化成链表而提出的概念
通过平衡因子，我们可以判断该二叉搜索树是否达到平衡，是否满足AVL树的定义

结点的平衡因子怎么去计算呢？

一个结点的平衡因子就是该结点左右孩子结点的高之差
或者说一个结点的左右子树的高之差

默认情况下，我们使用左孩子的高 - 右孩子的高 的顺序去计算结点的平衡因子

**图有错，要重新改正**
So , 结点的平衡因子可以由如下计算的得出

所以结点A的平衡因子 = 结点B平衡因子 - 结点C平衡因子 = 2
所以结点G的平衡因子 = 结点I平衡因子 - 0 = 1
所以结点I的平衡因子 = 0 - 0 = 0

怎么判断一棵二叉搜索树是不是AVL树？

首先该树的前提肯定是一个棵二叉搜索树(二叉搜索树的中序遍历必定是一个升序序列)
然后标注这个树所有结点的高度
然后计算每个结点的平衡因子
看看是否有结点的平衡因子超过了[-1,1]取值区间
只要有结点的平衡因子超过了取值范围，就不满足AVL树，而没有超过则满足AVL树

在这里插入图片描述

如上图，我们将一颗二叉搜索树的所有结点的高用红色字体标记出来，同时也算出了所有结点的平衡因子，用蓝色字体标记出来。可以看出，该二叉搜索树有两个结点的平衡因子是不再AVL树所要求的[-1,1]范围之内的，所以图中的二叉搜索树并不满足AVL树的要求

什么是LL,RR,LR,RL?

当新插入一个元素后，该树出现了不平衡现象，那么根据新插入元素与向上回溯找到的第一个不平衡结点的相对位置，可以分为如下四种情况：

LL
LL就是新插入元素是在向上回溯找到的第一个不平衡结点的左孩子的左侧的情况
RR
RR就是新插入元素是在向上回溯找到的第一个不平衡结点的右孩子的右侧的情况
LR
LR就是新插入元素是在向上回溯找到的第一个不平衡结点的左孩子的右侧的情况
RL
RR就是新插入元素是在向上回溯找到的第一个不平衡结点的右孩子的左侧的情况

在这里插入图片描述

插入和删除操作都是一样的，都面临维持平衡的情况，LL,LR,RR,RL同样满足与删除一个结点的情况。

什么是左旋，右旋？

什么是左旋，右旋？

左旋，右旋指的是对不平衡结点进行类似向左旋转和向右旋转的操作，最终让整棵二叉搜索树得以满足平衡特性
因为对不平衡结点的动作，就像将该不平衡结点进行左边旋转或右边旋转

LL,LR,RR,RL四种情况下的解决方式:

LL
对不平衡结点y进行右旋操作即可（右旋）
LR
先对不平衡结点y的左孩子x进行左旋操作，得到对结点y的LL情况，再对不平衡结点y进行右旋操作（先左旋，后右旋）
RR
对不平衡结点y进行左旋操作即可（左旋）
RL
选对不平衡结点y的右孩子x进行右旋操作，得到对结点y的RL情况，再对不平衡结点y进行左旋操作(先右旋，后左旋)

以下是一个LL情况的左旋操作，最终的到一棵满足平衡的二叉搜索树
在这里插入图片描述

以下是一个LR的情况
在这里插入图片描述

Java实践分析

功能

首先我得先说一下，我们这棵AVL树要实现一下什么功能？

主要功能：

判断该树是否是一棵二叉搜索树 | isBSTree()
判断该树是否是一棵平衡二叉树 | isBalanceTree()
新增一个元素 | add()
删除一个元素 | remove()

辅助功能：

获得结点的高 | getHeight()
获得结点的平衡因子 | getBalanceFactor
对结点进行左旋 | leftRotate()
对结点进行右旋 | rightRotate()
中序遍历 | midOrder()
寻找avl树的最小结点 | minimumWithRecursion()

另外呢，整体的代码，可以说是在之前所写的文章初入数据结构的二叉搜索树( Binary Search Tree) 的基础上改造的。所以如果想要真正的了解AVL树，还是建议先把二叉搜索树的代码实践先了解清楚

AVLTree类定义

public class AVLTree<T extends Comparable<T>> {...}
1

准确的说，这个不算是AVL树要关注的点，而是二叉搜索树需要关注的点，既二叉搜索树存储的元素必须是一个可比较的元素
所以T extends Comparable<T>

AVLTree结点构造 | `TreeNode<E>{}`

	/**
     * AVL树的结点
     * 跟其他普通的二叉树不一样
     * 结点需要一个域来记录所在的高
     *
     * @param <E>
     */
    public static class TreeNode<E> {
        /**
         * @data 数据域
         * @height 结点的高
         * @lchild,@rchild 左右孩子
         */
        public E data;
        public int height;
        public TreeNode<E> lchild, rchild;

        /**
         * 每构造一个结点，默认该结点是叶子结点
         * 所以height是1
         *
         * @param data
         */
        public TreeNode(E data) {
            this.data = data;
            this.lchild = null;
            this.rchild = null;
            this.height = 1;
        }

        ...省略hashcode(),equal(),toString()等方法
    }
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

AVL树中的结点跟平时二叉搜索树结点有个很大的不同点需要注意的是，AVL树的每个结点需要记住 结点的高 , 这个很重要，结点的高涉及到判断结点的平衡因子，而平衡因子则涉及到判断该树是否平衡，如何维护平衡等操作
结点的构造函数中，将某个结点的高默认为1。为什么呢？因为二叉搜索树中的新增结点，必定是该树的新叶子结点。而叶子结点的高必然是1，所以…

判断一棵树是否是二叉搜索树？| `isBSTree()`

如何判断的思路：

二叉树搜索树的中序遍历的序列，一定是一个升序序列

我们就利用上面的二叉搜索树的特点，去完成这个一个判断

 /**
     * 判断该二叉树是否是一棵二叉搜索树
     * 是则True, 否则False
     *
     * @return
     */
    public boolean isBSTree() {
        ArrayList<T> datas = new ArrayList<>();
        midOrder(this.rootNode, datas);
        System.out.println(datas);

        // 判断datas是否是一个升序list
        for (int i = 1; i < datas.size(); i++) {
            if (datas.get(i - 1).compareTo(datas.get(i)) > 0) {
                return false;
            }
        }
        return true;

    }

    /**
     * 为isBSTree()方法服务的私有中序遍历方法
     * 二叉搜索树的中序遍历，恰好就是整棵树所有元素的升序组合
     *
     * @param root
     * @param datas
     */
    private void midOrder(TreeNode<T> root, ArrayList<T> datas) {
        if (root == null) {
            return;
        }

        midOrder(root.lchild, datas);
        datas.add(root.data);
        midOrder(root.rchild, datas);

    }
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

判断一棵树是否是平衡二叉树？ | `isBalanceTree()`

如何判断的思路：

从树的根结点开始向下全递归判断每个结点的平衡因子是否在取值范围内[-1,1], 是则平衡，反之不平衡

	/**
     * 判断该树是否是一棵平衡二叉搜索树
     * 简而言之就是该树是否平衡
     *
     * @return
     */
    public boolean isBalanceTree() {
        return isBalanceTree(this.rootNode);
    }

    /**
     * 判断该树是否是一棵平衡二叉树 | 递归调用
     * 从根结点向下递归，全递归，整个树的所有结点都能被递归到
     *
     * @param root
     * @return
     */
    private boolean isBalanceTree(TreeNode<T> root) {

        /**
         * 1. 递归出口1
         * 如果是一棵空树，自然是平衡的啦
         */
        if (root == null) {
            return true;
        }

        /**
         * 2. 递归出口2，判断当前相对根结点的平衡因子是否满足平衡
         * 平衡因子是否在[-1,1]区间内，既平衡因子的绝对值是否小于等于1，不是则不满足
         */
        int balanceFactor = getBalanceFactor(root);
        //只要发现任何一个结点的平衡因子不满足，该树就不满足平衡条件
        if (Math.abs(balanceFactor) > 1) {
            return false;
        }


        /**
         * 3. 相对根结点的平衡因子满足平衡，就要看左右孩子是否满足
         */
        return isBalanceTree(root.lchild) && isBalanceTree(root.rchild);
    }
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

如果需要判断一棵树是否是AVL树，这需要该树满足是二叉搜索树且是平衡二叉树的双重条件

（重点）插入新元素 | `add()`

在AVL树中新插入一个元素，我们有三个要思考的点：

新元素插在树那个位置上
新插入的元素可能会导致原有结点的高发生变化
是否出现不平衡，怎么去维护平衡

第一个问题 好解决，只是一个二次搜索树的问题，只需要递归变量找到对应的新叶子结点位置即可。步骤也很简单

判断新元素跟所有结点数据的大小，大了就遍历右子树，小了就遍历左子树，直到找到一个合适的新叶子结点位置

第二个问题 也很好解决

因为add的过程是递归的过程，只需要每个子递归的过程中将当前所遍历到的结点的高 + 1即可

第三个问题 怎么去维持平衡的问题就要好好思考一下了

首先找到第一个不平衡的结点位置
根据新插入元素与新元素向上回溯找到的第一个不平衡结点的位置，分为LL,LR,RR,RL四种情况
分别采用右旋，先左后右旋，左旋，先右后左旋的方式解决上面四种情况即可

怎么用代码去判断什么时候属于LL,LR,RR,RL的那种情况？

先判断新元素在不平衡结点的左孩子侧，还是右孩子侧，解决第一个方向

我们的代码中：当前结点平衡因子 = 左孩子高 - 右孩子高
不平衡结点的平衡因子 >1，说明左子树更高，新元素在不平衡结点的左孩子侧(L)
不平衡结点的平衡因子< -1 ，说明右子树更高，新元素在不平衡结点的右孩子侧(R)

当确定了新元素在不平衡结点的左孩子或右孩子侧时, 再判断新结点在不平衡结点的孩子结点的左侧还是右侧，解决第二个方向

不平衡结点的左(L)孩子(balanceFactor > 1)

(LL)balanceFactor > 1 && lchild.balanceFactor >= 0 ; 当孩子结点的左子树更高或左右平衡时，属于LL
(LR)balanceFactor > 1 && lchild.balanceFactor < 0 ；当孩子结点的左子树更矮时，属于LR

不平衡结点的右(R)孩子(balanceFactor < -1)

(RR)balanceFactor < - 1 && rchild.balanceFactor <= 0 ;当孩子结点的右子树更高或左右平衡时，属于RR
(RL)balanceFactor < - 1 && rchild.balanceFactor > 0 ;当孩子结点的右子树更矮时，属于RL

LL,LR,RR,RL四种情况分别怎么维持平衡？

这个问题可以在上面小结的什么是左旋，右旋中看到解答

我们代码中定义了两个方法leftRotate，rightRotate就分别对应概念中的左旋右旋，整个代码的思路过程就是：

新插入一个结点，递归遍历寻找到可插入的新叶子结点位置
插入新元素之后，需要更新插入链中所有结点的高度
同时坚持插入新元素会，有没有造成不平衡现象
如果有，这从插入结点中回溯，找到第一个不平衡的结点
判断不平衡结点处理LL,LR,RR,RL那四种情况，分别采用左旋，右旋或组合旋去维持平衡

/**
     * 向AVL树添加一个元素 | 递归
     * 1. 统一操作，不用对根结点进行额外的判断
     * 2. 代码更简洁，只是相对不好理解
     *
     * @param data
     */
    public void add(T data) {
        this.rootNode = add(this.rootNode, data);
    }

    /**
     * 向根结点为root的AVL树添加元素 | 改进型，不需要对根结点做特殊处理
     * 1. 递归退出条件是，当递归到空树时，那么新元素就是该空树的根结点,因为我们知道二叉搜索树的新增元素必然发生在叶子结点，既新增元素必然是作为新叶子结点存在
     * 2. 每一次的递归返回的结点，都是用于给上层做关联的，即递归是找到新元素要存储的位置，然后将新元素结点返回给父结点去操作。parent.child = newNode
     * 3. 因为AVL树需要记录结点的高，而自己的子树多了一层结点，很有可能会导致以自己为根结点的树的高发生变化，所以要几时修改结点的高
     *
     * @param root
     * @param data
     * @return
     */
    private TreeNode<T> add(TreeNode<T> root, T data) {


        //递归退出条件，只要相对根结点为null，即代表目前我是一棵空树，新增元素就要作为我这棵空树的根结点，直接返回新结点给上层操作
        //新增元素必然是作为新叶子结点存在,所以这是递归的唯一出口
        if (root == null) {
            return new TreeNode<>(data);
        }

        /**
         * 1.寻找新元素可插入的位置，并插入
         */
        //不允许存在相同元素
        if (data.compareTo(root.data) == 0) {
            throw new RuntimeException("二叉搜索树所存储的元素不允许相等，已存在");
            //如果新增元素小于当前子树的根结点的值，左递归
        } else if (data.compareTo(root.data) < 0) {
            root.lchild = add(root.lchild, data);
            //如果新增元素大于当前子树的根结点的值，右递归
        } else if (data.compareTo(root.data) > 0) {
            root.rchild = add(root.rchild, data);
        }

        /**
         * 2. 更新相对根结点的Height
         * 因为是递归函数，所以所有的相对根结点的高就在此得到更新
         * 只有新元素作为叶子结点除外，叶子结点的高都是在结点构造函数中赋予的
         */
        root.height = 1 + Math.max(getHeight(root.lchild), getHeight(root.rchild));


        /**
         * 3. 计算当前相对根结点的平衡因子
         * avl树结点平衡因子的绝对值需要小于等于1
         */
        int balanceFactor = getBalanceFactor(root);
        if (Math.abs(balanceFactor) > 1) {
            System.out.println("不满足平衡二叉树: " + root.data + " factor: " + balanceFactor);
        }

        /**
         * 4. 平衡维护
         * (1) LL需要右旋
         * (2) RR需要左旋
         * (3) LR需要对不平衡结点的左孩子进行左旋，再对不平衡结点进行右旋
         * (4) RL需要对不平衡结点的右孩子进行右旋，再对不平衡结点进行左旋
         *
         * 注意一个情况，LL和RR情况下，孩子的平衡因子判断时带有等号的，既孩子平衡因子等于0时，是归于LL或RR的
         */

        //如果当前结点的平衡因子大于1，且左孩子的平衡因子大于等于0，则属于LL情况，需要右旋
        if (balanceFactor > 1 && getBalanceFactor(root.lchild) >= 0){
            //将右旋后的相对根结点返回给上一层做关联
            return rightRotate(root);
        }
        //如果当前结点的平衡因子大于1，且左孩子的平衡因子小于0，这属于LR情况，需要先左旋，再右旋
        if (balanceFactor > 1 && getBalanceFactor(root.lchild) < 0){
            root.lchild = leftRotate(root.lchild);
            return rightRotate(root);
        }
        //如果当前结点的平衡因子小于-1，且右孩子的平衡因子小于等于0，这属于RR情况，需要左旋
        if (balanceFactor < -1 && getBalanceFactor(root.rchild) <= 0 ){
            return leftRotate(root);
        }
        //如果当前结点的平衡因子小于1，且右孩子的平衡因子大于0，这属于RL情况，需要先右旋，再左旋
        if (balanceFactor < -1 && getBalanceFactor(root.rchild) > 0){
            root.rchild = rightRotate(root.rchild);
            return leftRotate(root);
        }

        //将当前子树的根结点返回出去，让上层做关联
        return root;
    }
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

AVL树相比普通二叉搜索树的add()方法而言，只多了两个部分，一就是对结点的高的更新，二就是需要维持平衡
重点要理解左旋，右旋，以及如何根据平衡因子判断不平衡现象属于四种情况（LL,LR,RR,RL）中的哪一种

（重点）删除一个元素 | `remove()`

我个人感觉呀，删除一个元素可比新增一个元素更复杂，但不是站在AVL树维持平衡的角度，而是二叉搜索树的删除元素操作本身就比较复杂。所以我建议在看AVL树之前，还是要非常熟悉二叉搜索树的删除操作（传送门 => 初入数据结构的二叉搜索树( Binary Search Tree) ）

看之前，首先要知道当删除某个结点，我们需要用什么结点去替换删除结点的位置？

删除结点没有左右孩子
相当于删除结点是叶子结点，直接删除，没有任何影响
删除结点没有左孩子 | 只有右孩子
使用其右孩子去替代原删除结点的位置
删除结点没有右孩子 | 只有左孩子
使用其左孩子去代替原删除结点的位置
删除结点左右孩子都有
使用其前趋结点或后继结点代替删除结点的位置

那什么是前趋结点，什么是后继结点？
当删除结点左右孩子都有的时候，用于替代删除结的替代结点，可以是删除结点的后继结点, 也可以是前趋结点

后继结点是删除结点的右子树的最小值结点
前趋结点是删除结点的左子树的最大值结点

整个删除步骤大致是：

传入要删除的数据，从根结点开始递归遍历（二分查找）匹配结点
找到匹配结点之后，分为四种情况去删除
- 删除结点没有左右孩子 => 直接删除
- 删除结点没有左孩子 | 只有右孩子 => 右孩子去地阿提
- 删除结点没有右孩子 | 只有左孩子 => 左孩子去代替
- 删除结点左右孩子都有 => 我们用后继结点去代替
删除结点之后，需要更新删除链所有相关结点的高
还需要判断删除结点之后，是否发生不平衡现象
如果发生不平衡现象，就更具LL,LR,RR,RL四种情况去解决问题


	/**
     * 二叉搜索树删除目标值结点（任意结点）
     * 1. 删除结点没有孩子的情况
     * 2. 删除结点只有一个孩子的情况
     * 3. 删除结点有两个孩子的情况
     * 4. 删除结点的替代结点可以是前趋结点，也可以是后继节点，我们这里采用后继结点
     *
     * @param data
     */
    public void remove(T data) {
        this.rootNode = remove(data, this.rootNode);
    }
    
	/**
     * 二叉搜索树删除以node结点为根结点的子树的data数据结点
     *
     * @param data
     * @param node
     * @return
     */
    private TreeNode<T> remove(T data, TreeNode<T> node) {
        //如果结点为null， 直接返回null，代表没有找到目标值结点
        if (node == null) {
            return null;
        }

        /**
         * 1. 二分查找递归，目标是找到目标值结点
         * 删除目标结点
         */
        TreeNode<T> resultNode;
        if (data.compareTo(node.data) < 0) {
            node.lchild = remove(data, node.lchild);
            resultNode = node;
        } else if (data.compareTo(node.data) > 0) {
            node.rchild = remove(data, node.rchild);
            resultNode = node;
        } else { //data == node.data，找到删除结点

            //如果删除结点没有孩子，直接删除，爽快，其实这个步骤可以省略，因为下面的做法已经囊括了，但是为了直观
            if (node.lchild == null && node.rchild == null) {
                resultNode = null;
            } else if (node.lchild == null) {
                //如果删除结点没有左孩子 | 等价删除结点只有右孩子
                TreeNode<T> rNode = node.rchild;
                node.rchild = null;
                resultNode = rNode;
            } else if (node.rchild == null) {
                //如果删除结点没有右孩子 | 等价删除结点只有左孩子
                TreeNode<T> lNode = node.lchild;
                node.lchild = null;
                resultNode = lNode;
            } else {

                /**
                 * 如果删除结点左右孩子都不为空，Hibbard Deletion
                 * 1. 找到删除结点右子树的最小值结点（删除结点的后继结点） minimum(node.rchild) ，作为删除结点的替代结点
                 * 2. 删除结点的后继结点的左右指针替换成删除结点的左右指针的指向
                 * 3. 剔除删除结点
                 * 4. 返回替代结点给上层，重新关联
                 */
                //获得后继结点，将后继结点作为删除结点的代替结点
                TreeNode<T> successorNode = minimumWithRecursion(node.rchild);


                /**这里有三个步骤：
                 * 1. 删除后继结点在原先的位置
                 * 2. 更新后继结点的右指针指向
                 * 3. 更新后续结点的左指针指向
                 * 这里要注意一个顺序，既要先删除后继结点在原子树的位置，再更新后继结点的左右指针,否则会导致错误
                 * 既后继结点被更新了左右孩子，但被删除了，又被继承到自己的后继结点，这是不应该的
                 * 因为这里的更新指针指向和删除后续结点在原先位置的代码是一句话，所以要保证更新右指针在更新左指针前面
                 */
                //(1) 后继结点的右指针指向删除结点的右指针
                //相当于removeMin, 因为后继结点要从删除结点的右子树最小结点位置移动到当前删除结点的位置，先删除，再移动
                //为什么要替换二叉搜索树中的removeMin？因为二叉搜索树的removeMin没有维护平衡，不想写这么多代码，所以使用remove来重用
                successorNode.rchild = remove(successorNode.data, node.rchild);

                //(2) 后继结点的左指针指向删除结点的左指针
                successorNode.lchild = node.lchild;

                //释放删除结点的左右孩子
                node.lchild = null;
                node.rchild = null;

                resultNode = successorNode;
            }
        }

        /**
         * 2. 更新相对根结点的Height
         * 因为是递归函数，所以所有的相对根结点的高就在此得到更新
         * 只有新元素作为叶子结点除外，叶子结点的高都是在结点构造函数中赋予的
         */
        if (resultNode == null) {
            return null;
        }
        resultNode.height = 1 + Math.max(getHeight(resultNode.lchild), getHeight(resultNode.rchild));


        /**
         * 3. 计算当前相对根结点的平衡因子
         * avl树结点平衡因子的绝对值需要小于等于1
         */
        int balanceFactor = getBalanceFactor(resultNode);

        /**
         * 4. 平衡维护
         * (1) LL需要右旋
         * (2) RR需要左旋
         * (3) LR需要对不平衡结点的左孩子进行左旋，再对不平衡结点进行右旋
         * (4) RL需要对不平衡结点的右孩子进行右旋，再对不平衡结点进行左旋
         *
         * 注意一个情况，LL和RR情况下，孩子的平衡因子判断时带有等号的，既孩子平衡因子等于0时，是归于LL或RR的
         */

        //如果当前结点的平衡因子大于1，且左孩子的平衡因子大于等于0，则属于LL情况，需要右旋
        if (balanceFactor > 1 && getBalanceFactor(resultNode.lchild) >= 0) {
            //将右旋后的相对根结点返回给上一层做关联
            return rightRotate(resultNode);
        }
        //如果当前结点的平衡因子大于1，且左孩子的平衡因子小于0，这属于LR情况，需要先左旋，再右旋
        if (balanceFactor > 1 && getBalanceFactor(resultNode.lchild) < 0) {
            resultNode.lchild = leftRotate(resultNode.lchild);
            return rightRotate(resultNode);
        }
        //如果当前结点的平衡因子小于-1，且右孩子的平衡因子小于等于0，这属于RR情况，需要左旋
        if (balanceFactor < -1 && getBalanceFactor(resultNode.rchild) <= 0) {
            return leftRotate(resultNode);
        }
        //如果当前结点的平衡因子小于1，且右孩子的平衡因子大于0，这属于RL情况，需要先右旋，再左旋
        if (balanceFactor < -1 && getBalanceFactor(resultNode.rchild) > 0) {
            resultNode.rchild = rightRotate(resultNode.rchild);
            return leftRotate(resultNode);
        }
        return resultNode;
    }
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

要多注意删除结点存在左右孩子的情况，我们这里相对之前的二叉搜索树代码写法，没有使用removeMin方法，而是重用remove，本质是因为懒。但这也会造成一定的坑，所以删除结点必须要在更新左右指针之前
删除结点的维护平衡操作跟插入结点的维护平衡操作是一模一样的，所以基本上就是copy过来的。

最后测试一下咯 | `test()`

 public static void main(String[] args) {
        AVLTree<Integer> avlTree = new AVLTree<>(12);
        List<Integer> list = Stream.generate(() -> new Random().nextInt(100)).limit(100).collect(Collectors.toList());
      /*  List<Integer> list = Stream.of(21, 23, 18, 78, 58, 26, 10, 58, 99, 1).collect(Collectors.toList());*/
        System.out.println(list);
        list.forEach(num -> {
            avlTree.add(num);
            if (!avlTree.isBSTree() && !avlTree.isBalanceTree()) {
                System.out.println("avlTree 添加数值 :" + num + " 时出现了不平衡，树高为: " + avlTree.height());
            }
        });

       list.forEach(num -> {
            avlTree.remove(num);
            if (!avlTree.isBSTree() && !avlTree.isBalanceTree()) {
                System.out.println("avlTree 删除数值 :" + num + " 时出现了不平衡，树高为: " + avlTree.height());
            }
        });
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

主要测试add一个序列，然后再把AVLTree中的元素全部删除，看看插入和删除操作之后是否能满足AVLTree的定义，结果是通过了

完整代码

TreeNode

  /**
     * AVL树的结点
     * 跟其他普通的二叉树不一样
     * 结点需要一个域来记录所在的高
     *
     * @param <E>
     */
    public static class TreeNode<E> {
        /**
         * @data 数据域
         * @height 结点的高
         * @lchild,@rchild 左右孩子
         */
        public E data;
        public int height;
        public TreeNode<E> lchild, rchild;

        /**
         * 每构造一个结点，默认该结点是叶子结点
         * 所以height是1
         *
         * @param data
         */
        public TreeNode(E data) {
            this.data = data;
            this.lchild = null;
            this.rchild = null;
            this.height = 1;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof TreeNode)) return false;

            TreeNode<?> treeNode = (TreeNode<?>) o;

            if (data != null ? !data.equals(treeNode.data) : treeNode.data != null) return false;
            if (lchild != null ? !lchild.equals(treeNode.lchild) : treeNode.lchild != null) return false;
            return rchild != null ? rchild.equals(treeNode.rchild) : treeNode.rchild == null;
        }

        @Override
        public int hashCode() {
            int result = data != null ? data.hashCode() : 0;
            result = 31 * result + (lchild != null ? lchild.hashCode() : 0);
            result = 31 * result + (rchild != null ? rchild.hashCode() : 0);
            return result;
        }
    }
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

AVLTree

/**
 * 自平衡二叉搜索树 | AVL树
 * 1. 判断该树是否是一棵二叉搜索树
 * 2. 判断该树是否是一棵平衡二叉搜索树
 * 3.
 */
public class AVLTree<T extends Comparable<T>> {

  
    /**
     * AVL树根结点
     */
    private TreeNode<T> rootNode;


    public AVLTree(T data) {
        this.rootNode = new TreeNode<>(data);
    }

    /**
     * 获得以node为根结点的子树的高
     * 既获得node结点的高
     *
     * @param root
     * @return
     */
    private int getHeight(TreeNode root) {
        //当相对根结点为空，所以该子树是空树，结点的高自然为0
        if (root == null) {
            return 0;
        }
        return root.height;
    }


    /**
     * 求树的高
     *
     * @return
     */
    public int height() {
        return depthForTree(rootNode);
    }

    /**
     * 求某棵子树的深度
     *
     * @param root
     * @return
     */
    private int depthForTree(TreeNode<T> root) {
        if (root == null) {
            return 0;
        }
        return Math.max(depthForTree(root.lchild), depthForTree(root.rchild)) + 1;
    }

    /**
     * 二叉树的查询 | 递归
     *
     * @param data
     * @return
     */
    public boolean contains(T data) {
        return contains(this.rootNode, data);
    }

    /**
     * 查询以root为根结点的子树
     *
     * @param root
     * @param data
     * @return
     */
    private boolean contains(TreeNode<T> root, T data) {

        //空树是肯定不含有目标元素，直接返回false , 递归退出条件
        if (root == null) {
            return false;
        }

        //如果相等，说明找到了，直接返回true
        if (data.compareTo(root.data) == 0) {
            return true;

            //如果当前子树的根结点不是目标元素，判断是当前根结点的左边还是右边
        } else if (data.compareTo(root.data) < 0) {
            return contains(root.lchild, data);
        } else {
            return contains(root.rchild, data);
        }
    }

    /**
     * 获得某个结点平衡因子
     * 结点的平衡因子等于左右子树高之差,或者说结点的平衡因子等于左右孩子结点的高之差
     * <p>
     * 实现是： 当前结点平衡因子 = 左孩子的高 - 右孩子的高
     *
     * @param root
     * @return
     */
    private int getBalanceFactor(TreeNode root) {
        //当相对根结点为空，则代表空树，该结点不存在，自然没有平衡因子或认为是0
        if (root == null) {
            return 0;
        }
        return getHeight(root.lchild) - getHeight(root.rchild);

    }


    /**
     * 判断该二叉树是否是一棵二叉搜索树
     * 是则True, 否则False
     *
     * @return
     */
    public boolean isBSTree() {
        ArrayList<T> datas = new ArrayList<>();
        midOrder(this.rootNode, datas);


        // 判断datas是否是一个升序list
        for (int i = 1; i < datas.size(); i++) {
            if (datas.get(i - 1).compareTo(datas.get(i)) > 0) {
                return false;
            }
        }
        return true;

    }

    /**
     * 为isBSTree()方法服务的私有中序遍历方法
     * 二叉搜索树的中序遍历，恰好就是整棵树所有元素的升序组合
     *
     * @param root
     * @param datas
     */
    private void midOrder(TreeNode<T> root, ArrayList<T> datas) {
        if (root == null) {
            return;
        }

        midOrder(root.lchild, datas);
        datas.add(root.data);
        midOrder(root.rchild, datas);

    }

    /**
     * 判断该树是否是一棵平衡二叉树
     * 简而言之就是该树是否平衡
     *
     * @return
     */
    public boolean isBalanceTree() {
        return isBalanceTree(this.rootNode);
    }

    /**
     * 判断该树是否是一棵平衡二叉树 | 递归调用
     * 从根结点向下递归，全递归，整个树的所有结点都能被递归到
     *
     * @param root
     * @return
     */
    private boolean isBalanceTree(TreeNode<T> root) {

        /**
         * 1. 递归出口1
         * 如果是一棵空树，自然是平衡的啦
         */
        if (root == null) {
            return true;
        }

        /**
         * 2. 递归出口2，判断当前相对根结点的平衡因子是否满足平衡
         * 平衡因子是否在[-1,1]区间内，既平衡因子的绝对值是否小于等于1，不是则不满足
         */
        int balanceFactor = getBalanceFactor(root);
        //只要发现任何一个结点的平衡因子不满足，该树就不满足平衡条件
        if (Math.abs(balanceFactor) > 1) {
            return false;
        }


        /**
         * 3. 相对根结点的平衡因子满足平衡，就要看左右孩子是否满足
         */
        return isBalanceTree(root.lchild) && isBalanceTree(root.rchild);
    }


    /**
     * 向AVL树添加一个元素 | 递归
     * 1. 统一操作，不用对根结点进行额外的判断
     * 2. 代码更简洁，只是相对不好理解
     *
     * @param data
     */
    public void add(T data) {
        this.rootNode = add(this.rootNode, data);
    }

    /**
     * 向根结点为root的AVL树添加元素 | 改进型，不需要对根结点做特殊处理
     * 1. 递归退出条件是，当递归到空树时，那么新元素就是该空树的根结点,因为我们知道二叉搜索树的新增元素必然发生在叶子结点，既新增元素必然是作为新叶子结点存在
     * 2. 每一次的递归返回的结点，都是用于给上层做关联的，即递归是找到新元素要存储的位置，然后将新元素结点返回给父结点去操作。parent.child = newNode
     * 3. 因为AVL树需要记录结点的高，而自己的子树多了一层结点，很有可能会导致以自己为根结点的树的高发生变化，所以要几时修改结点的高
     *
     * @param root
     * @param data
     * @return
     */
    private TreeNode<T> add(TreeNode<T> root, T data) {


        //递归退出条件，只要相对根结点为null，即代表目前我是一棵空树，新增元素就要作为我这棵空树的根结点，直接返回新结点给上层操作
        //新增元素必然是作为新叶子结点存在,所以这是递归的唯一出口
        if (root == null) {
            return new TreeNode<>(data);
        }

        /**
         * 1.寻找新元素可插入的位置，并插入
         */
        //二叉搜索树所存储的元素不允许相等，已存在
        if (data.compareTo(root.data) == 0) {
            root.data = data;
            //如果新增元素小于当前子树的根结点的值，左递归
        } else if (data.compareTo(root.data) < 0) {
            root.lchild = add(root.lchild, data);
            //如果新增元素大于当前子树的根结点的值，右递归
        } else if (data.compareTo(root.data) > 0) {
            root.rchild = add(root.rchild, data);
        }

        /**
         * 2. 更新相对根结点的Height
         * 因为是递归函数，所以所有的相对根结点的高就在此得到更新
         * 只有新元素作为叶子结点除外，叶子结点的高都是在结点构造函数中赋予的
         */
        root.height = 1 + Math.max(getHeight(root.lchild), getHeight(root.rchild));


        /**
         * 3. 计算当前相对根结点的平衡因子
         * avl树结点平衡因子的绝对值需要小于等于1
         */
        int balanceFactor = getBalanceFactor(root);
        /*if (Math.abs(balanceFactor) > 1) {
            System.out.println("不满足平衡二叉树: " + root.data + " factor: " + balanceFactor);
        }*/

        /**
         * 4. 平衡维护
         * (1) LL需要右旋
         * (2) RR需要左旋
         * (3) LR需要对不平衡结点的左孩子进行左旋，再对不平衡结点进行右旋
         * (4) RL需要对不平衡结点的右孩子进行右旋，再对不平衡结点进行左旋
         *
         * 注意一个情况，LL和RR情况下，孩子的平衡因子判断时带有等号的，既孩子平衡因子等于0时，是归于LL或RR的
         */

        //如果当前结点的平衡因子大于1，且左孩子的平衡因子大于等于0，则属于LL情况，需要右旋
        if (balanceFactor > 1 && getBalanceFactor(root.lchild) >= 0) {
            //将右旋后的相对根结点返回给上一层做关联
            return rightRotate(root);
        }
        //如果当前结点的平衡因子大于1，且左孩子的平衡因子小于0，这属于LR情况，需要先左旋，再右旋
        if (balanceFactor > 1 && getBalanceFactor(root.lchild) < 0) {
            root.lchild = leftRotate(root.lchild);
            return rightRotate(root);
        }
        //如果当前结点的平衡因子小于-1，且右孩子的平衡因子小于等于0，这属于RR情况，需要左旋
        if (balanceFactor < -1 && getBalanceFactor(root.rchild) <= 0) {
            return leftRotate(root);
        }
        //如果当前结点的平衡因子小于1，且右孩子的平衡因子大于0，这属于RL情况，需要先右旋，再左旋
        if (balanceFactor < -1 && getBalanceFactor(root.rchild) > 0) {
            root.rchild = rightRotate(root.rchild);
            return leftRotate(root);
        }

        //将当前子树的根结点返回出去，让上层做关联
        return root;
    }


    /**
     * 二叉搜索树删除目标值结点（任意结点）
     * 1. 删除结点没有孩子的情况
     * 2. 删除结点只有一个孩子的情况
     * 3. 删除结点有两个孩子的情况
     * 4. 删除结点的替代结点可以是前趋结点，也可以是后继节点，我们这里采用后继结点
     *
     * @param data
     */
    public void remove(T data) {
        this.rootNode = remove(data, this.rootNode);
    }

    /**
     * 二叉搜索树删除以node结点为根结点的子树的data数据结点
     *
     * @param data
     * @param node
     * @return
     */
    private TreeNode<T> remove(T data, TreeNode<T> node) {
        //如果结点为null， 直接返回null，代表没有找到目标值结点
        if (node == null) {
            return null;
        }

        /**
         * 1. 二分查找递归，目标是找到目标值结点
         * 删除目标结点
         */
        TreeNode<T> resultNode;
        if (data.compareTo(node.data) < 0) {
            node.lchild = remove(data, node.lchild);
            resultNode = node;
        } else if (data.compareTo(node.data) > 0) {
            node.rchild = remove(data, node.rchild);
            resultNode = node;
        } else { //data == node.data，找到删除结点

            //如果删除结点没有孩子，直接删除，爽快，其实这个步骤可以省略，因为下面的做法已经囊括了，但是为了直观
            if (node.lchild == null && node.rchild == null) {
                resultNode = null;
            } else if (node.lchild == null) {
                //如果删除结点没有左孩子 | 等价删除结点只有右孩子
                TreeNode<T> rNode = node.rchild;
                node.rchild = null;
                resultNode = rNode;
            } else if (node.rchild == null) {
                //如果删除结点没有右孩子 | 等价删除结点只有左孩子
                TreeNode<T> lNode = node.lchild;
                node.lchild = null;
                resultNode = lNode;
            } else {

                /**
                 * 如果删除结点左右孩子都不为空，Hibbard Deletion
                 * 1. 找到删除结点右子树的最小值结点（删除结点的后继结点） minimum(node.rchild) ，作为删除结点的替代结点
                 * 2. 删除结点的后继结点的左右指针替换成删除结点的左右指针的指向
                 * 3. 剔除删除结点
                 * 4. 返回替代结点给上层，重新关联
                 */
                //获得后继结点，将后继结点作为删除结点的代替结点
                TreeNode<T> successorNode = minimumWithRecursion(node.rchild);


                /**这里有三个步骤：
                 * 1. 删除后继结点在原先的位置
                 * 2. 更新后继结点的右指针指向
                 * 3. 更新后续结点的左指针指向
                 * 这里要注意一个顺序，既要先删除后继结点在原子树的位置，再更新后继结点的左右指针,否则会导致错误
                 * 既后继结点被更新了左右孩子，但被删除了，又被继承到自己的后继结点，这是不应该的
                 * 因为这里的更新指针指向和删除后续结点在原先位置的代码是一句话，所以要保证更新右指针在更新左指针前面
                 */
                //(1) 后继结点的右指针指向删除结点的右指针
                //相当于removeMin, 因为后继结点要从删除结点的右子树最小结点位置移动到当前删除结点的位置，先删除，再移动
                //为什么要替换二叉搜索树中的removeMin？因为二叉搜索树的removeMin没有维护平衡，不想写这么多代码，所以使用remove来重用
                successorNode.rchild = remove(successorNode.data, node.rchild);

                //(2) 后继结点的左指针指向删除结点的左指针
                successorNode.lchild = node.lchild;

                //释放删除结点的左右孩子
                node.lchild = null;
                node.rchild = null;

                resultNode = successorNode;
            }
        }

        /**
         * 2. 更新相对根结点的Height
         * 因为是递归函数，所以所有的相对根结点的高就在此得到更新
         * 只有新元素作为叶子结点除外，叶子结点的高都是在结点构造函数中赋予的
         */
        if (resultNode == null) {
            return null;
        }
        resultNode.height = 1 + Math.max(getHeight(resultNode.lchild), getHeight(resultNode.rchild));


        /**
         * 3. 计算当前相对根结点的平衡因子
         * avl树结点平衡因子的绝对值需要小于等于1
         */
        int balanceFactor = getBalanceFactor(resultNode);

        /**
         * 4. 平衡维护
         * (1) LL需要右旋
         * (2) RR需要左旋
         * (3) LR需要对不平衡结点的左孩子进行左旋，再对不平衡结点进行右旋
         * (4) RL需要对不平衡结点的右孩子进行右旋，再对不平衡结点进行左旋
         *
         * 注意一个情况，LL和RR情况下，孩子的平衡因子判断时带有等号的，既孩子平衡因子等于0时，是归于LL或RR的
         */

        //如果当前结点的平衡因子大于1，且左孩子的平衡因子大于等于0，则属于LL情况，需要右旋
        if (balanceFactor > 1 && getBalanceFactor(resultNode.lchild) >= 0) {
            //将右旋后的相对根结点返回给上一层做关联
            return rightRotate(resultNode);
        }
        //如果当前结点的平衡因子大于1，且左孩子的平衡因子小于0，这属于LR情况，需要先左旋，再右旋
        if (balanceFactor > 1 && getBalanceFactor(resultNode.lchild) < 0) {
            resultNode.lchild = leftRotate(resultNode.lchild);
            return rightRotate(resultNode);
        }
        //如果当前结点的平衡因子小于-1，且右孩子的平衡因子小于等于0，这属于RR情况，需要左旋
        if (balanceFactor < -1 && getBalanceFactor(resultNode.rchild) <= 0) {
            return leftRotate(resultNode);
        }
        //如果当前结点的平衡因子小于1，且右孩子的平衡因子大于0，这属于RL情况，需要先右旋，再左旋
        if (balanceFactor < -1 && getBalanceFactor(resultNode.rchild) > 0) {
            resultNode.rchild = rightRotate(resultNode.rchild);
            return leftRotate(resultNode);
        }
        return resultNode;
    }


    /**
     * 查找二叉搜索树的最小值 | 递归
     *
     * @return
     */
    public T minimumWithRecursion() {
        if (this.rootNode == null) {
            return null;
        }

        return minimumWithRecursion(this.rootNode).data;

    }

    /**
     * 查找二叉树搜索树的最小值 | 递归
     * 1. 每一步就是查找左子树的最小值是什么，如果没有左子树，则最小值就是当前结点所代表的值
     *
     * @param node
     * @return
     */
    private TreeNode<T> minimumWithRecursion(TreeNode<T> node) {
        if (node.lchild == null) {
            return node;
        }

        return minimumWithRecursion(node.lchild);

    }


    /**
     * 维护平衡 | LL下的右旋
     * 对不平衡结点y进行右旋操作，返回新的根结点x
     * <p>
     * y                                          x
     * / \                                       /   \
     * x   T4          y结点向右旋转             z     y
     * / \             --------------->          / \   / \
     * z   T3                                    T1 T2 T3 T4
     * / \
     * T1  T2
     *
     * @param y
     * @return
     */
    private TreeNode<T> rightRotate(TreeNode<T> y) {
        /**
         * 1. 进行右旋操作
         * (1) 先记录x结点和T3结点（记录了T3就不需要再判断x是否有右结点了,也方便理解）
         * (2) 将T3变成y结点的左孩子
         * (3) 将y变成y的右孩子
         */
        TreeNode<T> x = y.lchild;
        TreeNode<T> t3 = x.rchild;
        y.lchild = t3;
        x.rchild = y;

        /**
         * 2. 更新y和x的高度值
         * 先更新y，再更新x ; 因为旋转后，x是y的父结点，x高度的更新依赖y高度的更新
         */
        y.height = Math.max(getHeight(y.lchild), getHeight(y.rchild)) + 1;
        x.height = Math.max(getHeight(x.lchild), getHeight(x.rchild)) + 1;

        //返回新的根结点（RR下，新的根结点就是原不平衡结点的左孩子）
        return x;
    }


    /**
     * 维护平衡 | RR下的左旋
     * 对不平衡结点y进行向左旋转操作，返回旋转后新的根结点x
     * y                             x
     * /  \                          /   \
     * T1   x      向左旋转 (y)       y     z
     * / \   - - - - - - - ->   / \   / \
     * T2  z                     T1 T2 T3 T4
     * / \
     * T3 T4
     *
     * @param y 不平衡结点
     * @return
     */
    private TreeNode<T> leftRotate(TreeNode<T> y) {
        /**
         * 1. 进行右旋操作
         * (1) 先记录x结点和T2结点
         * (2) 将T2变成y结点的右孩子
         * (3) 将y变成x的左孩子
         */
        TreeNode<T> x = y.rchild;
        TreeNode<T> t2 = x.lchild;
        y.rchild = t2;
        x.lchild = y;

        /**
         * 2. 更新y和x的高度值
         * 先更新y，再更新x ; 因为旋转后，x是y的父结点，x高度的更新依赖y高度的更新
         */
        y.height = Math.max(getHeight(y.lchild), getHeight(y.rchild)) + 1;
        x.height = Math.max(getHeight(x.lchild), getHeight(x.rchild)) + 1;

        //返回新的根结点（LL下，新的根结点就是原不平衡结点的右孩子）
        return x;
    }


    public static void main(String[] args) {
        AVLTree<Integer> avlTree = new AVLTree<>(12);
        List<Integer> list = Stream.generate(() -> new Random().nextInt(100)).limit(100).collect(Collectors.toList());
      /*  List<Integer> list = Stream.of(21, 23, 18, 78, 58, 26, 10, 58, 99, 1).collect(Collectors.toList());*/
        System.out.println(list);
        list.forEach(num -> {
            avlTree.add(num);
            if (!avlTree.isBSTree() && !avlTree.isBalanceTree()) {
                System.out.println("avlTree 添加数值 :" + num + " 时出现了不平衡，树高为: " + avlTree.height());
            }
        });

       list.forEach(num -> {
            avlTree.remove(num);
            if (!avlTree.isBSTree() && !avlTree.isBalanceTree()) {
                System.out.println("avlTree 删除数值 :" + num + " 时出现了不平衡，树高为: " + avlTree.height());
            }
        });

    }

}

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
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562

参考资料

RongleXie/Play-with-Data-Structures-Ronglexie - @作者：RongleXie
如果觉得对你有帮助，能否点个赞或关个注，以示鼓励笔者呢？！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/528387?site

【数据结构】初入数据结构中的平衡二叉搜索树(AVL树)及Java实现_给定一个2^n-1个不同的整数(1<=n<=10),构建一个平衡二叉搜索树,二叉搜索树的定义

初入数据结构中的平衡二叉搜索树(AVL树)

前提概念

什么是平衡二叉搜索树？

平衡二叉搜索树的定义

平衡二叉搜索树的作用

平衡二叉搜索树的实现算法

AVL树

什么是结点的高？

什么是结点的平衡因子？

怎么判断一棵二叉搜索树是不是AVL树？

什么是LL,RR,LR,RL?

什么是左旋，右旋？

Java实践分析

功能

AVLTree类定义

AVLTree结点构造 | TreeNode<E>{}

判断一棵树是否是二叉搜索树？| isBSTree()

判断一棵树是否是平衡二叉树？ | isBalanceTree()

（重点）插入新元素 | add()

（重点）删除一个元素 | remove()

最后测试一下咯 | test()

完整代码

TreeNode

AVLTree

相关博文

参考资料

AVLTree结点构造 | `TreeNode<E>{}`

判断一棵树是否是二叉搜索树？| `isBSTree()`

判断一棵树是否是平衡二叉树？ | `isBalanceTree()`

（重点）插入新元素 | `add()`

（重点）删除一个元素 | `remove()`

最后测试一下咯 | `test()`