AVL树【图示详解+代码实现】

✨前言：这篇文章会对AVL树这个较复杂的数据结构进行讲解，重点讲解了对AVL树的四种旋转操作，对于这四种旋转都做了非常详细的画图分析，并且对代码进行了实现，还有对于AVL树的验证代码及AVL树的性能分析也做了介绍.

AVL树详解

🏞️1.AVL树的概念

在前面，我们学习过二叉搜索树，虽然二叉搜索树可以缩短查找效率，但如果数据有序或接近有序二叉搜索树将退化为单边树，查找元素相当于在顺序表中查找，效率低下. 因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度**.

基于上述概念，我们可以得出：一棵AVL树，要么是空树，要么是具有以下性质的二叉搜索树：

它的左右子树均为AVL树
左右子树高度之差（简称平衡因子）的绝对值不超过1

上述图中计算平衡因子时采用公式：平衡因子 = 右子树高度 - 左子树高度

如果一棵二叉搜索树是高度平衡的，它就是AVL树. 如果它有n个节点，其高度可保持在 $O(log_2n)$ ，搜索时间复杂度 $O(log_2n)$ .

🌁2. AVL树节点的定义

AVL树节点定义：

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K, V>& val = pair<K, V>())
		: _kv(val)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}

	pair<K, V> _kv;
	int _bf;

	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在节点定义中，我们使用kv模型来存储值.

🌠3. AVL树的操作

📖3.1 AVL树的插入

注意：对于AVL树的插入，因为它是要结合AVL树的旋转的，所以在本文中，AVL树的插入和AVL树的旋转合起来才是完整的插入过程，所以这里的3.1 主要讲一下插入的大体的一个过程，具体插入的细节及代码实现都在3.2AVL树的旋转中.

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树. 那么AVL树的插入可以分为两步：

按照二叉搜索树的方式插入新节点
调整平衡因子

对于平衡因子的调整，在插入之前，所有节点的平衡因子分为三种情况：0，1，-1插入后，新插入节点可能会使它的父节点的平衡因子发生变化，有这么三种情况：

1.新插入节点的父节点（parent）的平衡因子变成0（一定是由1或-1变成0）

2.新插入节点的父节点（parent）的平衡因子变成-1/1（由0变成1或-1）

3.新插入节点的父节点的平衡因子变成2/-2，此时已经违反了平衡树的性质，需要对其进行旋转处理.

📖3.2 AVL树的旋转

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

对于图中的右单旋，它的规则如下：

对于图中的a，b，c均为抽象节点，可能不太好理解，所以我们也可以将它们设置成实际的节点来进行分析，会更加直观：

对于，图中的抽象模型，为了方便分析，我们可以将它替换成实际节点来看：

当我们通过将h设置为不同的值时，实际的AVL树就会改变，通过画出h = 0和 h = 1的图我们就已经可以分析清楚这种旋转的情况了，对于h=2、3、4........，由于光是h=2时这棵树的样子就可能有36种情况，所以这里便不再一一画出.如果读者感兴趣，可以试着自己画一画，但根据以上h=0和h=1的情况我们就已经可以分析清楚了

最终，根据我们图上所画的这种右单选的情况，我们可以按照上图写出右旋转的代码：

void RotateR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    parent->_left = subLR;
    if (subLR)
    {
        subLR->_parent = parent;
    }

    //有可能parent是一个节点的子节点
    Node* ppNode = parent->_parent;

    subL->_right = parent;
    parent->_parent = subL;

    if (ppNode)
    {
        //parent为ppNode的子节点
        if (parent == ppNode->_left)
        {
            ppNode->_left = subL;
        }
        else
        {
            ppNode->_right = subL;
        }

        subL->_parent = ppNode;
    }
    else
    {
        //parent为根结点，旋转后将subL作新的根节点
        _root = subL;
        subL->_parent == nullptr;
    }
	
    //调整平衡因子
    subL->_bf = 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
32
33
34
35
36
37
38
39
40
41

在写上述的代码时，我们有一个需要注意的地方，当我们发现当前节点的平衡因子发生错误，我们就需要将当前节点传入到RotateR右旋函数进行右单选，但是当前的节点也就是parent节点，它有可能是根结点，也可能是一个节点（在代码中我们用ppNode表示）的子节点，所以我们需要分情况讨论.

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

左单旋的旋转规则如下：

对于左单选的图示中，将抽象节点转换为实际节点进行分析在右单选中已经演示过，两者非常类似，所以这里不再花费篇幅去讲解.

我们根据左单选的旋转规则就可以写出它的代码：

void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;

    if (subRL)
    {
        subRL->_parent = parent;
    }

    Node* ppNode = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;

    if (ppNode)
    {
        if (parent == ppNode->_left)
        {
            ppNode->_left = subR;
        }
        else
        {
            ppNode->_right = subR;
        }
        subR->_parent = ppNode;
    }
    else
    {
        _root = subR;
        subR->_parent = nullptr;
    }

    subR->_bf = 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
32
33
34
35

新插入节点在较高左子树的右侧：先左单选再右单旋

对于这种左右双旋，它的旋转规则如下：

对于规则中所述的左单旋和右单旋，在文章上面均已讲解，可以参考上面.

在上图所画的节点均为抽象节点，对于这种左右双旋的情况，我们也可以将抽象节点代替成成实际节点来分析一下：

当h=0时：

当h=1时：在这里要注意，当h=1时，我们在插入新节点的时候，25的左子树和右子树均可以插入，所以就有两种情况我们先来看第一种：新节点插入在25的左子树

新节点插入在25的右子树：

我们分别分析了h=0、h=1时的情况，对左右双旋的这种情况进一步的加深理解，对于分析过程中，我们应该还会发现一个问题，那就是最终调整完之后的平衡因子调整问题：

我们发现，对上面的情况，每一棵树在插入新节点后，它们的subLR的平衡因子都各不相同，而且对应最终平衡因子需要调整的节点（parent、subL、subLR），它们调整后的值也是分为了三种情况的：

所以，由此，我们可以总结出最终的平衡因子调整规则：

当subLR = 0时：调整为subLR = 0，subL = 0，parent = 0
当subLR = -1时：调整为subLR = 0，subL = 0，parent = 1
当subLR = 1时：调整为subLR = 0，subL = -1，parent = 0

对于左右双旋的旋转规则我们已经分析完成，接下来完成它的代码：

void RotateLR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;

    RotateL(parent->_left);
    RotateR(parent);

    if (bf == 0)
    {
        parent->_bf = 0;
        subL->_bf = 0;
        subLR->_bf = 0;
    }
    else if (bf == -1)
    {
        parent->_bf = 1;
        subL->_bf = 0;
        subLR->_bf = 0;
    }
    else if (bf == 1)
    {
        parent->_bf = 0;
        subL->_bf = -1;
        subLR->_bf = 0;
    }
    else
    {
        //如果走到这里，说明在旋转之前就已经有错，直接断言
        assert(false);
    }
}
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

新节点插入到较高右子树的左侧：先右单旋再左单旋

同样的，对于右左双旋的这种情况，在插入新节点的时，也会有两个插入位置，所以也要分情况来看：

新节点插入在25的左边：

新节点插入在25的右边：

对于平衡因子的调整，上述讨论已经展现出了两种调整情况，但它和左右双旋一样，也是有三种的调整情况，所以我们需要再分析一下当h=0时的这个特殊情况：

所以，对于右左双旋的平衡因子调整，我们也可以总结出下面三种：

当subRL = 0时：调整为subRL = 0，subR = 0，parent = 0
当subRL = -1时：调整为subRL = 0，subR = 1，parent = 0
当subRL = 1时：调整为subRL = 0，subR = 0，parent = -1

由以上分析，我们可以最终得出右左双旋的代码：

void RotateRL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    
    //右左双旋
    RotateR(parent->_right);
    RotateL(parent);
    
    //根据平衡因子的调节规则调节平衡因子
    if (bf == 0)
    {
        parent->_bf = 0;
        subRL->_bf = 0;
        subR->_bf = 0;
    }
    else if (bf == -1)
    {
        parent->_bf = 0;
        subR->_bf = 1;
        subRL->_bf = 0;
    }
    else if (bf == 1)
    {
        parent->_bf = -1;
        subR->_bf = 0;
        subRL->_bf = 0;
    }
    else
    {
        //说明在旋转前就已经不平衡
        assert(false);
    }

}
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

插入的完整代码：

bool insert(const pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_bf = 0;
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return false;
        }
    }

    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }

    cur->_parent = parent;

    //更新平衡因子
    while (parent)
    {
        //如果插入在左边，父节点的平衡因子减1
        if (cur == parent->_left)
        {
            parent->_bf--;
        }
        else
        {
            //如果插入在右边，父节点的平衡因子加1
            parent->_bf++;
        }

        if (parent->_bf == 0)
        {
            //由1/-1变成0->填上了矮的那一边，整体高度不变，不需要再向上调整
            break;
        }
        else if (parent->_bf == 1 || parent->_bf == -1)
        {
            //需要继续向上调整平衡因子
            cur = parent;
            parent = parent->_parent;
        }
        else if (parent->_bf == -2 || parent->_bf == 2)
        {
            //右单旋
            if (parent->_bf == -2 && cur->_bf == -1)
            {
                RotateR(parent);
            }
            else if (parent->_bf == 2 && cur->_bf == 1)
            {
                //左单旋
                RotateL(parent);
            }
            else if (parent->_bf == -2 && cur->_bf == 1)
            {
                左右双旋
                RotateLR(parent);
            }
            else if (parent->_bf == 2 && cur->_bf == -1)
            {
                //右左双旋
                RotateRL(parent);
            }

            break;
        }
        else
        {
            //插入之前AVL树就已经不平衡了
            assert(false);
        }

    }

    return true;

}
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

📖3.3 AVL树的删除

对于AVL树的删除操作，它是要比插入稍微复杂的，但同样的，它也是在二叉搜索树的基础上引入了平衡因子这个概念，所以对于二叉搜索树的删除也是分为两步：

1.按照二叉搜索树的方式进行删除

2.调节平衡因子，对于不平衡的节点进行旋转操作

那么，在前面的二叉搜索树，我们已经分析过，对于它的删除其实也是分为3种情况：

1.待删除节点没有孩子节点

2.待删除节点最多只有一个孩子节点

3.待删除节点有两个孩子节点（这种情况下我们通过转换为删除前驱或后继节点）

所以，我们只需要再这些操作完成后加上调节平衡因子的操作即可.

我们先来看待删除节点有两个孩子节点的情况：

对于这三种情况，我们最终都是转换成了删除只有一个孩子或没有孩子的节点，那么在成功删除节点后，会对节点的祖先造成影响，这个时候就需要我们去调节，其实删除的过程就是插入的一个逆过程，比如你给左边删除节点，站在删除的角度，也可以看作是给右边插入新节点，所以我们在判断是否需要进行旋转时，依旧可以使用删除时分析的那些需要旋转的情况.

一共有下面这四种：

基于以上的分析，我们得出AVL树删除的代码：

Node* _remove(Node* node, const K& val)
{
    if (node == nullptr)
    {
        return nullptr;
    }

    if (node->_kv.first > val)
    {
        node->_left = _remove(node->_left, val);

        if (abs(node->_bf) > 1)
        {
            if (Depth(node->_right->_right) >= Depth(node->_right->_left))
            {
                // 右孩子的右子树太高
                RotateL(node);
            }
            else
            {
                // 右孩子的左子树太高
                RotateRL(node);
            }
        }
    }
    else if (node->_kv.first < val)
    {
        node->_right = _remove(node->_right, val);

        // 右子树删除节点，可能导致左子树太高
        if (abs(node->_bf) > 1)
        {
            if (Depth(node->_left->_left) >= Depth(node->_left->_right))
            {
                // 左孩子的左子树太高
                RotateR(node);
            }
            else
            {
                // 左孩子的右子树太高
                RotateLR(node);
            }
        }
    }
    else
    {
        if (node->_left != nullptr && node->_right != nullptr)
        {
            if (Depth(node->_left) >= Depth(node->_right))
            {
                Node* prev = node->_left;
                while (prev->_right)
                    prev = prev->_right;
                node->_kv.first = prev->_kv.first;
                node->_left = _remove(node->_left, prev->_kv.first);
            }
            else
            {
                Node* post = node->_right;
                while (post->_left)
                    post = post->_left;
                node->_kv.first = post->_kv.first;
                node->_right = _remove(node->_right, post->_kv.first);
            }
        }
        else
        {
            //最多有一个孩子
            if (node->_left != nullptr)
            {
                Node* left = node->_left;
                delete node;
                return left;
            }
            else if (node->_right != nullptr)
            {
                Node* right = node->_right;
                delete node;
                return right;
            }
            else
            {
                //没有孩子
                return nullptr;
            }
        }
    }

    node->_bf = Depth(node->_right) - Depth(node->_left);

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

📖3.4 AVL树的验证

那么当我们写好了一棵AVL树之后，我们怎样知道它是一棵AVL树呢？我们可以采用以下方式验证：

bool _IsBalanceTree(Node* root)
{
    // 空树也是AVL树
    if (nullptr == root)
        return true;

    // 计算root节点的平衡因子：即root左右子树的高度差
    int leftHeight = Depth(root->_left);
    int rightHeight = Depth(root->_right);
    int diff = rightHeight - leftHeight;

    // 如果计算出的平衡因子与root的平衡因子不相等，或者
    // root平衡因子的绝对值超过1，则一定不是AVL树
    if (abs(diff) >= 2)
    {
        cout << root->_kv.first << "节点平衡因子异常" << endl;
        return false;
    }

    if (diff != root->_bf)
    {
        cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
        return false;
    }

    // pRoot的左和右如果都是AVL树，则该树一定是AVL树
    return _IsBalanceTree(root->_left)
        && _IsBalanceTree(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

//对AVL树进行测试的代码,AVL树完整代码在本文末尾
#include
#include "AVLTree.h"
using namespace std;

int main()
{
	AVLTree<int, int> avl;
	for (int i = 1; i <= 100; ++i)
	{
		avl.insert(make_pair(i, i));
	}

	avl.remove(23);
	avl.remove(57);

	//对AVL树中序遍历，也应该是有序的
	avl.InOrder();
	cout << endl;

	if (avl.IsBalanceTree())
	{
		cout << "是AVL树" << endl;
	}
	else
	{
		cout << "不是AVL树" << endl;
	}


	return 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

运行结果：
在这里插入图片描述

🌌4. AVL树的性能

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

AVL树完整代码：

#pragma once
#include
#include
#include
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K, V>& kv = pair<K, V>())
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}

	pair<K, V> _kv;
	int _bf;

	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_bf = 0;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		//更新平衡因子
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				//由1/-1变成0->填上了矮的那一边，高度不变
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == -2 || parent->_bf == 2)
			{
				//右单旋
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}

				break;
			}
			else
			{
				//插入之前AVL树就已经不平衡了
				assert(false);
			}

		}

		return true;

	}

	void remove(const K& val)
	{
		_root = _remove(_root, val);
	}

	void InOrder()
	{
		_InOrder(_root);
	}

	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}
protected:
	Node* _remove(Node* node, const K& val)
	{
		if (node == nullptr)
		{
			return nullptr;
		}

		if (node->_kv.first > val)
		{
			node->_left = _remove(node->_left, val);

			if (abs(node->_bf) > 1)
			{
				if (Depth(node->_right->_right) >= Depth(node->_right->_left))
				{
					// 右孩子的右子树高
					RotateL(node);
				}
				else
				{
					// 右孩子的左子树太高
					RotateRL(node);
				}
			}
		}
		else if (node->_kv.first < val)
		{
			node->_right = _remove(node->_right, val);

			// 右子树删除节点，可能导致左子树太高
			if (abs(node->_bf) > 1)
			{
				if (Depth(node->_left->_left) >= Depth(node->_left->_right))
				{
					// 左孩子的左子树太高
					RotateR(node);
				}
				else
				{
					// 左孩子的右子树太高
					RotateLR(node);
				}
			}
		}
		else
		{
			if (node->_left != nullptr && node->_right != nullptr)
			{
				if (Depth(node->_left) >= Depth(node->_right))
				{
					Node* prev = node->_left;
					while (prev->_right)
						prev = prev->_right;
					node->_kv.first = prev->_kv.first;
					node->_left = _remove(node->_left, prev->_kv.first);
				}
				else
				{
					Node* post = node->_right;
					while (post->_left)
						post = post->_left;
					node->_kv.first = post->_kv.first;
					node->_right = _remove(node->_right, post->_kv.first);
				}
			}
			else
			{
				//最多有一个孩子
				if (node->_left != nullptr)
				{
					Node* left = node->_left;
					delete node;
					return left;
				}
				else if (node->_right != nullptr)
				{
					Node* right = node->_right;
					delete node;
					return right;
				}
				else
				{
					//没有孩子
					return nullptr;
				}
			}
		}

		node->_bf = Depth(node->_right) - Depth(node->_left);

		return node;
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}

		//有可能parent是一个节点的子节点
		Node* ppNode = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (ppNode)
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}

			subL->_parent = ppNode;
		}
		else
		{
			_root = subL;
			subL->_parent == nullptr;
		}

		subL->_bf = parent->_bf = 0;
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		
		if (subRL)
		{
			subRL->_parent = parent;
		}

		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (ppNode)
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
		else
		{
			_root = subR;
			subR->_parent = nullptr;
		}

		subR->_bf = parent->_bf = 0;
	}

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)
		{
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			//说明在旋转前就已经不平衡
			assert(false);
		}

	}

	//求高度
	int Depth(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftDepth = Depth(root->_left);
		int rightDepth = Depth(root->_right);

		return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first<<" ";
		_InOrder(root->_right);

	}

	bool _IsBalanceTree(Node* root)
	{
		// 空树也是AVL树
		if (nullptr == root)
			return true;

		// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
		int leftHeight = Depth(root->_left);
		int rightHeight = Depth(root->_right);
		int diff = rightHeight - leftHeight;

		// 如果计算出的平衡因子与root的平衡因子不相等，或者
		// root平衡因子的绝对值超过1，则一定不是AVL树
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "节点平衡因子异常" << endl;
			return false;
		}

		if (diff != root->_bf)
		{
			cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
			return false;
		}

		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
		return _IsBalanceTree(root->_left)
			&& _IsBalanceTree(root->_right);
	}

	Node* _root = nullptr;
};
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

相关阅读:
【HDLBits 刷题 13】Circuits（8）Buliding Larger Circuits
设计模式深入解析与实例应用
 Unity websocket
SM4 研究与实现
 SpringBoot 10 登录功能和登录拦截器
 安卓车轮视图 WheelView kotlin
一次直播和图像识别技术应用的探索之旅
 手把手教你写Linux线程池
 利用NVIDIA GPU将Minecraft场景渲染成真实场景
 【数据结构--八大排序】之快速排序
原文地址：https://blog.csdn.net/smf12138/article/details/126476051