C++:底层数据结构之二叉搜索树_c++容器底层通过二叉搜索树实现的

C++:底层数据结构之二叉搜索树

1. 二叉搜索树概念

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

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

2. 二叉搜索树的特性

特性:

1. 任意节点都比其左子树中所有节点大，比其右子树中所有节点小
2. 最左侧节点一定是最小的，最右侧节点一定是最大的
3. 中序遍历:可以得到一个有序序列

3. 二叉搜索树的操作

1. 二叉搜索树的查找
2. 二叉搜索树的插入
   插入的具体过程如下：
   a. 树为空，则直接插入
   b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
3. 二叉搜索树的删除 首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
   a. 要删除的结点无孩子结点
   b. 要删除的结点只有左孩子结点
   c. 要删除的结点只有右孩子结点
   d. 要删除的结点有左、右孩子结点
   看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
   情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
   情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
   情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题

4. 二叉搜索树的性能（插入、删除、查找）

• 二叉搜索树在进行所有操作时都要先查找该值域对应在二叉搜索树中的位置，因此查找的性能就代表了二叉搜索树的性能。
• 构建好二叉搜索树后，查找的最坏情况就是要查找的位置与二叉搜索树的高度一致。但这种情况没有考虑构建出的二叉搜索树的结构。
  
• 如果在向二叉搜索树中插入节点时，元素是有序或者元素接近有序的，则构建出的二叉树是一个只有右子树的单支树，则此时为最差情况时间复杂度为O(n)
  
• 因为左右子树的节点个数不一定平衡，因此map/set/multimap/multiset底层结构没有直接使用二叉搜索树，而是在二叉搜索树的基础上进行改进
• 改进目的:让二叉搜索树变成二叉树平衡树，从而提高查找的效率

5. 二叉搜索树的实现

BStree.h

#include<iostream>
using namespace std;
template<class T>//构建二叉树节点类模板
struct BSTNode
{
	BSTNode(const T& val = T())
		:left(nullptr)
		, right(nullptr)
		, data(val)
	{}
	BSTNode<T>* left;
	BSTNode<T>* right;
	T data;
};

template<class T>//构建二叉搜索树及其方法
class BSTree
{
	typedef BSTNode<T> Node;
public:
	BSTree()
		:root(nullptr)//初始化一个根节点
	{}

	~BSTree()
	{
		_DestroyBSTree(root);
	}
	Node* Find(const T& data)//查找一个数
	{
		Node* cur = root;
		while (cur)
		{
			if (data == cur->data)
				return cur;
			else if (data < cur->data)
				return cur->left;
			else
				return cur->right;
		}
		return nullptr;
	}

	bool Insert(const T& data)//插入一个数据
	{
		//如果是空树
		if (nullptr==root)
		{
			root = new Node(data);
			return true;
		}
		// 非空
		// 1.找待插入元素在树中的位置，并保存其双亲
		else
		{
			Node* cur = root;
			Node* parent = nullptr;
			while (cur)
			{
				parent = cur;//保存双亲
				if (data < cur->data)
					cur = cur->left;
				else if (data > cur->data)
					cur = cur->right;
				else
					return false;
			}
			//2.插入新节点
			cur = new Node(data);
			if (data < parent->data)
				parent->left = cur;
			else
				parent->right = cur;

			return true;
		}
	}

	void InOrder()
	{
		_InOrder(root);
		cout << endl;
	}

	bool Erase(const T& data)//删除一个数
	{
		//1.找待删除结点在树中的位置
		Node* cur = root;
		Node* parent = nullptr;
		while (cur)
		{
			if (data == cur->data)
				break;
			else if (data < cur->data)
			{
				parent = cur;
				cur = cur->left;
			}
			else
			{
				parent = cur;
				cur = cur->right;
			}
		}
		//如果树中没有待删除元素的对应节点
		if (nullptr == cur)
			return false;

		//2.已经找到待删除元素的位置，之后进行删除
		if (nullptr == cur->left)// cur只有右孩子或者cur是叶子节点
		{
			if (nullptr == parent)//cur一定是根节点
			{
				root = cur->right;
			}
			else
			{
				if (cur == parent->left)
					parent->left = cur->right;
				else
					parent->right = cur->right;
			}
		}
		else if (nullptr == cur->right)//cur只有左孩子或者cur是叶子节点
		{
			if (nullptr == parent)//cur一定是根节点
			{
				root = cur->left;
			}
			else
			{
				if (cur == parent->left)
					parent->left = cur->left;
				else
					parent->right = cur->left;
			}
		}
		else
		{
			// cur左右孩子均存在
			// 1. 在cur的子树中找一个替代节点---左右子树中查找均可
			//    一般情况下是在右子树中查找的
			//    左子树中查找时一定是最大的节点 || 最右侧节点
			//    右子树中查找时一定是最小的节点 || 最左侧节点
			Node* del = cur->right;
			parent = cur;

			while (del->left)
			{
				parent = del;
				del = del->left;
			}
			//2.将替代节点的值域交给待删除节点
			cur->data = del->data;

			//3.删除待删除结点
			if (del == parent->left)
				parent->left = del->right;
			else
				parent->right = del->right;

			cur = del;
		}
		delete cur;
		return true;
	}

private:
	void _InOrder(Node* pRoot)//中序遍历
	{
		if (pRoot)
		{
			_InOrder(pRoot->left);
			cout << pRoot->data << " ";
			_InOrder(pRoot->right);
		}
	}

	void _DestroyBSTree(Node*& pRoot)
	{
		if (pRoot)
		{
			_DestroyBSTree(pRoot->left);
			_DestroyBSTree(pRoot->right);
			delete pRoot;
			pRoot = nullptr;
		}
	}
private:
	Node* root;
};

int TestBSTree()
{
	int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
	BSTree<int> t;
	for (auto e : a)
	{
		t.Insert(e);
	}

	t.InOrder();
	cout << t.Find(5) << endl;

	t.Erase(8);
	t.InOrder();
	cout << t.Find(8) << endl;

	t.Erase(0);
	t.InOrder();

	t.Erase(1);
	t.InOrder();

	t.Erase(5);
	t.InOrder();
	return 0;
}
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

Test.cpp

#include<iostream>
#include<vld.h>
#include "BStree.h"
using namespace std;


int main()
{
	TestBSTree();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11