二叉搜索树（BST,Binary Search Tree）

  • 开发
  • 24

目录

前言

一、二叉搜索树概念

二、二叉搜索树的实现与操作

1.查找

2.插入

3.删除

4.中序遍历 

5.完整代码 

三、二叉搜索树的应用（K模型、KV模型）

1.K模型

2.KV模型

3.完整代码

四、二叉搜索树的性能分析

前言

为何学？

1.二叉搜索树是一种树形结构，是一种查找效率非常高的结构，值得我们去学习

2.map和set的底层也是二叉搜素树，学习二叉搜索树可以让我们更好的了解set和map的特性

一、二叉搜索树概念

二叉搜索树（BST,Binary Search Tree）又称二叉排序树、二叉查找树

它可以是一颗空树

如果不是，它（或者说它的任何一颗子树）必须满足下列条件：

1.如果它的左子树不为空，则左子树上的所有节点值都小于根节点的值

2.如果它的右子树不为空，则右子树上的所有节点值都大于根节点的值

3.左、右子树都是二叉搜索树 

二、二叉搜索树的实现与操作

节点结构

template<class K>
struct BSTreeNode
{
	typedef BSTreeNode<K> Node;

	Node* _left;
	Node* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

树类

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	bool Insert(const K& key){}
    bool Find(const K& key){}
    bool Erase(const K& key){}
    void _InOrder(Node* root){}

    void InOrder()
    {
	    _InOrder(root);
    }
private:
	Node* root = nullptr;
};

 

1.查找

从根开始查找比较，比当前根值大往右边查找，比当前根值大往右边查找，且最多查找高度次，走到空还未找到，则所查找值不存在

代码实现：

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;
}

2.插入

1.如果为空树，则将创建新节点，并将新节点赋值给根节点（root指针）

2.如果树不为空，则按二叉搜索树的性质先查找插入位置，再插入

bool Insert(const K& key)
{
	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;
}

3.删除

在二叉搜索树中删除是一个稍显麻烦的事，其中包含了许多细节

我们可以知道，待删除的节点有四种情景：

1.要删除的结点无孩子结点

2.要删除的结点只有左孩子结点

3.要删除的结点只有右孩子结点

4.要删除的结点有左、右孩子结点

 在后面的处理中1情景和23情景可以融合，因此去掉1情景，我们有3种情景

  • 情景2：使待删除节点的父节点指向待删除节点的左孩子，删除待删除节点
  • 情景3：使待删除节点的父节点指向待删除节点的右孩子，删除待删除节点 
  • 情景4：

这里我们事用替换法删除--即在待删除节点的子树中找一个合适的替换节点，用它的值替换填补调待删除节点，可以找左子树的最大值或者右子树的最小值 ，在处理替换节点的子树问题

下面的演示代码找的树右子树的最小值替换：

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 (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					if (cur == parent->_right)
					{
						parent->_right = cur->_right;
					}
					else
					{
						parent->_left = cur->_right;
					}
				}

				delete cur;
				return true;
			}
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (cur == parent->_right)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}
				}

				delete cur;
				return true;
			}
			else
			{
				// 替换法
				Node* rightMinParent = cur;
				Node* rightMin = cur->_right;
				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}

				cur->_key = rightMin->_key;

				if (rightMin == rightMinParent->_left)
					rightMinParent->_left = rightMin->_right;
				else
					rightMinParent->_right = rightMin->_right;

				delete rightMin;
				return true;
			}
		}
	}

	return false;
}

4.中序遍历 

既然二叉搜索树能叫做二叉排序树，自然是有原因的，在二叉搜索树中，对二叉搜索树来一次中序遍历，即可得到一组有序元素

 在C++的类中，不能直接调用递归函数，需要嵌套一层递归

void InOrder()
{
	_InOrder(_root);
	cout << endl;
}
void _InOrder(Node* root)
{
	if (root == nullptr)
		return;

	_InOrder(root->_left);
	cout << root->_key << " ";
	_InOrder(root->_right);
}

5.完整代码 

template<class K>
struct BSTreeNode
{
	typedef BSTreeNode<K> Node;

	Node* _left;
	Node* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	
	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}

	bool Insert(const K& key)
	{
		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 (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}

					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}

					delete cur;
					return true;
				}
				else
				{
					// 替换法
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					if (rightMin == rightMinParent->_left)
						rightMinParent->_left = rightMin->_right;
					else
						rightMinParent->_right = rightMin->_right;

					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}

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

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

		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;
};

三、二叉搜索树的应用（K模型、KV模型）

1.K模型

K模型中只有一个key值作为关键码，只存储key值 

如我们要在一个词库中搜索一个单词 “key”，我们只需要以这个词库的每一个单词作为key值构建二叉搜索树，再在这个树中查找key值为“key”的节点

2.KV模型

KV模型中的每一个key值都有一个对应的value值（也叫映射），即<Key,Value>键值对

如我们平时学习上经常用到的英汉词典，每个英文都对应着中文，英文单词与其对应的<Word,Chinese>就构成了一种键值对

下面就是上述K模型代码改造的KV模型代码

3.完整代码

template<class K, class V>
struct BSTreeNode
{
	typedef BSTreeNode<K, V> Node;

	Node* _left;
	Node* _right;
	K _key;
	V _value;

	BSTreeNode(const K& key, const V& value)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
		, _value(value)
	{}
};

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	bool Insert(const K& key, const V& value)
	{
		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 (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}

					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}

					delete cur;
					return true;
				}
				else
				{
					// 替换法
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_key = rightMin->_key;

					if (rightMin == rightMinParent->_left)
						rightMinParent->_left = rightMin->_right;
					else
						rightMinParent->_right = rightMin->_right;

					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}

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

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;
};

四、二叉搜索树的性能分析

根据上面的介绍我们可以知道，无论是删除还是插入，都需要先查找到需要处理的位置，因此，查找效率代表了二叉搜索树的各个操作额性能

对于一个有n个节点的二叉搜索树，查找的平均长度差不多就是二叉搜索树的深度，节点越深，次数越多。

插入次序不同，得到的二叉搜索树的结构可能不同，比如下图：

对于较好的情况参考上面的左图，二叉树为完全二叉树或者说接近完全二叉树，查找的平均次数为log n 

对于较差的情况参考上面的右图，二叉搜索树退化成单只树或者说接近单只树，查找的平均次数为n

若是退化为单只树，二叉搜索树就失去了它的性能优势

要想二叉搜索树的性能不管怎样插入都能达到最优，请继续学习后面大佬们发明的AVL树和红黑树，在那里你可以找到所要的答案

阅读全部

相关推荐

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-06-07 04:00:01       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-06-07 04:00:01       101 阅读

  9. 在Django里面运行非项目文件

    2024-06-07 04:00:01       82 阅读

  19. Python语言-面向对象

    2024-06-07 04:00:01       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-06-07 04:00:01       85 阅读

热门阅读

  3. 分账能为电商平台带来哪些便捷？

    2024-06-07 04:00:01       27 阅读

  5. HElib 使用样例

    2024-06-07 04:00:01       28 阅读

  11. YT-DLP 超好用的开源视频下载工具

    2024-06-07 04:00:01       33 阅读

  16. python 滑雪小游戏代码

    2024-06-07 04:00:01       26 阅读

  18. 设计模式-状态模式

    2024-06-07 04:00:01       20 阅读

  19. 图像处理知识积累

    2024-06-07 04:00:01       26 阅读

  21. 非阻塞IO

    2024-06-07 04:00:01       34 阅读

  23. tcpdump

    2024-06-07 04:00:01       30 阅读