当前位置： 首页 > article >正文

【二叉树进阶】二叉搜索树

article 2024/11/15 15:42:34

目录

1. 二叉搜索树概念

2. 二叉搜索树的实现

2.1 创建二叉搜索树节点

2.2 创建实现二叉搜索树

2.3 二叉搜索树的查找

2.4 二叉搜索树的插入

2.5 二叉搜索树的删除

2.6 中序遍历

2.7 完整代码加测试

3. 二叉搜索树的应用

3.1 K模型：

3.2 KV模型：

4. 二叉搜索树的性能分析

1. 二叉搜索树概念

二叉搜索树（BST，Binary Search Tree）：可以是一颗空树，满足以下性质：

  • 根节点的值大于左子树上所有节点的值，小于右子树上所有节点的值。
  • 它的左子树和右子树也分别为二叉搜索树。

它的中序遍历是有序的：0 1 2 3 4 5 6 7 8 9 ，所以也称为二叉排序树或二叉查找树。

2. 二叉搜索树的实现

int a[ ] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };

2.1 创建二叉搜索树节点

template<class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;
	//初始化节点
	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

2.2 创建实现二叉搜索树

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
    //操作实现
    //查找
    bool Find(const K& key) { }
    //插入
    void Insert(const K& key) { }
    //删除
    bool Erase() { }
    //中序遍历
    void InOrder() { }
private:
    Node* _root = nullptr;
}

2.3 二叉搜索树的查找

a、从根开始查找，比根大往右边查找，比根小往左边查找。

b、最多查找高度次，走到空，还没找到，则要查找的值不存在。

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

2.4 二叉搜索树的插入

a、如果树为空，新增节点，赋值给_root指针。

b、按搜索二叉树性质查找插入位置，插入节点。

c、要插入的位置一定为为空的位置，所以要插入，还要找到要插入位置的父节点，让父节点指向新插入的节点。

bool Insert(const K& key)
{
	//如果树为空，新增节点
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		//比根小
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		//比根大
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		//与根相等
		else
		{
			return false;
		}
	}
	cur = new Node(key);
	if (key < parent->_key)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	return true;
}

2.5 二叉搜索树的删除

a、先判断要删除的元素是否存在，不存在，返回false。

b、若存在，则分为以下情况:

  1. 要删除的节点（叶子节点）左右子树为空
  2. 要删除的节点左子树为空或右子树为空
  3. 要删除的节点左子树右子树都不为空

实际操作起来，情况1和情况2能合并到一起实现，只有两种情况：

  • 要删除的节点的左子树或右子树为空：直接删除-----让父亲指向要删除节点右子树（左子树），再直接删除该节点。

如果要删除的该节点为根，则直接让它的右子树（左子树）赋值给_root让它成为新根即可。

  • 要删除的节点的左右子树都不为空：替换法删除----在它的右子树中找到最小值（最左节点）或在左子树中找到最大值（最右节点），将它的值与要删除节点的值替换，这时就转换为该节点的删除问题。

右子树最左节点的左子树一定为空，左子树最右节点的右子树一定为空，这就转换为第一种情况的删除了。

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		//查找
		while (cur)
		{
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			//找到了 删除
			else
			{
				//1.要删除节点的左子树为空或者右子树为空
				if (cur->_left == nullptr)
				{
					//如果为根
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					//如果为根且右子树为空
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
				}
				//要删除的左右子树都不为空
				else
				{
					//这里找到是右子树的最左值
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;//要替换的节点
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}
					//替换法交换
					cur->_key = rightMin->_key;
					//转换成删除rightMin
					if (rightMin == rightMinParent->_right)
					{
						//rightMin的左子树一定为空
						rightMinParent->_right = rightMin->_right;
					}
					else
					{
						rightMinParent->_left = rightMin->_right;
					}
					delete rightMin;
				}
				//这里我们去找左子树的最大值
				//else
				//{
				//	Node* leftMaxParent = cur;
				//	Node* leftMax = cur->_left;
				//	while (leftMax->_right)
				//	{
				//		leftMaxParent = leftMax;
				//		leftMax = leftMax->_right;
				//	}
				//	//替换法删除
				//	cur->_key = leftMax->_key;
				//	//转换为删除leftMax
				//	if (leftMax == leftMaxParent->_left)
				//	{
				//		leftMaxParent->_left = leftMax->_left;
				//	}
				//	else
				//	{
				//		leftMaxParent->_right = leftMax->_left;
				//	}
				//	delete leftMax;
				//}
				return true;
			}
		}
		return false;
	}

2.6 中序遍历

中序遍历：按照左子树 根 右子树的方式迭代遍历二叉树。

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

总之，我们在实现二叉搜索树的时候一定要考虑多种情况，每种情况也要多找几个节点进行分析。

2.7 完整代码加测试

BSTree.hpp:

//创建二叉树节点
template<class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;
	//初始化节点
	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};
//创建实现二叉树
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	bool Insert(const K& key)
	{
		//如果树为空，新增节点
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			//比根小
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			//比根大
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			//与根相等
			else
			{
				return false;
			}
		}
		cur = new Node(key);
		if (key < parent->_key)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		return true;
	}
	//中序遍历
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		//查找
		while (cur)
		{
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			//找到了 删除
			else
			{
				//1.要删除节点的左子树为空或者右子树为空
				if (cur->_left == nullptr)
				{
					//如果为根
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					//如果为根且右子树为空
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
				}
				//要删除的左右子树都不为空
				else
				{
					//这里找到是右子树的最左值
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;//要替换的节点
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}
					//替换法交换
					cur->_key = rightMin->_key;
					//转换成删除rightMin
					if (rightMin == rightMinParent->_right)
					{
						//rightMin的左子树一定为空
						rightMinParent->_right = rightMin->_right;
					}
					else
					{
						rightMinParent->_left = rightMin->_right;
					}
					delete rightMin;
				}
				//这里我们去找左子树的最大值
				//else
				//{
				//	Node* leftMaxParent = cur;
				//	Node* leftMax = cur->_left;
				//	while (leftMax->_right)
				//	{
				//		leftMaxParent = leftMax;
				//		leftMax = leftMax->_right;
				//	}
				//	//替换法删除
				//	cur->_key = leftMax->_key;
				//	//转换为删除leftMax
				//	if (leftMax == leftMaxParent->_left)
				//	{
				//		leftMaxParent->_left = leftMax->_left;
				//	}
				//	else
				//	{
				//		leftMaxParent->_right = leftMax->_left;
				//	}
				//	delete leftMax;
				//}
				return true;
			}
		}
		return false;
	}
	bool Find(const K& key)
	{
		if (_root == nullptr)
		{
			return false;
		}
		Node* cur = _root;
		while (cur)
		{
			if (key < cur->_left)
			{
				cur = cur->_left;
			}
			else if (key > cur->_right)
			{
				cur = cur->_right;
			}
			else
			{
				return true;
			}
		}
		return false;
	}
private:
	Node* _root = nullptr;
};
void TestBSTree()
{
	BSTree<int> t;
	int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	for (auto e : a)
	{
		t.Erase(e);
		t.InOrder();
	}
}

Test.cpp:

#include"BSTree.hpp"
int main()
{
	TestBSTree();
	return 0;
}

运行结果：

3. 二叉搜索树的应用

3.1 K模型

K模型只有Key作为关键码，结构中只需要存储Key即可，关键码就是要搜索的值。

用途：判断Key在不在。

比如：给一个单词，判断该单词是否正确：

  • 以词库中所有单词集合中的每个单词作为key，构建一颗二叉搜索树
  • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

其实就是上面我们实现的二叉搜索树的查找。这里不在重复实现了。

3.2 KV模型

每一个关键码Key，都有与子对应的Value，即<Key,Value>的键值对。

用途：通过Key找对应的Value。

  • 比如：英汉词典就是英文与中文的对应关系，通过英文可以快速找到对应中文，英文单词与其中文构成<world，chinese>就构成一种键值对；
  • 比如：统计单词次数，统计成功后，给定单词可以快速找到其出现次数，单词与其出现次数<world，count>就构成一种键值对。

也很简单，其实就是让二叉搜索树中的节点多存一个值Value，查找、插入、删除等操作依旧是按照key去实现的。

改造二叉搜索树为KV结构模型：

template<class K,class V>
struct BSTreeNode
{
	BSTreeNode<K,V>* _left;
	BSTreeNode<K,V>* _right;
	K _key;
	V _value;//多存一个值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)
	{ }
	void _InOrder(Node* root)
	{ }
	void InOrder()
	{ }
	bool Erase(const K& key)
	{ }
	Node* Find(const K& key)//返回节点的指针，这里不再实现
	{ }
private:
	Node* _root = nullptr;
};

应用测试1：输入英文查找对应的中文

void TestBSTree()
{
	BSTree<string, string> dict;
	dict.Insert("string", "字符串");
	dict.Insert("tree", "树");
	dict.Insert("int", "整型");
	dict.Insert("search", "查找");
	dict.Insert("insert", "插入");
	string str;
	while (cin >> str)
	{
		BSTreeNode<string, string>* ret = dict.Find(str);
		if (ret == nullptr)
		{
			cout << "词库中无此单词" << endl;
		}
		cout << ret->_value << endl;
	}
}

结果：

应用测试2：查找水果出现的次数

void TestBSTree()
{
	string arr[] = { "苹果","香蕉","西瓜","西瓜","香梨","西瓜" ,"苹果" ,"西瓜" ,"西瓜" ,"香蕉" ,"苹果" };
	BSTree<string, int> t;
	int i = 0;
	for (auto e : arr)
	{
		BSTreeNode<string, int>* ret = t.Find(e);
		//ret为空说明要查找的是第一次出现
		if (ret == nullptr)
		{
			t.Insert(e, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	t.InOrder();
}

结果：

3.3 二叉搜索树的修改

二叉搜索树中Key是不能被修改的。

如果是KV模型的搜索树，可以修改Value，但是不能修Key

4. 二叉搜索树的性能分析

插入、删除操作都必须先查找，所有查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二
叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同（无序、接近有序），可能得到不同结构的二叉搜索树：

  • 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log2N（以2为底N的对数）。
  • 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N。
如果为单支树，二叉搜索树的性能就没有了，那么这种情况就要用到AVL树和红黑树了，后续再讲解。


http://www.kler.cn/a/308261.html

相关文章：

  • 排序算法 -快速排序
  • 城市轨道交通数据可视化的应用与优势
  • 深入解析贪心算法及其应用实例
  • arcgis做buffer
  • 缓存与数据库不一致的解决方案：深入理解与实践
  • 速盾：高防 CDN 和 CDN 的缓存机制都一样吗？
  • 视频格式转为mp4（使用ffmpeg）
  • 小程序面试题八
  • 【百日算法计划】：每日一题，见证成长（014）
  • 【SQL Server】清除日志文件ERRORLOG、tempdb.mdf
  • 如何快准稳 实现MySQL大表历史数据迁移？
  • linux文件系统权限详解
  • 服务器——装新的CUDA版本的方法
  • Web：HTTP包的相关操作
  • RocksDB系列一：基本概念
  • flink实战--如何基于java-agent技术增强Flink功能
  • 【Hot100】LeetCode—4. 寻找两个正序数组的中位数
  • 简单易懂的变动率指标ROC，做短线的快来了解一下
  • 超链接/表格/表单的复习（课后作业）
  • 蓝桥杯DS18B20程序源码
  • 【数据结构】4——树和森林
  • Mastering openFrameworks_第十一章_网络
  • 身份识别与服装类型检测系统源码分享
  • 基于微信小程序图书馆自习室座位预约小程序
  • USB组合设备——串口+鼠标+键盘
  • WPS生成目录