0%

二叉搜索树

二叉排序树

基础知识

名称 : 二叉排序树, 二叉搜索树

性质 :

  1. 左子树 < 根节点
  2. 右子树 > 根节点

用途 : 解决与排名有关的检索需求

插入过程 : 根据插入节点值和根节点比较, 选择左子树或右子树继续比较, 最终放在叶子节点上

删除过程 :

  1. 删除叶子节点

    直接删除

  2. 删除度为1的节点

    把孩子交给祖父节点

  3. 删除度为2的节点

    中序遍历 : 10 17 20 28 29 30 32

    性质 : 待删除节点的前驱无右子树, 后继无左子树, 因此前驱后继一定不是度为2的节点

    将前驱或后继直接覆盖待删除节点后, 问题转换为删除叶子节点或者是度为1的节点

优化 :

  1. 删除掉处理度为0的代码逻辑,不影响代码整体功能
  2. 解决排名相关的检索需求,修改二叉搜索树的定义,增加size字段,记录每棵树的节点数目
    1. K == LS - 1 : 根节点就是排名第k的元素
    2. k <= LS : 排名第k位的元素在左子树中
    3. k > LS : $search_k(root->rchild, k - LS - 1)$
  3. 解决 top-k 问题,输出前k位的元素(找到小于第k位的所有元素)
    1. 根节点就是第k位元素, 输出左子树所有节点和根节点值
    2. 第k位元素在左子树中, 前k位元素全部在左子树中
    3. 第k位元素在右子树中, 说明左子树中的所有节点和根节点都是前k位元素
  4. 二叉排序树和快速排序的关系
    1. 二叉排序树是快速排序的逻辑结构
    2. 思考1: 快速排序算法的时间复杂度和二叉排序树建树时间复杂度之间的关系
    3. 思考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
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
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
using namespace std;

#define KEY(n) (n ? n->key : 0)
#define SIZE(n) (n ? n->size : 0)
#define L(n) (n ? n->lchild : 0)

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

/*
* 二叉搜索树的若干操作:
* 1. 创建节点
* 2. 销毁节点
* 3. 查找
* 4. 插入
* 5. 删除
*/

/*
* 优化1: 将删除度为0和度为1的节点的代码合并
* 优化2: 实现查找第k位的元素
* 优化3: 实现输出前k位的元素(TOP-K)
*/

//更新树高
void update_size(Node * root){
root->size = SIZE(root->lchild) + SIZE(root->rchild) + 1;
}

//创建节点
Node * getNewNode(int key){
Node *p = (Node *)malloc(sizeof(Node));
p->key = key;
p->size = 1;
p->lchild = nullptr, p->rchild = nullptr;
return p;
}

//销毁树
void clear(Node * root){
if(root == nullptr) return;
clear(root->lchild);
clear(root->rchild);
free(root);
return;
}

//查找
int search(Node* root, int val){
if(root == nullptr) return 0;
if(root->key == val) return 1;
if(root->key > val) return search(root->lchild, val);
if(root->key < val) return search(root->rchild, val);
return 0;
}

//查找第k大的元素
int search_k(Node * root, int k){
if(root == nullptr) return -1;
if(SIZE(L(root)) == k - 1) return root->key;
if(k <= SIZE(L(root))) {
return search_k(root->lchild, k);
} else {
return search_k(root->rchild, k - SIZE(L(root)) - 1);
}
}

//插入
Node * insert(Node * root, int val){
if(root == nullptr) return getNewNode(val);
if(root->key == val) return root;
if(val < root->key) root->lchild = insert(root->lchild, val);
if(val > root->key) root->rchild = insert(root->rchild, val);
update_size(root);
return root;
}

//寻找前驱(默认父节点有左孩子)
Node * predecessor(Node * root){
Node * tmp = root->lchild;
while(tmp->rchild != nullptr) tmp = tmp->rchild;
return tmp;
}

//删除节点
Node * erase(Node * root, int val){
if(root == nullptr) return nullptr;
if(root->key > val)
root->lchild = erase(root->lchild, val);
else if(root->key < val)
root->rchild = erase(root->rchild, val);
else { //删除节点本身
//删除度为0的节点和度为1的节点操作相同
if(root->lchild == nullptr || root->rchild == nullptr){
Node * tmp = root->lchild ? root->lchild : root->rchild;
free(root);
return tmp;
} else { //删除度为2的节点
Node * tmp = predecessor(root);
root->key = tmp->key;
root->lchild = erase(root->lchild, tmp->key);
}
}
update_size(root);
return root;
}

//输出整棵树的所有节点 - 中序
void output(Node * root){
if(root == nullptr) return;
output(root->lchild);
printf("[%d, %d, %d, size : %d]\n",KEY(root),KEY(root->lchild),KEY(root->rchild),SIZE(root));
output(root->rchild);
return;
}

//输出前k个节点
void output_k(Node *root, int k){
if(k == 0 || root == nullptr) return;
if(k <= SIZE(L(root))){
output_k(root->lchild, k);
} else {
output(root->lchild);
printf("[%d, %d, %d, size : %d]\n",KEY(root),KEY(root->lchild),KEY(root->rchild),SIZE(root));
output_k(root->rchild, k - SIZE(L(root)) - 1);
}
return;
}


int main(int argc, char ** argv){

int op, val;

/* op :
* 0 查找
* 1 插入
* 2 删除
* 3 查找第k位的元素
* 4 输出前k位的元素
*/
Node * root = nullptr;
while(~scanf("%d%d", &op, &val)){
switch(op){
case 0: printf("search %d, result : %d\n", val, search(root, val)); break;
case 1: root = insert(root, val); break;
case 2: root = erase(root, val); break;
case 3: printf("search k %d, result : %d\n",val, search_k(root, val)); break;
case 4: {
printf("output top-%d elements\n",val);
output_k(root, val);
printf("----------------\n");
} break;
}
if(op != 0 && op != 4){
output(root);
printf("----------------\n");
}
}

return 0;
}

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