AVL树基本结构
AVL树是通过 balance factor 平衡因子来控制树的高度不会失衡的，每个节点的 balance factor 定义为右子树的高度减去左子树的高度，如果是平衡的，那么 balance factor 的绝对值不会超过1，如果超过了1，那么就需要进行旋转操作来保持平衡。
在维护AVL树的时候，基本操作只有 左旋 he 右旋 两种，其示意图如下：
不难发现，左旋和右旋都有保证树的高度不变的性质。
其中左旋的代码如下：
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
| void AVL::roteLeft(Node *A, Node *C) {
#ifdef DEBUG
cout << "Rote left \n";
#endif
if (A == this->root) {
Node *B = A->leftChild;
Node *D = C->leftChild;
Node *E = C->rightChild;
C->leftChild = A;
C->rightChild = E;
A->leftChild = B;
A->rightChild = D;
A->parent = C;
C->parent = nullptr;
if (B != nullptr)
B->parent = A;
if (D != nullptr)
D->parent = A;
if (E != nullptr)
E->parent = C;
this->root = C;
} else {
Node *parent = A->parent;
bool isLeft = (A == parent->leftChild);
Node *B = A->leftChild;
Node *D = C->leftChild;
Node *E = C->rightChild;
C->leftChild = A;
C->rightChild = E;
A->leftChild = B;
A->rightChild = D;
A->parent = C;
C->parent = parent;
if (B != nullptr)
B->parent = A;
if (D != nullptr)
D->parent = A;
if (E != nullptr)
E->parent = C;
if (isLeft) {
parent->leftChild = C;
} else {
parent->rightChild = C;
}
}
}
|
右旋代码如下：
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
| void AVL::roteRight(Node *A, Node *B) {
#ifdef DEBUG
cout << "Rote right \n";
#endif
if (A == this->root) {
Node *D = B->leftChild;
Node *E = B->rightChild;
Node *C = A->rightChild;
B->leftChild = D;
B->rightChild = A;
A->leftChild = E;
A->rightChild = C;
A->parent = B;
B->parent = nullptr;
if (C != nullptr)
C->parent = A;
if (D != nullptr)
D->parent = B;
if (E != nullptr)
E->parent = A;
this->root = B;
} else {
Node *parent = A->parent;
bool isLeft = (A == parent->leftChild);
Node *D = B->leftChild;
Node *E = B->rightChild;
Node *C = A->rightChild;
B->leftChild = D;
B->rightChild = A;
A->leftChild = E;
A->rightChild = C;
A->parent = B;
B->parent = parent;
if (C != nullptr)
C->parent = A;
if (D != nullptr)
D->parent = B;
if (E != nullptr)
E->parent = A;
if (isLeft) {
parent->leftChild = B;
} else {
parent->rightChild = B;
}
}
}
|
AVL树的插入和维护
插入流程
AVL树在插入的过程中和二叉搜索树是一致的，都是需要找到中序遍历的前驱，然后在叶子结点出插入，但是由于插入之后，树的形态可能发生改变，需要根据balance factor进行对应的修正。
插入后的维护
首先，证明每次插入最多只需要旋转一次使得树重新获得平衡：
假设在节点插入之前树是满足AVL的性质的，在插入一个叶子结点之后，假设存在一个节点A，使得A在旋转调整之后，树重新满足AVL的平衡性质。使用反证法证明这件事，假设存在A和A’两个节点需要旋转，容易知道A和A’至少有一个在另一个的子树中(插入叶子节点只会 影响插入路径上的点)，不妨假设A’在A的子树中，那么在A’经过旋转之后，子树的高度不变，回复平衡，A的平衡因子不再发生变化，那么就无需进行旋转了。
根据上述证明，可以想到，如果想要不使用递归找到这个点，关键就是需要找到在插入路径上面最后一个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
| Node *cur = this->root;
Node *parentOfCur = nullptr;
Node *lastNonZero = nullptr;
while (cur != nullptr) {
if (cur->bf != 0) {
lastNonZero = cur;
}
if (cur->value < val) {
parentOfCur = cur;
cur = cur->rightChild;
} else if (cur->value == val) {
return false;
} else {
parentOfCur = cur;
cur = cur->leftChild;
}
}
if (parentOfCur->value > val) {
parentOfCur->leftChild = insertNode;
insertNode->parent = parentOfCur;
} else {
parentOfCur->rightChild = insertNode;
insertNode->parent = parentOfCur;
}
|
这里通过迭代的方式，从根节点开始遍历，搜索插入节点的位置，并且实时更新最后一个bf非0的节点
找到bf非0的节点之后，需要根据这个节点和他的左右儿子的bf，选择相应的调整方式，具体如下(此处的bf是插入节点后重新计算的bf)：
- bf = 0:直接返回无需调整
- bf = 1/-1:写错了，建议检查一下
- bf = 2:
- 右子节点bf = 1:左单旋一次，两个节点的bf重新调整成0
- 右子节点bf = -1:右左双旋 注意，这里的bf需要根据右子节点的左子结点的bf分三类讨论
- 右子节点bf = 0: 左单旋一次，bf调整为一个1一个-1
- bf = -2:
- 左子节点bf = -1:右单旋一次，两个节点的bf重新调整成0
- 左子节点bf = 1:左右双旋 注意，这里的bf需要根据左子节点的右子结点的bf分三类讨论
- 左子节点bf = 0: 右单旋一次，bf调整为一个1一个-1
具体代码如下：
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
| if (lastNonZero->bf == 2) {
if (lastNonZero->rightChild->bf == 1) {
Node *A = lastNonZero;
Node *C = lastNonZero->rightChild;
roteLeft(lastNonZero, lastNonZero->rightChild);
A->bf = 0;
C->bf = 0;
} else if (lastNonZero->rightChild->bf == -1) {
Node *A = lastNonZero;
Node *C = A->rightChild;
Node *D = C->leftChild;
roteRight(C, D);
roteLeft(A, D);
if (D->bf == 0) {
A->bf = D->bf = C->bf = 0;
} else if (D->bf == 1) {
A->bf = -1;
D->bf = C->bf = 0;
} else if (D->bf == -1) {
C->bf = 1;
A->bf = D->bf = 0;
}
} else {
Node *A = lastNonZero;
Node *C = lastNonZero->rightChild;
roteLeft(lastNonZero, lastNonZero->rightChild);
A->bf = 1;
C->bf = -1;
}
} else if (lastNonZero->bf == -2) {
if (lastNonZero->leftChild->bf == -1) {
Node *A = lastNonZero;
Node *B = A->leftChild;
roteRight(A, B);
A->bf = 0;
B->bf = 0;
} else if (lastNonZero->leftChild->bf == 1) {
Node *A = lastNonZero;
Node *B = A->leftChild;
Node *E = B->rightChild;
roteLeft(B, E);
roteRight(A, E);
if (E->bf == 0) {
A->bf = B->bf = E->bf = 0;
} else if (E->bf == 1) {
E->bf = A->bf = 0;
B->bf = -1;
} else if (E->bf == -1) {
A->bf = 1;
B->bf = 0;
E->bf = 0;
} else throw Exception("Not a valid bf", Exception::CANNOT_REACH_HERE);
} else {
Node *A = lastNonZero;
Node *B = A->leftChild;
roteRight(A, B);
A->bf = -1;
B->bf = 1;
}
}
|
这里一定要仔细，虽然左右看起来是对称的，但是这个对称不是想象中那么简单的，还得自己推一遍
插入部分完整代码
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
| bool AVL::Insert(int val) {
Node *insertNode = new Node(val);
if (this->root == nullptr) {
this->root = insertNode;
return true;
} else {
Node *cur = this->root;
Node *parentOfCur = nullptr;
Node *lastNonZero = nullptr;
while (cur != nullptr) {
if (cur->bf != 0) {
lastNonZero = cur;
}
if (cur->value < val) {
parentOfCur = cur;
cur = cur->rightChild;
} else if (cur->value == val) {
return false;
} else {
parentOfCur = cur;
cur = cur->leftChild;
}
}
if (parentOfCur->value > val) {
parentOfCur->leftChild = insertNode;
insertNode->parent = parentOfCur;
} else {
parentOfCur->rightChild = insertNode;
insertNode->parent = parentOfCur;
}
if (lastNonZero == nullptr) {
cur = this->root;
lastNonZero = root;
} else {
cur = lastNonZero;
}
while (cur != nullptr) {
if (cur->value < val) {
cur->bf++;
cur = cur->rightChild;
} else if (cur->value == val) {
break;
} else {
cur->bf--;
cur = cur->leftChild;
}
}
if (lastNonZero->bf == 2) {
if (lastNonZero->rightChild->bf == 1) {
Node *A = lastNonZero;
Node *C = lastNonZero->rightChild;
roteLeft(lastNonZero, lastNonZero->rightChild);
A->bf = 0;
C->bf = 0;
} else if (lastNonZero->rightChild->bf == -1) {
Node *A = lastNonZero;
Node *C = A->rightChild;
Node *D = C->leftChild;
roteRight(C, D);
roteLeft(A, D);
if (D->bf == 0) {
A->bf = D->bf = C->bf = 0;
} else if (D->bf == 1) {
A->bf = -1;
D->bf = C->bf = 0;
} else if (D->bf == -1) {
C->bf = 1;
A->bf = D->bf = 0;
}
} else {
Node *A = lastNonZero;
Node *C = lastNonZero->rightChild;
roteLeft(lastNonZero, lastNonZero->rightChild);
A->bf = 1;
C->bf = -1;
}
} else if (lastNonZero->bf == -2) {
if (lastNonZero->leftChild->bf == -1) {
Node *A = lastNonZero;
Node *B = A->leftChild;
roteRight(A, B);
A->bf = 0;
B->bf = 0;
} else if (lastNonZero->leftChild->bf == 1) {
Node *A = lastNonZero;
Node *B = A->leftChild;
Node *E = B->rightChild;
roteLeft(B, E);
roteRight(A, E);
if (E->bf == 0) {
A->bf = B->bf = E->bf = 0;
} else if (E->bf == 1) {
E->bf = A->bf = 0;
B->bf = -1;
} else if (E->bf == -1) {
A->bf = 1;
B->bf = 0;
E->bf = 0;
} else throw Exception("Not a valid bf", Exception::CANNOT_REACH_HERE);
} else {
Node *A = lastNonZero;
Node *B = A->leftChild;
roteRight(A, B);
A->bf = -1;
B->bf = 1;
}
}
}
return true;
}
|
AVL树的删除和维护
删除一个节点比插入要更为复杂，具体来说，需要找到一个高度变矮的最小子树，逻辑如下:
- 第一次从根节点出发，找到在数值上等于被删除的节点的位置
- 如果这个节点没有子节点或者子节点只有一个，那么这个节点就是要删除的节点
- 如果这个节点有两个子节点，那么就需要寻找中序下面的直接前驱，即向左走一步然后一直向右走。找到前驱之后，实际删除的节点是它的前驱，然后把他的前驱的值放到原来的节点上
- 第二次倒过来走，由于删除一个节点，它自己肯定变矮，所以倒过来判断，可以假定上一个节点的左子树或者右子树一定变矮
- 如果左子树变矮，以当前节点为根节点的树高度变矮的情况是
- bf = -1:当前左子树本来较高
- bf = 1 且 cur->rightChild->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
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
| Node *AVL::findNoShorter(int val, Node *&toDelete, Node *&theNode) {
stack<Node *> stack1;
Node *noShorter = nullptr;
Node *cur = this->root;
bool isFind = false;
while (cur != nullptr) {
stack1.push(cur);
if (cur->value > val) {
cur = cur->leftChild;
} else if (cur->value < val) {
cur = cur->rightChild;
} else {
isFind = true;
theNode = cur;
if (cur->leftChild == nullptr || cur->rightChild == nullptr) {
toDelete = cur;
break;
} else {
cur = cur->leftChild;
stack1.push(cur);
while (cur->rightChild != nullptr) {
cur = cur->rightChild;
stack1.push(cur);
}
toDelete = cur;
break;
}
}
}
if (!isFind) {
throw Exception("No node to delete", Exception::NO_NODE_TO_DELETE);
} else {
Node *next = nullptr;
bool shorter = true;
while (!stack1.empty()) {
cur = stack1.top();
stack1.pop();
if (cur == toDelete) {
next = cur;
continue;
}
if (cur->leftChild == next) {
if (shorter && (cur->bf == -1 || (cur->bf == 1 && cur->rightChild->bf != 0))) {
shorter = true;
} else {
shorter = false;
while (!stack1.empty()) stack1.pop();
noShorter = cur;
break;
}
} else if (cur->rightChild == next) {
if (shorter && (cur->bf == 1 || (cur->bf == -1 && cur->leftChild->bf != 0))) {
shorter = true;
} else {
shorter = false;
while (!stack1.empty()) stack1.pop();
noShorter = cur;
break;
}
} else {
cout << "Can not reach here";
exit(-1);
}
next = cur;
}
}
if (noShorter == nullptr) noShorter = this->root;
return noShorter;
}
|
寻找完这个不会变矮的最小子树之后，从这个节点出发，沿着删除的路径依次向下遍历，直到到达物理上需要删除的节点，沿途一路调整对应的bf，调整逻辑如下：
- 如果是左子树变矮
- 当前的bf = -1或0则只需要修正bf的值，无需旋转
- 当前的bf = 1:
- 右子节点的bf = 1，进行一次左单旋，两个点的bf调整为0
- 右子节点的bf = 0，还是一次左单旋，两个点的bf改为1和-1
- 右子节点的bf = -1，需要进行右左双旋，bf的修正同insert的，注意三种情况
- 如果是右子树变矮
- 当前的bf = 1或0则只需要修正bf的值，无需旋转
- 当前的bf = -1:
- 左子节点的bf = -1，进行一次右单旋，两个点的bf调整为0
- 左子节点的bf = 0，还是一次右单旋，两个点的bf改为1和-1
- 左子节点的bf = 1，需要进行左右双旋，bf的修正同insert的，注意三种情况
修正方案比较复杂，建议自己推理一遍，代码如下：
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
| bool AVL::Delete(int val) {
Node *toDelete = nullptr;
Node *noShorter = nullptr;
Node *theNode = nullptr;
try {
noShorter = findNoShorter(val, toDelete, theNode);
}
catch (Exception &exp) {
if (exp.getcode() & Exception::NO_NODE_TO_DELETE) {
return false;
} else throw std::move(exp);
}
int val_ = toDelete->value;
Node *cur = noShorter;
if (toDelete == this->root) {
if (toDelete->leftChild != nullptr) {
this->root = toDelete->leftChild;
} else if (toDelete->rightChild != nullptr) {
this->root = toDelete->rightChild;
}
delete toDelete;
return true;
}
while (true) {
if (cur == toDelete) {
bool isLeft = (cur == cur->parent->leftChild);
if (cur->leftChild == nullptr && cur->rightChild == nullptr) {
if (isLeft) {
cur->parent->leftChild = nullptr;
} else cur->parent->rightChild = nullptr;
delete cur;
theNode->value = val_;
return true;
} else if (cur->leftChild == nullptr) {
if (isLeft) {
cur->parent->leftChild = cur->rightChild;
cur->rightChild->parent = cur->parent;
} else {
cur->parent->rightChild = cur->rightChild;
cur->rightChild->parent = cur->parent;
}
delete cur;
theNode->value = val_;
return true;
} else if (cur->rightChild == nullptr) {
if (isLeft) {
cur->parent->leftChild = cur->leftChild;
cur->leftChild->parent = cur->parent;
} else {
cur->parent->rightChild = cur->leftChild;
cur->leftChild->parent = cur->parent;
}
delete cur;
theNode->value = val_;
return true;
} else throw Exception("delete node with two child", Exception::CANNOT_REACH_HERE);
break;
}
if (cur->value > val_) {
if (cur->bf <= 0) {
cur->bf++;
cur = cur->leftChild;
} else {
if (cur->rightChild->bf == 1) {
Node *P = cur;
Node *Q = cur->rightChild;
roteLeft(P, Q);
P->bf = 0;
Q->bf = 0;
} else if (cur->rightChild->bf == -1) {
Node *P = cur;
Node *Q = cur->rightChild;
Node *R = Q->leftChild;
roteRight(Q, R);
roteLeft(P, R);
P->bf = R->bf == 1 ? -1 : 0;
Q->bf = R->bf == -1 ? 1 : 0;
R->bf = 0;
} else {
Node *P = cur;
Node *Q = P->rightChild;
roteLeft(P, Q);
Q->bf = -1;
P->bf = 1;
}
cur = cur->leftChild;
}
} else if (cur->value < val_) {
if (cur->bf >= 0) {
cur->bf--;
cur = cur->rightChild;
} else {
if (cur->leftChild->bf == -1) {
Node *P = cur;
Node *Q = cur->leftChild;
roteRight(P, Q);
P->bf = 0;
Q->bf = 0;
} else if (cur->leftChild->bf == 1) {
Node *P = cur;
Node *Q = cur->leftChild;
Node *R = Q->rightChild;
roteLeft(Q, R);
roteRight(P, R);
if (R->bf == 0) {
P->bf = Q->bf = R->bf = 0;
} else if (R->bf == 1) {
R->bf = 0;
P->bf = 0;
Q->bf = -1;
} else {
R->bf = 0;
Q->bf = 0;
P->bf = 1;
}
} else {
Node *P = cur;
Node *Q = P->leftChild;
roteRight(P, Q);
Q->bf = 1;
P->bf = -1;
}
cur = cur->rightChild;
}
} else {
if (cur == toDelete) {
throw Exception("Can not reach here", Exception::CANNOT_REACH_HERE);
}
}
}
theNode->value = val_;
return true;
}
|
验证树是否合法
在这里给出一个check函数，可以验证构建的树是否是合法的
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
| bool AVL::check() {
try {
check(this->root);
return true;
} catch (Exception &exp) {
if (exp.getcode() & Exception::DEBUG_ERROR) {
cout << exp.what() << " " << ios::hex << exp.getcode() << endl;
exit(-1);
return false;
}
}
}
int AVL::check(Node *cur) {
int height = 0;
int heightL = 0;
int heightR = 0;
if (cur->leftChild != nullptr) {
heightL = check(cur->leftChild);
}
if (cur->rightChild != nullptr)
heightR = check(cur->rightChild);
if (cur->bf != heightR - heightL) {
cur->print();
cout << "heightR = " << heightR << " heightL = " << heightL << " bf= " << cur->bf << endl;
throw Exception("Error BF counting", Exception::DEBUG_ERROR | Exception::DEBUG_ERROR_BF);
}
if (cur->leftChild != nullptr && cur->value <= cur->leftChild->value) {
throw Exception("Left is too large", Exception::DEBUG_ERROR | Exception::DEBUG_ERROR_ERROR_ORDER);
}
if (cur->rightChild != nullptr && cur->rightChild->value <= cur->value) {
throw Exception("Right is too small", Exception::DEBUG_ERROR | Exception::DEBUG_ERROR_ERROR_ORDER);
}
if (cur->bf >= 2 || cur->bf <= -2) {
throw Exception("bf out of range", Exception::DEBUG_ERROR | Exception::DEBUG_ERROR_BF);
}
if (cur->leftChild != nullptr && cur->leftChild->parent != cur) {
throw Exception("error connection on left", Exception::DEBUG_ERROR | Exception::DEBUG_ERROR_CONNECTION);
}
if (cur->rightChild != nullptr && cur->rightChild->parent != cur) {
throw Exception("error connection on right", Exception::DEBUG_ERROR | Exception::DEBUG_ERROR_CONNECTION);
}
height = max(heightL, heightR) + 1;
return height;
}
|
所有程序的完整代码详见github
