2020/7/15
学习内容：
二叉树查找树原理和实现：
二叉查找树是特殊的二叉树，其中左子树的key值都小于根节点key值，右子树key值都大于根节点key值，对于每个子树，也是一颗二叉查找树。
二叉树查找树的构建：
1
2
3
4
5
6
7
8
9
10
11
12
| typedef struct Node{
int key;
int data;
struct Node *lchild, *rchild;
}node;
node *getNewNode(int key) {
node *p = (node *)malloc(sizeof(node));
p->key = key;
p->lchild = p->rchild = NULL;
return p;
}
|
二叉树查找树的插入：
1
2
3
4
5
6
7
8
| //返回插入后的根节点
node *insert(node *root, int key) {
if (root == NULL) return getNewNode(key);
if (root->key == key) return root;
if (root->key > key) root->lchild = insert(root->lchild, key);
else root->rchild = insert(root->rchild, key);
return root;
}
|
二叉查找树的销毁：
1
2
3
4
5
6
7
| void clear(node *root) {
if (root == NULL) return;
clear(root->lchild);
clear(root->rchild);
free(root);
return;
}
|
二叉树查找树的删除：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| //返回删除后的根节点
node *erase(node *root, int key) {
if (root == NULL) return NULL;
if (key < root->key) {
root->lchild = erase(root->lchild, key);
} else if (key > root->key) {
root->rchild = erase(root->rchild, key);
} else {
if (root->lchild == NULL || root->rchild == NULL) {
node *p = root->lchild ? root->lchild : root->rchild;
free(p); //均为NULL时，p为NULL
return p;
} else {
node *p = predecessor(root);//找到root的前驱节点
root->key = p->key;
root->child = erase(p, p->key);//删除前驱节点
}
}
}
|
AVL树原理和实现：
AVL树通过左右子树的相对高度来判断树是否平衡，根据失衡的情形可以分为四种情况。
LL，LR，RL，RR。
AVL树的构建：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #define K(n) ((n) ? (n)->key : 0)
#define H(n) ((n) ? (n)->h : 0)
#define R(n) ((n) -> rchild)
#define L(n) ((n) -> lchild)
typedef struct Node{
int key;
int data;
int h; //用于保存树高的信息
struct Node *lchild, *rchild;
}node;
node *getNewNode(int key) {
node *p = (node *)malloc(sizeof(node));
p->key = key;
p->rchild = p->lchild = NULL;
p->h = 1;
return p;
}
|
AVL树的插入
1
2
3
4
5
6
7
8
9
| //返回插入后的根节点
node *insert(node *root, int key) {
if (root == NULL) return getNewNode(key);
if (root->key == key) return root;
if (root->key > key) root->lchild = insert(root->lchild, key);
else root->rchild = insert(root->rchild, key);
update_height(root);
return maintain(root);
}
|
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
| //更新树的高数
//取左右子树中最高的加1
void update_height(node *root) {
root->h = (H(L(root)) > H(R(root)) ? H(L(root)) : H(R(root))) + 1;
return;
}
//AVL树的调整 返回调整之后的根节点
node *maintain(node *root) {
if (abs(H(L(root)) - H(R(root))) <= 1) return root; //不需要调整
if (H(L(root)) > H(R(root))) { //L型调整，LL右旋，LR先左旋后右旋
if (H(R(L(root))) > H(L(L(root)))) {//LR型
root->lchild = left_rot(root->lchild);
}
root = right_rot(root);
} else {
if (H(L(R(root))) > H(R(R(root)))) {//LR型
root->rchild = right_rot(root->rchild);
}
root = left_rot(root);
}
}
//左旋
node *left_rot(node *root) {
node *p = root->rchild;
root->rchild = p->lchild; //左孩子变右孩子
p->lchild = root;
update_height(root);
update_height(p);
return p;
}
//右旋
node *right_rot(node *root) {
node *p = root->lchild;
root->lchild = p->rchild;
p->rchild = root;
update_height(root);
update_height(p);
return p;
}
|
