概念
二叉搜索树（Binary Search Tree）是一种可以在 O(logN) 复杂度做查找，插入和删除的操作。
二叉搜索树是一种满足以下特殊性质的二叉树。
- 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值
- 若右子树不空，则右子树上所有结点的值均小于或等于它的根结点的值
- 左右子树均为二叉搜索树
二叉搜索树包含三种基本操作。其流程如下。
查找操作
- 若当前节点为 NULL，返回 false
- 若查找的值小于当前节点的值，则递归搜索左子树
- 若查找的值大于当前节点的值，则递归搜索右子树
- 若查找的值等于当前节点的值，则返回 true
插入操作
- 若当前节点为 NULL，用插入的值构建新节点插入到当前位置
- 若插入的值小于当前节点的值，则在左子树上执行插入操作
- 若插入的值大于当前节点的值，则在右子树上执行插入操作
删除操作
- 若当前节点为 NULL，返回 false
- 若删除的值小于当前节点的值，则在左子树上执行删除操作
- 若删除的值大于当前节点的值，则在右子树上执行删除操作
- 若删除的值等于当前节点的值，这里又分为多种情况
- 若当前节点左子树为空，则直接将右子树接上来
- 若当前节点右子树为空，则直接将左子树接上来
- 否则，查找左子树中最大的值（或者右子树中最小的值），与当前节点的值进行交换，然后删除被交换的节点，这里想一下就可以明白，左子树最大的数值移动到当前节点的位置，因为它是左子树中最大的数值，所以它一定大于左子树中其他值，同时也一定小于右子树中所有值，这样操作后仍然满足 BST 的性质。
根据二叉搜索树的性质，中序遍历二叉搜索树，得到的一定是一个有序的数列。所以用二叉搜索树进行排序，时间复杂度为 O(NlogN)
用法
以下内容来自洛谷日报
这样一种数据结构，支持找前驱与后继，还可以按排名与按数值查找
找前驱
所谓前驱，就是小于 x 的最大的数，所以前驱一定比 x 小
其实找前驱，就是从根节点开始，递归子树，如果你要找的数小于当前节点，就找他的左子树，反之找他的右子树，直到没有可以找的为止。
按排名找值
再节点维护一个 size 信息，表示当前位置开始的树的节点数量，则找排名为 k 的节点，先看左子树的 size+1 是否大于等于 k，若大于，则在左子树中查找 排名为 k-1 的节点。否则，查询右树中排名为 k-size-1 的节点。
按值找排名
按值找排名时，从根开始，如果该位置的值小于要查询的值，就找他的右子树，同时记住他左子树的大小，如果小于，就查询他的左子树，直到大小相等，他的排名就是该点左子树的大小加上一路上比他小的节点个数再加上 1。
代码
以下是 BST 基础功能的 C++ 实现的代码:
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <bitset>
#include <cstdlib>
#include <cmath>
#include <set>
#include <list>
#include <deque>
#include <map>
#include <queue>
#include <sstream>
using namespace std;
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100;
template <typename T>
struct node
{
T val;
node *lch, *rch;
node(T val) : val(val), lch(NULL), rch(NULL) {}
};
template <typename T>
struct bst
{
typedef node<T> node;
private:
node *root;
public:
bst() : root(NULL) {}
bool insert(const T &val)
{
return _insert(root, val);
}
bool _insert(node *&root, const T &val)
{
if (root == NULL)
{
root = new node(val);
return true;
}
if (val < root->val)
{
return _insert(root->lch, val);
}
else
{
return _insert(root->rch, val);
}
}
bool find(T val)
{
return _find(root, val);
}
bool _find(node *root, const T &val)
{
if (root == NULL)
{
return NULL;
}
else if (val < root->val)
{
return _find(root->lch);
}
else if (val > root->val)
{
return _find(root->rch);
}
else
{
return root;
}
}
bool remove(T val)
{
return _remove(root, val);
}
bool _remove(node *&root, T val)
{
if (root == NULL)
{
return false;
}
else if (val < root->val)
{
return _remove(root->lch, val);
}
else if (val > root->val)
{
return _remove(root->rch, val);
}
else
{
if (root->lch == NULL)
{
node *del = root;
root = root->rch;
delete del;
return true;
}
else if (root->rch == NULL)
{
node *del = root;
root = root->lch;
delete del;
return true;
}
else
{
node *rightMin = root->rch->lch;
while (rightMin)
{
rightMin = rightMin->lch;
}
swap(root->val, rightMin->val);
_remove(root->rch, rightMin->val);
return true;
}
}
}
void output()
{
_output(root);
}
void _output(node *root)
{
if (root == NULL)
{
return;
}
_output(root->lch);
cout << root->val << endl;
_output(root->rch);
}
};
int main()
{
bst<int> b;
b.insert(1);
b.insert(3);
b.insert(2);
b.insert(10);
b.insert(8);
b.remove(2);
b.insert(4);
b.remove(3);
b.output();
}
|