avl树
特性：
avl树又称自平衡二叉树查找树，平衡二叉树是，任一节点的左右子树的高度差不能超过1
首先它是一颗二叉查找树，所以任何父节点的值大于左孩子节点小于右孩子节点的值。
但是普通的二叉查找树不能够充分的体现二分的特性，它的左右子树可能分布并不均匀。
所以在查找和插入的时候复杂度可能会退化成线性的。所以，这时就需要来通过旋转操作
才维持树的平衡性，所以这就是自平衡二叉查找树。它通过各种旋转操作来保持树的平衡性。
avl树节点设计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class AVLTree;
template<class Type>
class AVLNode {
private:
Type data;
AVLNode<Type> *leftChild;
AVLNode<Type> *rightChild;
int bf;
public:
AVLNode():data(0), leftChild(NULL), rightChild(NULL), bf(0) {}
AVLNode(Type d, AVLNode<Type> *left = NULL, AVLNode<Type> *right = NULL)
:data(d), leftChild(left), rightChild(right), bf(0)
{}
~AVLNode() {}
friend class AVLNode<Type>;
};
|
avl树的设计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| template <class Type>
class AVLTree {
private:
AVLNode<Type> *root;
public:
AVLTree() : root(NULL) {}
public:
bool Insert(const Type &x)
{
return Insert(root, x);
}
bool Remove(const Type &x)
{
return Remove(root, x);
}
protected:
bool Insert(AVLNode<Type> *&t, const Type &x);
bool Remove(AVLNode<Type> *&t, const Type &x);
void RotateL(AVLNode<Type> *&ptr);
void RotateR(AVLNode<Type> *&ptr);
void RotateLR(AVLNode<Type> *&ptr);
void RotateRL(AVLNode<Type> *&ptr);
};
|
avl树的旋转
avl树每次插入或者删除就需要使用选装操作来维持树的平衡性。
总共分为：左旋转，右旋转，左右旋，和右左旋。
以下的旋转操作只是旋转，旋转之后链就断了，这个由之后操作再接起来。
左旋
1
2
3
4
5
6
7
8
9
| template<class Type>
void RotateL(AVLNode<Type> *&ptr)
{
AVLNode<Type> *subL = ptr;
ptr = subL->rightChild;
subL->rightChild = ptr->leftChild;
ptr->leftChild = subL;
subL->bf = ptr->bf = 0;
}
|
右旋
1
2
3
4
5
6
7
8
| void RotateR(AVLNode<Type> *&ptr)
{
AVLNode<Type> *subR = ptr;
ptr = subR->leftChild;
subR->leftChild = ptr->rightChild;
ptr->rightChild = subR;
subR->bf = ptr->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
| void AVLTree<Type>::RotateLR(AVLNode<Type> *&ptr)
{
AVLNode<Type> *subR = ptr;
AVLNode<Type> *subL = subR->leftChild;
ptr = subL->rightChild;
subL->rightChild = ptr->leftChild;
ptr->leftChild = subL;
if (ptr->bf <= 0) {
subL->bf = 0;
} else {
subL->bf = -1;
}
subR->leftChild = ptr->rightChild;
ptr->rightChild = subR;
if (ptr->bf == -1) {
subR->bf = 1;
} else {
subR->bf = 0;
}
ptr->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
| void AVLTree<Type>::RotateRL(AVLNode<Type> *&ptr)
{
AVLNode<Type> *subL = ptr;
AVLNode<Type> *subR = subL->rightChild;
ptr = subL->leftChild;
subR->leftChild = ptr->rightChild;
ptr->rightChild = subR;
if (ptr->bf <= 0) {
subR->bf = 0;
} else {
subR->bf = 1;
}
subL->rightChild = ptr->leftChild;
ptr->leftChild = subL;
if (ptr->bf == -1) {
subL->bf = 1;
} else {
subL->bf = 0;
}
ptr->bf = 0;
}
|
插入与删除
avl树的难点并不在如何旋转，而是在于判断树在插入或者删除之后判断改做出哪一种旋转操作。
插入
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
| template<class Type>
bool AVLTree<Type>::Insert(AVLNode<Type> *&t, const Type &x)
{
AVLNode<Type> *p = t;
AVLNode<Type> *pr = NULL;
stack<AVLNode<Type> * > st;
while(p != NULL)
{
if(p->data == x)
return false;
pr = p;
st.push(pr);
if(x < p->data)
p = p->leftChild;
else
p = p->rightChild;
}
p = new AVLNode<Type>(x);
if(NULL == p)
{
cout<<"Out Of Memory."<<endl;
exit(1);
}
if(pr == NULL)
{
t = p;
return true;
}
if(pr->data > x) {
pr->leftChild = p;
} else {
pr->rightChild = p;
}
while(!st.empty())
{
pr = st.top();
st.pop();
if(pr->leftChild == p)
pr->bf--;
else
pr->bf++;
if(pr->bf == 0) {
break;
}
if(pr->bf==1 || pr->bf==-1) {
p = pr;
} else {
int flag = pr->bf<0 ? -1 : 1;
if(p->bf == flag) {
if(p->bf < 0) {
RotateR(pr);
} else {
RotateL(pr);
}
} else {
if(p->bf > 0) {
RotateLR(pr);
} else {
RotateRL
}
}
break;
}
}
if(st.empty()) {
t = pr;
} else {
AVLNode<Type> *q = st.top();
if(q->data > pr->data) {
q->leftChild = pr;
} else {
q->rightChild = pr;
}
}
return true;
}
|
删除
