平衡二叉查找树简称平衡二叉树，则前苏联数学家Adelse-Velskill和Landis发明，所以又称AVL树。它满足：
1、为二叉查找树；
2、为空树；
3、如果不是空树，任意一个节点的左子树和右子树都是平衡二叉树，且高度之差不超过1。
平衡因子：某节点的平衡因子定义为其左右子树高度之差。在平衡二叉树，任意节点的平衡因子只能取-1、0和1。
平衡二叉树的节点定义为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
struct AVLNode {
int value; // 节点值，使用更改为需要的类型或者使用模板
int depth; // 深度，即以此节点为根节点的子树高度
int balance; // 平衡因子，左子树高度减去右子树高度
AVLNode *parent; // 父节点
AVLNode *left; // 左孩子
AVLNode *right; // 右孩子
explicit AVLNode(int value) : value(value) {
depth = 0;
balance = 0;
parent = left = right = nullptr;
}
~AVLNode() {
delete left;
delete right;
}
};
|
平衡二叉树定义为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class AVL {
public:
AVL() : avl_root(nullptr) {}
~AVL() {
delete avl_root;
}
// 查找数据。如果找到数据则返回数据所在节点的指针，如果没有找到则返回nullptr。
AVLNode *search(int data);
// 插入数据。如果data已存在，则什么也不做。
// 如果应用时为key-value组合可改为更新value
void insert(int data);
// 删除数据
void erase(int data);
// 删除节点
void erase(AVLNode *node);
AVLNode *getRoot() const { return avl_root; }
private:
AVLNode *avl_root;
// 计算节点深度，假定其孩子节点的深度已经计算完毕
static int getDepth(AVLNode *root);
// 计算节点平衡因子，假定其孩子节点的深度已经计算完毕
static int getBalance(AVLNode *root);
// 左旋
void leftRotate(AVLNode *root);
// 右旋
void rightRotate(AVLNode *root);
};
|
平衡二叉树是一种查找二叉树，主要目的仍是为了快速查找数据，查找过程与普通的二叉查找树没有区别，代码描述如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
// 对外接口
public: AVLNode *search(int data) {
return search(avl_root, data);
}
// 递归实现(也可以用循环实现，不需要使用栈记录路径)
private: AVLNode *AVL::search(AVLNode *root, int data) {
if (!root)
return nullptr;
if (root->value == data)
return root;
else if (root->value < data)
return search(root->right, data);
else
return search(root->left, data);
}
|
如果找到数据则返回数据所在的节点指针，如果没有找到数据则返回nullptr;
在维护平衡二叉树过程中，需要从子树计算节点的深度和平衡因子而不能直接使用节点保存的信息，此处给出两个函数用于计算节点的深度和平衡因子，此处假定节点的孩子的深度已经计算好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// 计算节点深度，假定其孩子节点的深度已经计算完毕
int AVL::getDepth(AVLNode *root) {
if (!root)
return 0;
int left_depth = root->left ? root->left->depth : 0;
int right_depth = root->right ? root->right->depth : 0;
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
// 计算节点平衡因子，假定其孩子节点的深度已经计算完毕
int AVL::getBalance(AVLNode *root) {
if (!root)
return 0;
int left_depth = root->left ? root->left->depth : 0;
int right_depth = root->right ? root->right->depth : 0;
return left_depth - right_depth;
}
|
在插入节点到平衡二叉树时，或者从平衡二叉树删除节点时，可能破坏二叉树的平衡性，为了将这样的二叉树重新调整为平衡二叉树，一般使用旋转操作。旋转具体分为左旋与右旋。
左旋用于将一棵平衡因子为-2的二叉树旋转为平衡二叉树，即原树左子树的高度比右子树的高度小2，绕根节点旋转后左子树高度与右子树高度相同。左旋的一个示例如下：
代码描述为：
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
|
// 左旋
void AVL::leftRotate(AVLNode *root) {
if (!root || !root->right)
return;
// 右孩子变成根节点
AVLNode *new_root = root->right;
AVLNode *parent = root->parent;
new_root->parent = parent;
if (parent) {
if (parent->left == root)
parent->left = new_root;
else
parent->right = new_root;
} else { // 整棵树都旋转了，根节点需要改变
avl_root = new_root;
}
// 右孩子的左子树变成root的右子树
root->right = new_root->left;
if (new_root->left)
new_root->left->parent = root;
// root成为右孩子(原来的)的左子树
new_root->left = root;
root->parent = new_root;
// 更新深度信息
root->depth = getDepth(root);
root->balance = getBalance(root);
new_root->depth = getDepth(new_root);
new_root->balance = getBalance(new_root);
}
|
右旋用于将一棵平衡因子为2的二叉树旋转为平衡二叉树，即原树的左子树比右子树的高度大2，绕根节点旋转后高度相同，如:
代码描述为：
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
|
// 右旋
void AVL::rightRotate(AVLNode *root) {
if (!root || !root->left)
return;
// 左孩子变成根节点
AVLNode *new_root = root->left;
AVLNode *parent = root->parent;
new_root->parent = parent;
if (parent) {
if (parent->left == root)
parent->left = new_root;
else
parent->right = new_root;
} else { // 整棵树都旋转了，根节点需要改变
avl_root = new_root;
}
// 左孩子的右子树变成root的左子树
root->left = new_root->right;
if (new_root->right)
new_root->right->parent = root;
// root成为其左孩子(原来)的右子树
new_root->right = root;
root->parent = new_root;
// 更新深度信息
root->depth = getDepth(root);
root->balance = getBalance(root);
new_root->depth = getDepth(new_root);
new_root->balance = getBalance(new_root);
}
|
左旋和右旋的代码非常相似，主要考虑这几个步骤：1、改变根节点，可能需要改变整棵树的根节点；2、由原来的根节点收养旋转后由它占去的位置上的分支；3、原来的根节点成为新的根节点的子树；4、重新计算深度和平衡因子。
插入数据首先需要考虑是否为空树，如果是空树则直接插入为根节点即可。如果不是空树，则和查找的过程类似(不考虑已经数据的情况)：1、如果data < root->value，则将它插入到root的左子树中，如果root没有左子树，则将它插入为root的左子树；2、如果data > root->value，则将它插入到root的右子树中，如果root没有右子树，则将它插入为root的右子树。
插入节点之后，二叉树的平衡性可能被打破，此时可以通过旋转操作来重新使二叉树平衡。每次插入操作不需要对整个二叉树进行调整，只需要调整失衡的部分即可。从插入节点向上第一个平衡因子的绝对值大于1的节点为根的子树称为最小失衡树。平衡二叉树的失衡通过旋转最小失衡树来调整，哪边的子树较高，就把哪边的子树旋转上来。
根据引起失衡的节点在最小失衡树A中的插入位置，可以分为以下四种情况：
1、插入在A的左孩子的左子树中(LL)
做一次右旋即可。
2、插入在A的右孩子的右子树中(RR)
做一次左旋即可。
3、插入在A的左孩子的右子树中(LR)
只做一次右旋仍然不能平衡，因此需要先对左子树做一次左旋变成第一种情况，然后再做一次右旋使二叉树平衡：
4、插入在A的右孩子的左子树中(RL)
一次左旋后仍然不能平衡，需要先对右子树做一次右旋变成第二种情况，然后再做一次左旋使二叉树平衡：
在实际的插入过程中，插入之后，往上递归，先计算当前节点的平衡因子，如果平衡因子是2则表明左高右低，需要右旋，右旋之前再检查一下其左子树的平衡因子，如果平衡因子是0或者1就是第1种情况，如果平衡因子是-1则为第3种情况，需要先对左子树进行左旋。如果当前节点的平衡因子是-2则表明左低右高，需要左旋，左旋之前检查一下其右子树的平衡因子，如果是1则为第4种情况，需要先对右子树进行右旋。代码描述为：
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
|
// 公共接口，插入数据。如果data已存在，则什么也不做。
// 如果应用时为key-value组合可改为更新value
public: void AVL::insert(int data) {
if (!avl_root) {
avl_root = new AVLNode(data);
return;
}
insert(avl_root, data);
}
// 递归插入数据。假定根节点不为空
private: void AVL::insert(AVLNode *root, int data) {
// 要插入的数据小于根节点，往左边插入
if (data < root->value) {
if (root->left)
insert(root->left, data);
else {
root->left = new AVLNode(data);
root->left->parent = root;
}
}
// 要插入的数据大于根节点，往右边插入
else if (data > root->value) {
if (root->right)
insert(root->right, data);
else {
root->right = new AVLNode(data);
root->right->parent = root;
}
}
// data已经存在，什么也不做，如果为key-value组合可改为更新value
else { // data == root->value
return;
}
// 计算平衡因子
root->balance = getBalance(root);
// 左子树比右子树高，应当右旋
if (root->balance == 2) {
// 如果左子树的右子树比左子树的左子树高，直接右旋后仍然不平衡，必须先对左子树进行左旋
if (root->left->balance == -1)
leftRotate(root->left);
rightRotate(root);
}
// 右子树比左子树高，应当左旋
else if (root->balance == -2) {
// 如果右子树的左子树比右子树的右子树高，必须先对右子树右旋
if (root->right->balance == 1)
rightRotate(root->right);
leftRotate(root);
}
// 更新深度，平衡因子已经计算过了，如果有旋转，则平衡因子在旋转的函数中更新，
// 而深度在这时重复计算
root->depth = getDepth(root);
}
|
插入节点之后从下往上维护平衡性，遇到的第一个不平衡的节点即为最小失衡树的根节点，通过旋转使最小失衡树使二叉树重新平衡。可以看出以上四种插入都不改变最小失衡树的高度，因此最小失衡树往上的节点的深度和平衡因子都不会改变，也不会失衡。所以插入操作最多需要两次旋转，时间复杂度为O(log n)。
平衡二叉树是一种二叉搜索树，删除节点之后必须保证节点的值满足二叉搜索树的要求，因此此处先给出二叉搜索树删除节点的思路。二叉搜索树删除节点时根据节点的子树情况来考虑：
1、被删除节点为叶子节点，直接删除即可，需要考虑此节点有根节点的情况；
2、被删除节点只有左孩子，或者只有右孩子。有两种思路：
(1) 无论是左子树还是右子树，它们的所有节点的值都是大于被删除节点的父节点的，因此可以直接将左子树或者右子树移动上来替换掉被删除节点；
(2) 只有左孩子则在左子树寻找拥有最大值的节点，只有右孩子则在右子树中寻找拥有最小值的节点，将它的值与被删除节点的值交换，然后递归删除找到的节点。这是一个递归的过程，比第一种思路复杂，后面从平衡二叉树中删除节点采用第1种思路。
3、被删除节点既有左孩子又有右孩子。可以从左子树中寻找拥有最大值的节点，或者从右子树中寻找拥有最小值的节点，将它的值与被删除节点交换，然后递归删除找到的节点。显然左子树中拥有最大值的节点不可能有右孩子，右子树中拥有最小值的节点不可能有左孩子，因此交换一次后，需要递归删除的节点必定是第2种情况。考虑到要使二叉搜索树左右子树的高度尽量接近，以提升查找的性能，此处可以选择左右子树高度较高的一边进行递归删除。
下面的图演示了如何从二叉搜索树删除节点。
1、二叉搜索树删除叶子节点
2.1、二叉搜索树删除只有左孩子的节点
2.2、递归删除只有左孩子的节点
此处4和3交换之后4已经是叶子节点，直接删除即可，如果3还有左子树，则交换过后4仍然是只有左孩子的节点，重复此过程直到4为叶子节点即可。删除只有右孩子的节点与此类似，此处不再赘述。
3、删除既有左孩子又有右孩子的节点
交换一次之后，3只有左子树而没有右子树，按2的情况处理即可。
二叉搜索树的删除比较简单，此处不再给出代码，接下来考虑如何从平衡二叉树中删除节点，即考虑二叉树删除节点之后如何调整使其重新平衡。比较简单的策略是从删除的节点开始向上更新深度和平衡因子，如果平衡因子为-2或者2则进行左旋或者右旋，一直到根节点。代码描述如下：
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
|
void AVL::erase(AVLNode *node) {
// 空指针什么也不做
if (!node)
return;
AVLNode *parent = node->parent;
// node既有左孩子又有右孩子
if (node->left && node->right) {
AVLNode *replace_node = nullptr;
if (node->left->depth > node->right->depth) { // 左树高，从左树选最大值替换
replace_node = node->left;
while (replace_node->right)
replace_node = replace_node->right;
} else { // 右树高，从右树选最小值替换
replace_node = node->right;
while (replace_node->left)
replace_node = replace_node->left;
}
// 将replace_node的值移动上来，然后删除replace_node，它最多只有一个孩子
node->value = replace_node->value; // 非内置类型可能需要移动语义
node = replace_node;
}
// 如果node只有左孩子或者只有右孩子或者没有孩子
if (!node->left && !node->right) { // 叶子节点
if (!parent) { // 根节点
avl_root = nullptr;
} else { // 非根节点
if (node == parent->left)
parent->left = nullptr;
else
parent->right = nullptr;
}
} else if (node->left && !node->right) { // 只有左孩子
if (!parent) { // 根节点
avl_root = node->left;
} else { // 非根节点
if (node == parent->left)
parent->left = node->left;
else
parent->right = node->left;
}
node->left = nullptr;
} else { // 只有右孩子
if (!parent) { // 根节点
avl_root = node->right;
} else { // 非根节点
if (node == parent->left)
parent->left = node->right;
else
parent->right = node->right;
}
node->right = nullptr;
}
delete node;
// 向上更新节点深度
while (parent) {
parent->depth = getDepth(parent);
parent->balance = getBalance(parent);
if (parent->balance == -2) {
if (parent->right->balance == 1)
rightRotate(parent->right);
leftRotate(parent);
} else if (parent->balance == 2) {
if (parent->left->balance == -1)
leftRotate(parent->left);
rightRotate(parent);
}
parent = parent->parent;
}
}
|
这段代码和二叉搜索树删除节点的代码相比，只多了向上更新节点深度和平衡因子的代码，将这部分代码去掉即可得到二叉搜索树的删除节点代码。值得注意的是删除节点不能只通过调整最小失衡树来使二叉树重新平衡，最坏情况下需要回溯到根节点，进行多次旋转。
除上述函数之外，还需要一个根据给定数据查找并删除节点的函数，作简单的封装即可：
1
2
3
4
|
void AVL::erase(int data) {
AVLNode *node = search(data);
erase(node);
}
|
1、使用循环重写以上代码。查找数据不需要记录路径，不需要使用栈，而插入数据和删除数据时需要更新祖先节点的深度和平衡因子，可以使用栈来记录路径，也可以使用parent指针回溯。
2、插入更新时：如果当前节点的高度没有改变，则停止向上回溯父节点。
3、删除更新时：如果当前节点的高度没有改变，且平衡值在[-1, 1]区间则停止回溯。
查找函数的循环实现
1
2
3
4
5
6
7
8
9
10
|
AVLNode *AVL::search(int data) {
AVLNode *p = avl_root;
while (p && p->value != data) {
if (data < p->value)
p = p->left;
else
p = p->right;
}
return p;
}
|
当平衡二叉树为空时或者平衡二叉树中不存在data这个值时，循环将于p为nullptr时停止，然后返回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
|
void AVL::insert(int data) {
if (!avl_root) {
avl_root = new AVLNode(data);
return;
}
AVLNode *p = avl_root;
while (true) {
// 如果data在平衡二叉树中已经存在则什么也不做，
// 实际应用时如果是key-value的类型可以更新value
if (p->value == data) {
return;
} else if (data < p->value) { // 插入到左子树中
if (p->left) {
p = p->left;
} else {
p->left = new AVLNode(data);
p->left->parent = p;
break;
}
} else { // 插入到右子树中
if (p->right) {
p = p->right;
} else {
p->right = new AVLNode(data);
p->right->parent = p;
break;
}
}
}
// 向上更新节点深度和平衡因子
while (p) {
int depth_record = p->depth;
p->balance = getBalance(p);
if (p->balance == -2) { // 左旋
if (p->right->balance == 1)
rightRotate(p->right);
leftRotate(p);
} else if (p->balance == 2) { // 右旋
if (p->left->balance == -1)
leftRotate(p->left);
rightRotate(p);
}
// 如果p的深度不变，则p的祖先节点的深度和平衡因子都不变，无需继续回溯
p->depth = getDepth(p);
if (depth_record == p->depth)
return;
p = p->parent;
}
}
|
此处使用parent指针进行回溯，当某个节点的深度不变时不会再对其祖先节点造成影响，因此回溯可以提前终止。
删除节点函数的优化实现
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
|
void AVL::erase(AVLNode *node) {
// 空指针什么也不做
if (!node)
return;
AVLNode *parent = node->parent;
// node既有左孩子又有右孩子
if (node->left && node->right) {
AVLNode *replace_node = nullptr;
if (node->left->depth > node->right->depth) { // 左树高，从左树选最大值替换
replace_node = node->left;
while (replace_node->right)
replace_node = replace_node->right;
} else { // 右树高，从右树选最小值替换
replace_node = node->right;
while (replace_node->left)
replace_node = replace_node->left;
}
// 将replace_node的值移动上来，然后删除replace_node，它最多只有一个孩子
node->value = replace_node->value; // 非内置类型可能需要移动语义
node = replace_node;
}
// 如果node只有左孩子或者只有右孩子或者没有孩子
if (!node->left && !node->right) { // 叶子节点
if (!parent) { // 根节点
avl_root = nullptr;
} else { // 非根节点
if (node == parent->left)
parent->left = nullptr;
else
parent->right = nullptr;
}
} else if (node->left && !node->right) { // 只有左孩子
if (!parent) { // 根节点
avl_root = node->left;
} else { // 非根节点
if (node == parent->left)
parent->left = node->left;
else
parent->right = node->left;
}
node->left = nullptr;
} else { // 只有右孩子
if (!parent) { // 根节点
avl_root = node->right;
} else { // 非根节点
if (node == parent->left)
parent->left = node->right;
else
parent->right = node->right;
}
node->right = nullptr;
}
delete node;
// 向上更新节点深度
while (parent) {
int depth_record = parent->depth;
parent->balance = getBalance(parent);
if (parent->balance == -2) {
if (parent->right->balance == 1)
rightRotate(parent->right);
leftRotate(parent);
} else if (parent->balance == 2) {
if (parent->left->balance == -1)
leftRotate(parent->left);
rightRotate(parent);
}
// 如果某个节点的深度不变，则无需继续向上回溯
parent->depth = getDepth(parent);
if (depth_record == parent->depth)
return;
parent = parent->parent;
}
}
|
erase函数和之前大同小异，和insert类似，仅增加了判断节点深度是否变化的逻辑。
此外，可以看到insert和erase中向上更新节点深度和平衡因子的代码是完全一样的，可以将其单独拿出来作为一个函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void siftup(AVLNode *p) {
while (p) {
int depth_record = p->depth;
p->balance = getBalance(p);
if (p->balance == -2) { // 左旋
if (p->right->balance == 1)
rightRotate(p->right);
leftRotate(p);
} else if (p->balance == 2) { // 右旋
if (p->left->balance == -1)
leftRotate(p->left);
rightRotate(p);
}
// 如果p的深度不变，则p的祖先节点的深度和平衡因子都不变，无需继续回溯
p->depth = getDepth(p);
if (depth_record == p->depth)
return;
p = p->parent;
}
}
|
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
|
struct AVLNode {
int value; // 节点值，使用更改为需要的类型或者使用模板
int depth; // 深度，即以此节点为根节点的子树高度
int balance; // 平衡因子，左子树高度减去右子树高度
AVLNode *parent; // 父节点
AVLNode *left; // 左孩子
AVLNode *right; // 右孩子
explicit AVLNode(int value) : value(value) {
depth = 1;
balance = 0;
parent = left = right = nullptr;
}
// 析构函数，递归删除二叉树，这样只需要删除根节点即可删除整个二叉树
~AVLNode() {
delete left;
delete right;
}
};
class AVL {
public:
AVL() : avl_root(nullptr) {}
~AVL() {
delete avl_root;
}
// 查找数据。如果找到数据则返回数据所在节点的指针，如果没有找到则返回nullptr。
AVLNode *search(int data);
// 插入数据。如果data已存在，则什么也不做。
// 如果应用时为key-value组合可改为更新value
void insert(int data);
// 删除数据
void erase(int data);
// 删除节点
void erase(AVLNode *node);
AVLNode *getRoot() const { return avl_root; }
private:
AVLNode *avl_root;
// 计算节点深度，假定其孩子节点的深度已经计算完毕
static int getDepth(AVLNode *root);
// 计算节点平衡因子，假定其孩子节点的深度已经计算完毕
static int getBalance(AVLNode *root);
// 左旋
void leftRotate(AVLNode *root);
// 右旋
void rightRotate(AVLNode *root);
};
int AVL::getDepth(AVLNode *root) {
if (!root)
return 0;
int left_depth = root->left ? root->left->depth : 0;
int right_depth = root->right ? root->right->depth : 0;
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
int AVL::getBalance(AVLNode *root) {
if (!root)
return 0;
int left_depth = root->left ? root->left->depth : 0;
int right_depth = root->right ? root->right->depth : 0;
return left_depth - right_depth;
}
void AVL::leftRotate(AVLNode *root) {
if (!root || !root->right)
return;
// 右孩子变成根节点
AVLNode *new_root = root->right;
AVLNode *parent = root->parent;
new_root->parent = parent;
if (parent) {
if (parent->left == root)
parent->left = new_root;
else
parent->right = new_root;
} else { // 整棵树都旋转了，根节点需要改变
avl_root = new_root;
}
// 右孩子的左子树变成root的右子树
root->right = new_root->left;
if (new_root->left)
new_root->left->parent = root;
// root成为右孩子(原来的)的左子树
new_root->left = root;
root->parent = new_root;
// 更新深度信息
root->depth = getDepth(root);
root->balance = getBalance(root);
new_root->depth = getDepth(new_root);
new_root->balance = getBalance(new_root);
}
void AVL::rightRotate(AVLNode *root) {
if (!root || !root->left)
return;
// 左孩子变成根节点
AVLNode *new_root = root->left;
AVLNode *parent = root->parent;
new_root->parent = parent;
if (parent) {
if (parent->left == root)
parent->left = new_root;
else
parent->right = new_root;
} else { // 整棵树都旋转了，根节点需要改变
avl_root = new_root;
}
// 左孩子的右子树变成root的左子树
root->left = new_root->right;
if (new_root->right)
new_root->right->parent = root;
// root成为其左孩子(原来)的右子树
new_root->right = root;
root->parent = new_root;
// 更新深度信息
root->depth = getDepth(root);
root->balance = getBalance(root);
new_root->depth = getDepth(new_root);
new_root->balance = getBalance(new_root);
}
AVLNode *AVL::search(int data) {
AVLNode *p = avl_root;
while (p && p->value != data) {
if (data < p->value)
p = p->left;
else
p = p->right;
}
return p;
}
void AVL::insert(int data) {
if (!avl_root) {
avl_root = new AVLNode(data);
return;
}
AVLNode *p = avl_root;
while (true) {
// 如果data在平衡二叉树中已经存在则什么也不做，
// 实际应用时如果是key-value的类型可以更新value
if (p->value == data) {
return;
} else if (data < p->value) { // 插入到左子树中
if (p->left) {
p = p->left;
} else {
p->left = new AVLNode(data);
p->left->parent = p;
break;
}
} else { // 插入到右子树中
if (p->right) {
p = p->right;
} else {
p->right = new AVLNode(data);
p->right->parent = p;
break;
}
}
}
// 向上更新节点深度和平衡因子
while (p) {
int depth_record = p->depth;
p->balance = getBalance(p);
if (p->balance == -2) { // 左旋
if (p->right->balance == 1)
rightRotate(p->right);
leftRotate(p);
} else if (p->balance == 2) { // 右旋
if (p->left->balance == -1)
leftRotate(p->left);
rightRotate(p);
}
// 如果p的深度不变，则p的祖先节点的深度和平衡因子都不变，无需继续回溯
p->depth = getDepth(p);
if (depth_record == p->depth)
return;
p = p->parent;
}
}
void AVL::erase(AVLNode *node) {
// 空指针什么也不做
if (!node)
return;
AVLNode *parent = node->parent;
// node既有左孩子又有右孩子
if (node->left && node->right) {
AVLNode *replace_node = nullptr;
if (node->left->depth > node->right->depth) { // 左树高，从左树选最大值替换
replace_node = node->left;
while (replace_node->right)
replace_node = replace_node->right;
} else { // 右树高，从右树选最小值替换
replace_node = node->right;
while (replace_node->left)
replace_node = replace_node->left;
}
// 将replace_node的值移动上来，然后删除replace_node，它最多只有一个孩子
node->value = replace_node->value; // 非内置类型可能需要移动语义
node = replace_node;
}
// 如果node只有左孩子或者只有右孩子或者没有孩子
if (!node->left && !node->right) { // 叶子节点
if (!parent) { // 根节点
avl_root = nullptr;
} else { // 非根节点
if (node == parent->left)
parent->left = nullptr;
else
parent->right = nullptr;
}
} else if (node->left && !node->right) { // 只有左孩子
if (!parent) { // 根节点
avl_root = node->left;
} else { // 非根节点
if (node == parent->left)
parent->left = node->left;
else
parent->right = node->left;
}
node->left = nullptr;
} else { // 只有右孩子
if (!parent) { // 根节点
avl_root = node->right;
} else { // 非根节点
if (node == parent->left)
parent->left = node->right;
else
parent->right = node->right;
}
node->right = nullptr;
}
delete node;
// 向上更新节点深度
while (parent) {
int depth_record = parent->depth;
parent->balance = getBalance(parent);
if (parent->balance == -2) {
if (parent->right->balance == 1)
rightRotate(parent->right);
leftRotate(parent);
} else if (parent->balance == 2) {
if (parent->left->balance == -1)
leftRotate(parent->left);
rightRotate(parent);
}
// 如果某个节点的深度不变，则无需继续向上回溯
parent->depth = getDepth(parent);
if (depth_record == parent->depth)
return;
parent = parent->parent;
}
}
void AVL::erase(int data) {
AVLNode *node = search(data);
erase(node);
}
|
[1] https://zhuanlan.zhihu.com/p/56066942.
[2] https://zhuanlan.zhihu.com/p/94130997.
[3] 数据结构 二叉查找树. https://blog.csdn.net/wenqian1991/article/details/18228309.
[4] 平衡二叉树 AVL树(二) —— 删除. https://blog.csdn.net/yeswenqian/article/details/22291675.