二叉树

二叉搜索树的原理

结构
二叉搜索树是能够高效进行如下操作的数据结构。

  • 插入一个数值
  • 查询是否包含某个数值
  • 删除某个数值
    二叉搜索树的例子

所有的节点,都满珠左子树上的所有节点都比自己小,而右子树上的所有节点都比自己大这一条件。

二叉搜索树能够高效地管理数的集合。

例如,可以通过如下方法在上图的二叉搜索树中查询是否存在10。

  • 根节点的数值是7,比10小,所有往右子节点走。
  • 走到的节点数值是15,比10大,所以往左子节点走。
  • 走到的节点是10,因此10在集合中。
    查找的例子

接下来,如何往树中插入新的数值呢?

如果我们按照查找数值的方法试图查找这个数值的节点,就可以知道其对应的节点的所在位置,之后再那个位置插入新的节点即可。例如,我们需要插入数值6。和查找的方法类似,从根节点出发,通过“左→右”两步,可知6应该是5的右儿子,因此在5的右儿子的位置插入6的节点即可。(图A)
最后是删除数值。数值的删除比起之前提到的操作稍微麻烦一些。例如,我们要删除数值15。如果删除了15所在的节点,你们它的两个儿子10和17就悬空了。于是,把11提到15所在的位置就可以解决问题。(图B)
插入与删除
一般来说,需要根据以下几种情况分别进行处理。

  • 需要删除的节点没有左儿子,那么就把右儿子提上去。
  • 需要删除的节点的左儿子没有右儿子,那么就把左儿子提上去。
  • 以上两种情况都不满足,就把左儿子的子孙中最大的节点提到需要删除的节点上。

复杂度
无论哪一种操作,所花的时间都和树的高度成正比。因此,如果一共有n个元素,那么平均每次操作需要O(logn)O(log n) 的时间。

实现

以下是二叉搜索树的一种实现方式

1
2
3
node *root = NULL;
root = insert(root,1);
find(root,1);

如上述代码,我们使用函数的返回值进行操作,
需要注意的是insert、delete返回的是node结构体的指针。

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
//表示节点的结构体
struct node{
int val;
node *lch, *rch;
};
//插入数值x
node *insert(node *p.int x){
if (p == NULL){
node *q = new node;
q->val = x;
q->lch = q->rch = NULL;
return q;
}
else{
if (x < p->val) p->lch = insert(p->lch, x);
else p->rch = insert(p->rch, x);
return p;
}
}
//查找数值x
bool find(node * p,int x){
if (p == NULL) return false;
else if (x == p->val) return true;
else if (x < p->val) return find(p->lch, x);
else return find(p->rch, x);
}
//删除数值x
node *remove(node * p.int x){
if (P == NULL) return NULL;
else if (x < p->val) p->lch = remove(p->lch, x);
else if (x > p->val) p->rch = remove(p->rch, x);
else if (p->lch == NULL){
node *q = p->rch;
delete p;
return q;
}
else if (p->lch->rch == NULL){
node *q = p->lch;
q->rch = p->rch;
delete p;
return q;
}
else{
node *q;
for(q = p -> lch;q -> rch -> rch != NULL;q -> rch);
node *r = q -> rch;
q -> rch = r -> lch;
r -> lch = p -> lch;
r -> rch = p -> rch;
delete p;
return r;
}
return p;
}

当然,也可以参考以下代码,更易于理解。

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
/*
二叉搜索树

中序遍历是 从 小 到 大

递归求树 高度 与 最大值
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
int data;
struct node* left;
struct node* right;
}Node;

typedef struct {
Node* root;
}Tree;

//构建二叉搜索树
void insert(Tree* tree,int value){
Node* node = (Node*)malloc(sizeof(Node));
node -> data = value;
node -> left = NULL;
node -> right = NULL;

if(tree -> root == NULL){ //如果是空树,则为根
tree -> root = node;
}
else{
Node* temp = tree -> root;
while (temp != NULL){
if(value < temp -> data){
if(temp -> left == NULL){
temp -> left = node;
return ;
}
else{
temp = temp -> left;
}
}
else{
if(temp -> right == NULL){
temp -> right = node;
return ;
}
else{
temp = temp -> right;
}
}
}
}
}

//求树的高度
int get_height(Node* node){
if(node == NULL) //递归出口
return 0;
else{
int left_h = get_height(node -> left);
int right_h = get_height(node -> right);
int max = left_h;
if(right_h > max){
max = right_h;
}
return max + 1;
}
}

//求二叉树最大值(常规)
int get_maximum(Node* node){
if(node == NULL){ //递归出口
return -1;
}
else{
int m1 = get_maximum(node -> left);
int m2 = get_maximum(node -> right);
int m3 = node -> data;
int max = m1;
if(m2 > max) max = m2;
if(m3 > max) max = m3;
return max;
}
}

int main(){
void preorder(Node* node); //先序遍历
void inorder(Node* node); //中序遍历
void postorder(Node* node); //后序遍历

int arr[7] = {6, 3, 8, 2, 5, 1, 7};

//建立空树
Tree tree;
tree.root = NULL;

for(int i = 0;i < 7;i++){
insert(&tree,arr[i]);
}

printf("%d\n",get_height(tree.root));
printf("%d\n",get_maximum(tree.root));

//通过遍历检测是否插入成功
// 6 3 2 1 5 8 7
// 1 2 3 5 6 7 8
// 1 2 5 3 7 8 6
preorder(tree.root);
printf("\n");
inorder(tree.root);
printf("\n");
postorder(tree.root);
printf("\n");

return 0;
}

//先序遍历
void preorder(Node* node){
if(node != NULL){
printf("%d ",node -> data);
preorder(node -> left);
preorder(node -> right);
}
}

//中序遍历
void inorder(Node* node){
if(node != NULL){
inorder(node -> left);
printf("%d ",node -> data);
inorder(node -> right);
}
}

//后序遍历
void postorder(Node* node){
if(node != NULL){
postorder(node -> left);
postorder(node -> right);
printf("%d ",node -> data);
}
}

编程语言的标准库

一样,实际上在许多情况下都不需要自己实现二叉搜索树,许多编程语言都在标准库里实现了简单易用的二叉搜索树。例如,在 C++ 中, STL 里有 setmap 容器。set是想前者叙述的一样使用二叉搜索树维护集合的容器,而 map 则是维护键与键对应的值的容器。

set例子

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
#include <cstdio>
#include <set>
using namespace std;
set<int> s; //声明
int main(){
//插入元素
s.insert(1);
s.insert(3);
s.insert(5);

//查找元素
set<int>::iterator ite;;
ite = s.find(1);
if(ite == s.end()) puts("not found");
else puts("found");

ite = s.find(2);
if(ite == s.end()) puts("not found");
else puts("found");

//删除元素
s.erase(3);

//其他的查找元素方法
if (s.count(3) != 0) puts("found");
else puts("not found");
//遍历
for(ite = s.begin();ite != s.end();++ite)
printf("%d\n",*ite);

return 0;
}

map例子

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
#include <cstdio>
#include <map>
#include <string>
using namespace std;
//声明(int为键,const char* 为值)
map<int,const char*> m;
int main(){
//插入元素
m.insert(make_pair(1,"ONE"));
m.insert(make_pair(10,"TEN"));
m[100] = "HUNDRED"; //其他写法

//查找元素
map<int,const char*>::iterator ite;
ite = m.find(1);
puts(ite -> second); //输出 ONE

ite = m.find(2);
if(ite == m.end()) puts("not found");
else puts(ite -> second);

puts(m[10]); //其他写法

//删除元素
m.erase(10);

//遍历
for(ite = m.begin();ite != m.end();++ite)
printf("%d:%s\n",ite -> first,ite -> second);

return 0;
}

此外,还有能存放重复键值的 multisetmultimap 等容器。

代码的实现

在理想情况下,它可以以O(logn)O(log n) 的复杂度完成一系列修改和查询,包括:

  • 插入一个数
  • 删除一个数
  • 查询某数的排名(排名定义为比该数小的数的个数+1)
  • 查询指定排名的数
  • 求某数的前驱(前驱定义为小于该数,且最大的数)
  • 求某数的后继(后继定义为大于该数,且最小的数)

维护一个有序的数组,配合二分查找,也可以实现这些操作,但插入和删除的复杂度是O(N)O(N) 。相对地,链表可以O(1)O(1) 插入和删除,但其他操作的复杂度不够优秀。二叉搜索树即BST对于以上每个操作,都拥有不差的复杂度。

例如,如果我们依次插入6、2、5、1、7、4、2、5、9、5,得到BST的结构如下:

显然,二叉搜索树是一个二叉树,每个节点对应的左子树中的所有数都小于它,右子树中的所有数都大于它。而且每个节点对应的左右子树也是二叉搜索树(这是一个天然递归的结构)。由于我们这里维护的是可重集,所以每个节点还带有额外信息,即该节点储存的数出现的次数。此外,为了方便查询排名,我们还保存每个子树的大小。

1
2
3
// L: 左子树根节点编号,R:右子树根节点编号,N:该节点储存的数出现的次数
// val:该节点储存的数,size:以该节点为根节点的子树的节点数目(即子树大小)
int L[MAXN], R[MAXN], N[MAXN], val[MAXN], size[MAXN], cnt = 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
void insert(int v, int pos = 1) // 插入
{
size[pos]++; // 树大小+1
if (N[pos] == 0 && L[pos] == 0 && R[pos] == 0) // 空节点
{
val[pos] = v;
N[pos] = 1;
}
else if (v < val[pos]) // 向左搜索
{
if (L[pos] == 0) // 如果应该向左搜,但不存在左节点,则创建一个新节点
L[pos] = ++cnt;
insert(v, L[pos]);
}
else if (v > val[pos]) // 向右搜索
{
if (R[pos] == 0)
R[pos] = ++cnt;
insert(v, R[pos]);
}
else // 已经存在值相同的节点
N[pos]++;
}

删除
这里直接采取惰性删除的方法:找到要删除的数,令其计数-1。这样写起来比较简单,不用进行较复杂的分类讨论,而且不会增加时间复杂度。

稍微注意一下,采取惰性删除时判断一个节点是不是空节点要用N[pos]==0 && L[pos]==0 && R[pos]==0而不能仅仅判断N,因为N[pos]==0的点也可能是被删除的中间节点。(注意被删除的叶子节点可以当作空节点处理)

1
2
3
4
5
6
7
8
9
10
void remove(int v, int pos = 1) // 删除
{
size[pos]--; // 树大小-1
if (v < val[pos])
remove(v, L[pos]);
else if (v > val[pos])
remove(v, R[pos]);
else
N[pos]--;
}

求排名
因为排名被定义为比某数小的数+1,所以我们直接实现两个函数countl和countg,用来求比某数小的数的数量和比某数大的数的数量。(这两个函数后面也会用到)

countl为例,我们递归地求。如果要找的值比当前节点小,则向左边搜;反之则向右边搜,但这时要加上size[L[pos]]+N[pos],因为左子树和根节点的所有数都比要找的数小;如果要找的值恰好等于当前节点,则直接返回左子树的大小。

1
2
3
4
5
6
7
8
9
int countl(int v, int pos = 1) // 求比某数小的数的个数
{
if (v < val[pos])
return L[pos] ? countl(v, L[pos]) : 0;
else if (v > val[pos])
return size[L[pos]] + N[pos] + (R[pos] ? countl(v, R[pos]) : 0);
else
return size[L[pos]];
}

countg完全类似。

1
2
3
4
5
6
7
8
9
int countg(int v, int pos = 1) // 求比某数大的数的个数
{
if (v > val[pos])
return R[pos] ? countg(v, R[pos]) : 0;
else if (v < val[pos])
return size[R[pos]] + N[pos] + (L[pos] ? countg(v, L[pos]) : 0);
else
return size[R[pos]];
}
1
2
3
4
int rank(int v)
{
return countl(v) + 1;
}

求指定排名的数
与上面的方法类似,每个节点处判断应该往左边还是右边找,递归地往下搜寻。

1
2
3
4
5
6
7
8
9
int kth(int k, int pos = 1) // 求指定排名的数
{
if (size[L[pos]] + 1 > k) // 答案在左,在左子树中找排名为k的数
return kth(k, L[pos]);
else if (size[L[pos]] + N[pos] < k) // 答案在右,在右子树中找排名为k - size[L[pos]] - N[pos]的数
return kth(k - size[L[pos]] - N[pos], R[pos]);
else
return val[pos];
}

注意,假如某个数的排名为2,且它出现了3次,那么这个函数传入2、3、4都会返回这个数,这也提供了一些方便。

求前驱
根据我们kth函数的性质,直接找到排名比当前数小1的那个数即可。

1
2
3
4
5
int pre(int v) // 求前驱
{
int r = countl(v);
return kth(r);
}

求后继
后继的排名则是小于等于当前数的数的数量+1。

1
2
3
4
5
int suc(int v) // 求后继
{
int r = size[1] - countg(v) + 1;
return kth(r);
}

待补充…

参考资料
正月点灯笼视频 二叉搜索树实现01二叉搜索树实现02
挑战程序设计竞赛(第2版)