0%

AVL树

AVL树

基础知识

名称 : AVL树

发明者 :

G. M. Adelson-Velsky

E.M. Landis

年代 : 1962年(58岁)

优点 :

由于对每个节点的左右子树的树高做了限制, 所以整棵树不会退化成一个链表

**学习重点 : **

  1. 平衡二叉排序树,本质上也是二叉排序树, 所以拥有二叉排序树的所有性质
  2. 平衡二叉排序树的学习重点, 在于平衡条件以及平衡调整的相关学习

性质 :

  1. 平衡条件 : | H(left) - H(right) | ≤ 1

思考 :

​ 高度为 H 的树, 所包含节点的范围是?

​ BinarySearchTree : H ≤ size ≤ 2^H - 1

​ AVLTree : low(H-2) + low(H-1) + 1 ≤ size ≤ 2^H - 1 (low(H) 是 H 高度的二叉树的最少节点数) 左边等于 1.5^H

操作SSS

AVL树 - 左旋

左旋前 左旋后 AVL树 - 右旋 右旋前 右旋后

失衡类型

h(1,2,3,4) 分别代表左孩子的左子树个高,左孩子的右子树高,右孩子的左子树高和右孩子的右子树高

LL类型:左子树的左孩子更高

满足条件 : h1 = max(h3, h4) + 2 = h2 + 1

调整方案 : K1 右旋

LR类型:左子树的右孩子更高

满足条件 : max(h2, h3) = h4 = h1

调整方案 : 小左旋, 大右旋(左孩子左旋, 根节点右旋)

RL类型:右子树的左孩子更高

调整方案 : 小右旋, 大左旋

RR类型:右子树的右孩子更高

调整方案 : K1 左旋

平衡调整策略

  1. 发生在回溯阶段的, 第一个失衡节点处
  2. 理解平衡调整策略的关键在于 : 分析清楚四种情况下, ABCD四棵子树树高的关系
  3. LL, 大右旋
  4. LR, 先小左旋, 再大右旋
  5. RL, 先小右旋, 再大左旋
  6. RR, 大左旋

代码关键点

  1. 插入和删除以后, 注意调整树高字段, 先调低的root, 再调高的tmp
  2. 引入了NIL节点, 代替了 NULL和nullptr, NULL不可访问资源, NIL是一个实际节点, 可以访问资源(h,lchild,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
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
#include <cstdio>
#include <iostream>
using namespace std;

#define L(n) (n->lchild)
#define R(n) (n->rchild)
#define H(n) (n->h)

typedef struct Node{
int key,h;
struct Node *lchild, *rchild;
}Node;

//虚拟空节点, 为红黑树做准备的节点
Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void init_NIL(){
NIL->key = 0, NIL->h = 0;
NIL->lchild = NIL->rchild = nullptr;
}
//优先初始化上面这一段代码


/*
* AVL树的若干操作:
* 1. 创建节点
* 2. 销毁节点
* 3. 插入
* 4. 删除
*/

Node *getNewNode(int key){
Node * tmp = (Node*)malloc(sizeof(Node));
tmp->key = key;
tmp->h = 1;
tmp->lchild = NIL, tmp->rchild = NIL;
return tmp;
}

void clear(Node * root){
if(root == NIL) return;
clear(root->lchild);
clear(root->rchild);
free(root);
return;
}

//调整高度
void update_height(Node * root){
root->h = (H(L(root)) > H(R(root)) ? H(L(root)) : H(R(root))) + 1;
}

//左旋
Node * left_rotate(Node * root){
Node * tmp = root->rchild; //新根节点
root->rchild = tmp->lchild; //新左挂旧右
tmp->lchild = root; //旧根挂新左
update_height(root);
update_height(tmp);
return tmp;
}

//右旋
Node * right_rotate(Node * root){
Node * tmp = root->lchild; //新根
root->lchild = tmp->rchild; //新右成旧左
tmp->rchild = root; //旧根成新左
update_height(root);
update_height(tmp);
return tmp;
}

//调整
Node * maintain(Node * root){
//平衡调整代码
if(abs(H(L(root)) - H(R(root))) <= 1) return root;
if(root->lchild->h > root->rchild->h) {
//LR先小左旋
if(root->lchild->lchild->h < root->lchild->rchild->h)
root->lchild = left_rotate(root->lchild);
//LL大右旋
root = right_rotate(root);
} else {
//RL先小右旋
if(root->rchild->rchild->h < root->rchild->lchild->h)
root->rchild = right_rotate(root->rchild);
//RR大左旋
root = left_rotate(root);
}
return root;
}

Node * insert(Node * root, int key){
if(root == NIL) return getNewNode(key);
if(root->key == key) return root;
if(key < root->key) root->lchild = insert(root->lchild, key);
if(key > root->key) root->rchild = insert(root->rchild, key);
update_height(root);
return maintain(root);
}

//寻找前驱节点,默认传入度为2的节点,前父节点有左子树
Node * predeccessor(Node * root){
Node * tmp = root->lchild;
while(tmp->rchild) tmp = tmp->rchild;
return tmp;
}

Node * erase(Node * root, int key){
if(root == NIL) return NIL;
if(key < root->key) {
root->lchild = erase(root->lchild, key);
} else if(key > root->key) {
root->rchild = erase(root->rchild, key);
} else { //删除当前节点
if(root->rchild == NIL || root->lchild == NIL){
Node * tmp = root->rchild != NIL ? root->rchild : root->lchild;
free(root);
return tmp;
} else { // 删除度为2的节点
Node * tmp = predeccessor(root);
root->key = tmp->key;
root->lchild = erase(root->lchild, root->key);
}
}
update_height(root);
return maintain(root);
}

void print(Node * root){
printf("(%d[%d], %d, %d)\n",
root->key, root->h,
root->lchild->key,
root->rchild->key
);
}


void output(Node * root){
if(root == NIL) return;
print(root);
output(root->lchild);
output(root->rchild);
return ;
}

int main(int argc, char ** argv){
int op, val;
Node* root = NIL;
while(~scanf("%d%d", &op, &val)){
switch(op){
case 0: root = erase(root, val); break;
case 1: root = insert(root, val); break;
}
output(root);
printf("------------\n");
}
return 0;
}

-------------本文结束, 感谢您的阅读, 如有问题欢迎联系我-------------