[数据结构C++实现]二叉搜索树

一、二叉搜索树

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

最多查找高度次（前提：树要均衡）O(logN)

最坏O（N）

O(N / 2)还是O(N) —— 所以还是有些问题，解决方案——平衡搜索二叉树：AVLTree，RBTree

二、二叉搜索树基本框架

template <class K> // key关键字：比较数据大小
struct BSTreeNode // BinarySearchTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;
};

template <class K>
struct BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{}

private:
	Node* _root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三、二叉搜索树实现

3.1 非递归版本

插入
在这里插入图片描述

bool Insert(const K& key) // 非线性一般不叫push
{
	// 返回值意义：一般来说搜索树是不允许有重复元素了，有重复元素不让重复插入
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		// 找到空位置进行插入
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	// 走到空，就可以链接了
	cur = new Node(key);
	if (parent->_key < key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return ture;
}
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

删除

没有孩子的节点
在这里插入图片描述
只有一个孩子的节点

有两个孩子的节点

并且最右节点(一定右为空)或者最左节点(一定左为空)

删除只有一个孩子节点的情况：
在这里插入图片描述
父亲会不会为空？——会，只有根节点父亲会为空

让root指向cur的孩子

有两个孩子的节点：要么找右子树最左节点或者是左子树最右节点

若删除5：
在这里插入图片描述
若删除7：不要给空：Node* minParent = nullptr;，不然min父节点为空，之后又会出错

bool Erase(const K& key)
{
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			// 找到了，准备开始删除
			// 画图理解
			if (cur->_left == nullptr)
			{
				if (parent == nullptr)
				{
					_root = cur->_right;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->_right = cur->_right;
					}
				}
				delete cur;
			}
			else if (cur->_right == nullptr)
			{
				if (parent == nullptr)
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}
				}
				delete cur;
			}
			else
			{
				// 左右都不为空
				// 找右树最左节点
				// 不要给空：Node* minParent = nullptr;
				Node* minParent = cur;
				Node* min = cur->_right;
				while (min->_left)
				{
					minParent = min;
					min = min->_left;
				}
				cur->_key = min->_key;

				if (minParent->_left == min)
				{
					minParent->_left = min->_left;
				}
				else
				{
					minParent->_right = min->_right;
				}
				delete min;
			}
			return true;
		}
	}
	return false;
}
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

3.2 递归版本

递归可能会爆栈

插入
在这里插入图片描述

bool _InsertR(Node*& root, const K& key) // root必须加引用
{
	if (root == nullptr)
	{
		root = new Node(key);
		return true;
	}
	if (root->_key < key)
	{
		return _InsertR(root->_right, key); // 如这里，下一层的root就是这一层root->_right的别名，是要进行修改的
	}
	else if (root->_key > key)
	{
		return _InsertR(root->_left, key);
	}
	else
	{
		return false;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

删除
在这里插入图片描述

bool _EraseR(Node*& root, const K& key)
{
	if (root == nullptr)
	{
		return false;
	}
	if (root->_key < key)
	{
		return _EraseR(root->_right, key);
	}
	else if (root->_key > key)
	{
		return _EraseR(root->_left, key);
	}
	else
	{
		Node* del = root;
		if (root->_left == nullptr)
		{
			root = root->_right;
		}
		else if (root->_right == nullptr)
		{
			root = root->_left;
		}
		else
		{
			// 左右都不为空
			Node* min = root->_right;
			while (min->_left)
			{
				min = min->_left;
			}
			swap(min->_key, root->_key);
			// 递归到右子树去删除
			return _EraseR(root->_right, key); // 这里就已经删除了，防止和下面在删除一次，所以要直接return
		}
		delete del;
		return true;
	}
}
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

并且也不怕parent为空的情况
在这里插入图片描述

在这里插入图片描述

四、二叉搜索树的应用

4.1 K(key)搜索模型

通俗来说就是判断在不在
上述代码我们实现的就是K模型，只存一个值

namespace K
{
	template <class K> // key关键字：比较数据大小
	struct BSTreeNode // BinarySearchTreeNode
	{
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;

		// new需要他的构造函数
		BSTreeNode(const K& key)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}
	};

	template <class K>
	struct BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}
		bool Insert(const K& key) // 非线性一般不叫push
		{
			// 返回值意义：一般来说搜索树是不允许有重复元素了，有重复元素不让重复插入
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				// 找到空位置进行插入
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
			// 走到空，就可以链接了
			cur = new Node(key);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}

		bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return true;
				}
			}
			return false;
		}

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					// 找到了，准备开始删除
					// 画图理解
					if (cur->_left == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
					}
					else
					{
						// 左右都不为空
						// 找右树最左节点
						// 不要给空：Node* minParent = nullptr;
						Node* minParent = cur;
						Node* min = cur->_right;
						while (min->_left)
						{
							minParent = min;
							min = min->_left;
						}
						cur->_key = min->_key;

						if (minParent->_left == min)
						{
							minParent->_left = min->_left;
						}
						else
						{
							minParent->_right = min->_right;
						}
						delete min;
					}
					return true;
				}
			}
			return false;
		}
		Node* _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
			{
				return root;
			}
		}
		Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}

		bool _InsertR(Node*& root, const K& key) // root必须加引用
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}
			if (root->_key < key)
			{
				return _InsertR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key);
			}
			else
			{
				return false;
			}
		}
		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}
		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}
			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _EraseR(root->_left, key);
			}
			else
			{
				Node* del = root;
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					// 左右都不为空
					Node* min = root->_right;
					while (min->_left)
					{
						min = min->_left;
					}
					swap(min->_key, root->_key);
					// 递归到右子树去删除
					return _EraseR(root->_right, key); // 这里就已经删除了，防止和下面在删除一次，所以要直接return
				}

				delete del;
				return true;
			}
		}
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}
		void InOrder() // 为了外部测试函数可以直接调用，如果直接写下面的，root是私有，调用不到
		{
			_InOrder(_root);
			cout << endl;
		}
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
	private:
		Node* _root;
	};
}
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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287

4.2 KV(key value)搜索模型

通过一个值查找另外一个值
中英字典——中英互译
身份证，往卡里面写入数据

namespace KV
{
	template <class K, class V> // key关键字：比较数据大小,value表示值
	struct BSTreeNode // BinarySearchTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;

		// new需要他的构造函数
		BSTreeNode(const K& key, const V& value)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			,_value(value)
		{}
	};

	template <class K, class V>
	struct BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}
		bool Insert(const K& key, const V& value) // 非线性一般不叫push
		{
			// 返回值意义：一般来说搜索树是不允许有重复元素了，有重复元素不让重复插入
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				// 找到空位置进行插入
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
			// 走到空，就可以链接了
			cur = new Node(key, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}

		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					// 找到了，准备开始删除
					// 画图理解
					if (cur->_left == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
					}
					else
					{
						// 左右都不为空
						// 找右树最左节点
						// 不要给空：Node* minParent = nullptr;
						Node* minParent = cur;
						Node* min = cur->_right;
						while (min->_left)
						{
							minParent = min;
							min = min->_left;
						}
						cur->_key = min->_key;
						cur->_value = min->_value;

						if (minParent->_left == min)
						{
							minParent->_left = min->_left;
						}
						else
						{
							minParent->_right = min->_right;
						}
						delete min;
					}
					return true;
				}
			}
			return false;
		}

		void InOrder() // 为了外部测试函数可以直接调用，如果直接写下面的，root是私有，调用不到
		{
			_InOrder(_root);
			cout << endl;
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << " " << root->_value << " ";
			_InOrder(root->_right);
		}

	private:
		Node* _root;
	};

	void TestBSTree1()
	{
		// 字典中英互译
		BSTree<string, string> dict; // value可以是容器
		dict.Insert("sort", "排序");
		dict.Insert("left", "左边");
		dict.Insert("right", "右边");
		dict.Insert("map", "地图、映射");

		string str;
		while (cin >> str)
		{
			BSTreeNode<string, string>* ret = dict.Find(str);
			if (ret)
			{
				cout << "对应中文解释:" << ret->_value << endl;
			}
			else
			{
				cout << "没有对应解释" << endl;
			}
		}
	}

	void TestBSTree2()
	{
		// 统计水果出现从次数
		string arr[] = { "苹果", "西瓜","草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		BSTree<string, int> countTree;
		for (auto& str : arr)
		{
			BSTreeNode<string, int>* ret = countTree.Find(str);
			if (ret != nullptr)
			{
				ret->_value++;
			}
			else
			{
				countTree.Insert(str, 1);
			}
		}
		// 按key排序
		countTree.InOrder();
	}
}
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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244

从底层来看
set —— key模型的搜索树
map —— KV模型的搜索树（插入的pair，可以理解为是一个结构体）
1
2
3

4.3 排序+去重

实现中已经提到过

五、二叉搜索树性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树
若二叉搜索树是有序，则退化为单支，性能和链表就没什么区别了
这样子就没什么用了，因此需要弄出两个树才能解决——AVL、红黑树
2^30 ≈ 10亿

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2

相关阅读:
OpenCV之cvtColor颜色空间转换
 Android悬浮窗实现源码-悬浮球转盘&悬浮加速小火箭效果&悬浮播放视频图片
 Linux内存管理（二十七）：shrink_list 详解(2)
学网络安全怎么挖漏洞？怎么渗透？
[管理与领导-123]：IT人看清职场中的隐性规则 - 19 - 管理者激发团队拿到结果的方式和层次不同，你愿意跟随哪一种类型的领导？
寻找链表相交结点问题
 以科技传递温度，vivo亮相数字中国建设峰会
 c 语言基础：L1-049 天梯赛座位分配
 python学习手册
 zk系列三：zookeeper实战之分布式锁实现
原文地址：https://blog.csdn.net/weixin_51304981/article/details/126071712