数据结构进阶 二叉搜索树

作者：@小萌新
专栏：@数据结构进阶
作者简介：大二学生 希望能和大家一起进步！
本篇博客简介：介绍二叉搜索树并且模拟实现之

二叉搜索树的概念

二叉搜索树应当具有下面的性质

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

如下图

这就是一颗二叉搜索树

我们将其中序遍历 由于二叉搜索树的性质 得到的一定是有序的数组

节点类

为了符合C++的封装性 我们这里首先要建立一个节点类

看看上面的二叉搜索树我们就能看出来这个树需要的成员变量有哪些

一个左指针 一个右指针 还有一个就是我们的节点值

我们只需要完成一个构造函数就好

代码表示如下

template<class T>
class BSnode
{
public:
	BSnode<T>* _left;  // 左指针
	BSnode<T>* _right; // 右指针
	T _key;           // 节点值

	BSnode(const T& key = 0)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我们可以创建一个节点看看

BSnode<int>* p = new BSnode<int>(10);
1

我们可以发现没有问题

二叉搜索树类

私有成员

这里的成员和二叉树一样 只需要一个_root(根节点)就可以

代码表示如下

template<class T>
class BSTree
{
	typedef BSnode<T> Node
public:

	// 成员函数
private:
	Node* _root;
};
1
2
3
4
5
6
7
8
9
10

构造函数

我们想要构造出一颗新的二叉搜索树类 只要构造出一个空的根节点就好

代码表示如下

	BSTree()
		:_root(nullptr)
	{}
1
2
3

拷贝构造函数

为了以让代码更加简洁 同时也更加容易阅读和理解 我们这里使用一个子函数来完成拷贝构造 （一般来说子函数要私有化 这里为了方便就不进行私有化了）

子函数写的也很简单 分别拷贝根节点 左右子树就好了

	Node* _BSTree(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}

		Node* copynode = new Node(root->_key); // 拷贝根节点
		copynode->_left = _BSTree(root->_left);
		copynode->_right = _BSTree(root->_right);

		return copynode;
	}

	BSTree(const Node& t)
	{
		_root = _BSTree(t._root);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

赋值运算符重载函数

传统写法

我们要使用赋值运算符重载 只需要将给我们的树复制一份就可以

	// 赋值运算符重载 传统写法 
	const Node& operator = (const Node& t)
	{
		if (this != &t) 
		{			
		    this->_Destory(_root);
			_root = _BSTree(t._root);
		}
		return *this
	}
1
2
3
4
5
6
7
8
9
10

这里要注意的是 我们的那个if 条件 是为了防止自己给自己赋值

现代写法

	const Node& operator = (Node& t)
	{
		swap(_root, t._root);
		return *this;
	}
1
2
3
4
5

我们知道的是 形参是实参的一份临时拷贝 出作用域之后会自动析构

那么我们就可以利用这个性质 直接交换两个树的根节点

这样子就完成了 代码很简洁

析构函数

二叉树的析构函数其实就是后序遍历加上delete

至于为什么要后序遍历呢？ 因为只有这样子才不会破坏二叉树的结构

	void _Destory(Node* root)
	{
		if (root == nullptr) // 遍历到空节点之后就不管了
		{
			return;
		}
		_Destory(root->_left);
		_Destory(root->_right);
		delete root;
	}
	// 析构函数
	~BSTree()
	{
		_Destory(_root); // 释放二叉树
		_root = nullptr;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

插入函数

这里和堆的插入差不多 我们只要理清楚二叉搜索树的概念 分两种情况讨论

1. 假如是空树 那么插入的节点就作为它的根节点
2. 假如不是空树 那么久按照二叉搜索树的性质进行插入

那么 什么是二叉搜索树的性质呢？

1. 若待插入结点的值小于根结点的值，则需要将结点插入到左子树当中。
2. 若待插入结点的值大于根结点的值，则需要将结点插入到右子树当中。
3. 若待插入结点的值等于根结点的值，则插入结点失败。

之后按照这个性质 递归或循环实现 知道最后的值是空或者和插入的值相同则结束

非递归实现

首先我们要使用一个Cur指针来寻找到空或者是相同的那个位置

如果找到相同的值 则我们插入失败 返回一个false

如果找到空之后我们就准备开始链接

但是与此同时 我们还不知道父节点在哪里 因此我们要需要创建一个Parent指针来记录父节点的位置

	// 插入
	bool Insert(const T& key)
	{
		// 这里就写完了根节点为空的情况
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;

		// 开始找空或相同值
		while (cur)
		{
			// 如果找到了相同的值 则插入失败 
			if (key == cur->_key)
			{
				return false;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				parent = cur;
				cur = cur->_right;
			}
		}

		// 开始新节点 然后判断插入哪边
		cur = new Node(key);

		if (key < parent->_key)
		{
			parent->_left = cur;
			return true;
		}
		else
		{
			parent->_right = cur;
			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
42
43
44
45
46
47

这样子我们就完成了插入操作 那么 我们应该怎么验证我们的插入操作呢？

这个时候就用到了我们上面的性质 即中序遍历后它应该是有序的

那么我们首先写出一个中序遍历的代码

	void _Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_Inorder(root->_left);
		cout << root->_key << endl;
		_Inorder(root->_right);
	}


	void Inorder()
	{
		_Inorder(_root);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

那么我们现在随机插入十个数 再用中序遍历 看看是否是升序排列的

代码和显示效果如下

	BSTree<int> b1;
	b1.Insert(3);
	b1.Insert(5);
	b1.Insert(9);
	b1.Insert(10);
	b1.Insert(1);
	b1.Insert(4);
	b1.Insert(8);
	b1.Insert(7);
	b1.Insert(2);
	b1.Inorder();
1
2
3
4
5
6
7
8
9
10
11

我们可以发现 符合预期

递归实现

递归实现的写法很简单 但是理解起来有点难 大家先看代码

	bool _InsertR(Node*& root, const T& key) // 注意这里root的引用 很重荣
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

		if (key == root->_key)
		{
			return false;
		}
		else if (key < root->_key)
		{
			return _InsertR(root->_left, key);
		}
		else
		{
			return _InsertR(root->_right, key);
		}
	}

	bool Insert(const T& key)
	{
		return _InsertR(_root, key);
	}
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

因为上面的参数是引用 所以说像上面的

  root->_left
1

实际上就是root的别名 因此我们对于root赋值时候 实际上就是对于它赋值

right同理

这就是递归连接的技巧

之后我们再来验证下

删除函数

删除和插入一样 也是分两种情况讨论

1. 假设没有找到我们要删除的数 则返回false表示删除失败
2. 假设找到要删除的节点了 则要在删除完毕后还要符合二叉搜索树性质的条件下删除之

要满足条件二 则有需要满足下面三个条件之一

1. 删除节点的左子树为空
2. 删除节点的右子树为空
3. 删除节点的左右子树均不为空

接下来我们对于这三种情况分别讨论下解决方案

删除节点的左子树为空

当我们要删除的节点的左子树为空的时候 （包含其右子树也为空的情况）

我们可以直接将要删除节点的parent和它的右孩子连接 （右孩子为空也成立）

之后删除掉要删除的节点就可以

删除节点的右子树为空

和上面左子树为空的情况类似 我们只需要连接父节点和子节点就好

左右节点都不为空

这是删除中最麻烦的一步

这里我们使用的方法叫做替换法

即我们可以将让待删除结点左子树当中值最大的结点 或是待删除结点右子树当中值最小的结点代替待删除结点被删除

然后将待删除结点的值改为代替其被删除的结点的值即可

接下来我们来看代码

非递归实现

	//删除函数
	bool Erase(const T& key)
	{
		Node* parent = nullptr; //标记待删除结点的父结点
		Node* cur = _root; //标记待删除结点
		while (cur)
		{
			if (key < cur->_key) //key值小于当前结点的值
			{
				//往该结点的左子树走
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key) //key值大于当前结点的值
			{
				//往该结点的右子树走
				parent = cur;
				cur = cur->_right;
			}
			else //找到了待删除结点
			{
				if (cur->_left == nullptr) //待删除结点的左子树为空
				{
					if (cur == _root) //待删除结点是根结点，此时parent为nullptr
					{
						_root = cur->_right; //二叉搜索树的根结点改为根结点的右孩子即可
					}
					else //待删除结点不是根结点，此时parent不为nullptr
					{
						if (cur == parent->_left) //待删除结点是其父结点的左孩子
						{
							parent->_left = cur->_right; //父结点的左指针指向待删除结点的右子树即可
						}
						else //待删除结点是其父结点的右孩子
						{
							parent->_right = cur->_right; //父结点的右指针指向待删除结点的右子树即可
						}
					}
					delete cur; //释放待删除结点
					return true; //删除成功，返回true
				}
				else if (cur->_right == nullptr) //待删除结点的右子树为空
				{
					if (cur == _root) //待删除结点是根结点，此时parent为nullptr
					{
						_root = cur->_left; //二叉搜索树的根结点改为根结点的左孩子即可
					}
					else //待删除结点不是根结点，此时parent不为nullptr
					{
						if (cur == parent->_left) //待删除结点是其父结点的左孩子
						{
							parent->_left = cur->_left; //父结点的左指针指向待删除结点的左子树即可
						}
						else //待删除结点是其父结点的右孩子
						{
							parent->_right = cur->_left; //父结点的右指针指向待删除结点的左子树即可
						}
					}
					delete cur; //释放待删除结点
					return true; //删除成功，返回true
				}
				else //待删除结点的左右子树均不为空
				{
					//替换法删除
					Node* minParent = cur; //标记待删除结点右子树当中值最小结点的父结点
					Node* minRight = cur->_right; //标记待删除结点右子树当中值最小的结点
					//寻找待删除结点右子树当中值最小的结点
					while (minRight->_left)
					{
						//一直往左走
						minParent = minRight;
						minRight = minRight->_left;
					}
					cur->_key = minRight->_key; //将待删除结点的值改为minRight的值
					//注意一个隐含条件：此时minRight的_left为空
					if (minRight == minParent->_left) //minRight是其父结点的左孩子
					{
						minParent->_left = minRight->_right; //父结点的左指针指向minRight的右子树即可
					}
					else //minRight是其父结点的右孩子
					{
						minParent->_right = minRight->_right; //父结点的右指针指向minRight的右子树即可
					}
					delete minRight; //释放minRight
					return true; //删除成功，返回true
				}
			}
		}
		return false; //没有找到待删除结点，删除失败，返回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
88
89
90

递归实现

递归实现的版本和非递归实现的版本实际差别就是在查找这一步 在其他步骤上并无不同 所以我们直接写出以下代码

//递归删除函数的子函数
	bool _EraseR(Node*& root, const T& key)
	{
		if (root == nullptr) //空树
			return false; //删除失败，返回false

		if (key < root->_key) //key值小于根结点的值
			return _EraseR(root->_left, key); //待删除结点在根的左子树当中
		else if (key > root->_key) //key值大于根结点的值
			return _EraseR(root->_right, key); //待删除结点在根的右子树当中
		else //找到了待删除结点
		{
			if (root->_left == nullptr) //待删除结点的左子树为空
			{
				Node* del = root; //保存根结点
				root = root->_right; //根的右子树作为二叉树新的根结点
				delete del; //释放根结点
			}
			else if (root->_right == nullptr) //待删除结点的右子树为空
			{
				Node* del = root; //保存根结点
				root = root->_left; //根的左子树作为二叉树新的根结点
				delete del; //释放根结点
			}
			else //待删除结点的左右子树均不为空
			{
				Node* minParent = root; //标记根结点右子树当中值最小结点的父结点
				Node* minRight = root->_right; //标记根结点右子树当中值最小的结点
				//寻找根结点右子树当中值最小的结点
				while (minRight->_left)
				{
					//一直往左走
					minParent = minRight;
					minRight = minRight->_left;
				}
				root->_key = minRight->_key; //将根结点的值改为minRight的值
				//注意一个隐含条件：此时minRight的_left为空
				if (minRight == minParent->_left) //minRight是其父结点的左孩子
				{
					minParent->_left = minRight->_right; //父结点的左指针指向minRight的右子树即可
				}
				else //minRight是其父结点的右孩子
				{
					minParent->_right = minRight->_right; //父结点的右指针指向minRight的右子树即可
				}
				delete minRight; //释放minRight
			}
			return true; //删除成功，返回true
		}
	}
	//递归删除函数（方法）
	bool EraseR(const T& key)
	{
		return _EraseR(_root, key); //删除_root当中值为key的结点
	}
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

查找函数

这个就很好实现了 因为不管是我们上面的插入还是删除 再最前面都是用到的查找

并且是递归非递归版本都用到了 所以这里就直接写代码了

非递归实现

//查找函数
Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (key < cur->_key) //key值小于该结点的值
		{
			cur = cur->_left; //在该结点的左子树当中查找
		}
		else if (key > cur->_key) //key值大于该结点的值
		{
			cur = cur->_right; //在该结点的右子树当中查找
		}
		else //找到了值为key的结点
		{
			return cur; //查找成功，返回结点地址
		}
	}
	return nullptr; //树为空或查找失败，返回nullptr
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

递归实现

//递归查找函数的子函数
Node* _FindR(Node* root, const K& key)
{
	if (root == nullptr) //树为空
		return nullptr; //查找失败，返回nullptr

	if (key < root->_key) //key值小于根结点的值
	{
		return _FindR(root->_left, key); //在根结点的左子树当中查找
	}
	else if (key > root->_key) //key值大于根结点的值
	{
		return _FindR(root->_right, key); //在根结点的右子树当中查找
	}
	else //key值等于根结点的值
	{
		return root; //查找成功，返回根结点地址
	}
}
//递归查找函数
Node* FindR(const K& key)
{
	return _FindR(_root, key); //在_root当中查找值为key的结点
}

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

二叉搜索树的性能分析

因为不管是二叉搜索树的哪个操作 实际上都会用到查找这一步 所以说二叉搜索树的性能一般来说就是查找的性能

在二叉搜索树是一颗完全二叉树的情况下 它的性能是最好的 此时它的效率为 logN

在二叉搜索树是一颗近似单边树的情况下 它的性能是最差的 此时它的效率为 N