首页 > 其他分享 >【二叉树进阶】二叉搜索树

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

时间：2024-09-17 17:20:08浏览次数：12  
标签：进阶 cur 二叉 right 二叉树 key else left

目录

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树和红黑树了，后续再讲解。

标签：进阶,cur,二叉,right,二叉树,key,else,left
From： https://blog.csdn.net/2202_75924820/article/details/142304420

相关文章

  • Maven笔记（二）：进阶使用
    Maven笔记（二）-进阶使用一、Maven分模块开发分模块开发对项目的扩展性强，同时方便其他项目引入相同的功能。将原始模块按照功能拆分成若干个子模块，方便模块间的相互调用，接口共享(类似Jar包一样之间引用、复用)。开发步骤：创建Maven项目书写模块代码分模块开发需要先针对......
  • Leetcode 297. 二叉树的序列化与反序列化
    1.题目基本信息1.1.题目描述序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序......
  • 代码随想录算法训练营，9月17日 | 669. 修剪二叉搜索树，108.将有序数组转换为二叉搜索树，5
    669.修剪二叉搜索树题目链接：669.修剪二叉搜索树文档讲解︰代码随想录(programmercarl.com)视频讲解︰修剪二叉搜索树日期：2024-09-17想法：节点为空返回空，值在中间时，继续递归左右两边，小于时递归右子树，大于时递归左子树Java代码如下：classSolution{publicTreeNodetrimBST......
  • 数据结构-树和二叉树
      树和二叉树 1.树的概念   树tree     是n(n>=0)个节点的有限集    在任意的一个非空树中       (1)有且仅有一个特定的被称为根(root)的节点       (2)当n>1时,其余的节点可分为m(m>0)个互不相交的有限......
  • Docker 进阶篇-CIG 重量级监控系统
    上一篇讲的是轻量级的监控工具，本文就来讲重量级的：CAdvisor+InfluxDB+Granfana，简称CIG。​‍‍dockerstats原生的Docker命令中，stats可以查看每个容器占用的CPU，内存，网络流量等情况：CONTAINERIDNAMECPU%MEMUSAGE/LIMITMEM%NETI/O......
  • 代码随想录算法 - 二叉树7
    题目1669.修剪二叉搜索树给你二叉搜索树的根节点root，同时给定最小边界low和最大边界high。通过修剪二叉搜索树，使得所有节点的值在[low,high]中。修剪树不应该改变保留在树中的元素的相对结构(即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在唯一的答案......
  • Java数据存储结构——二叉查找树
    文章目录22.1.2二叉查找树22.1.2.1概述22.1.2.1二叉查找树添加节点22.1.2.2二叉查找树查找节点22.1.2.3二叉树遍历22.1.2.4二叉查找树的弊端22.1.2二叉查找树22.1.2.1概述二叉查找树,又称二叉排序树或者二叉搜索树二叉查找树的特点：每一个节点上最多有两个......
  • Day17 二叉树part07| LeetCode 235. 二叉搜索树的最近公共祖先 ，701.二叉搜索树中的插
    235.二叉搜索树的最近公共祖先235.二叉搜索树的最近公共祖先利用二叉搜索树的特性——有序树，可知，如果中间节点是p和q的公共节点，那个中间节点的数值一定在[p,q]区间因此，从根节点往下搜索，遇到的第一个位于[p,q]或[q,p]区间的节点就是最近公共祖先classSolution{......
  • c++入门（七万字心得体会！！）分上下两篇（初阶+进阶）
    目录c++入门c++关键字命名空间命名空间定义命名空间使用c++输入输出缺省参数缺省参数概念缺省参数分类函数重载函数重载概念c++支持函数重载原理--名字修饰（name）引用引用概念引用特性常引用使用场景传值，传引用效率对比引用和指针的区别内联函数概念特性a......
  • leetcode刷题day20|二叉树Part08（669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索
    669.修剪二叉搜索树思路：理解了删除二叉搜索树中的节点，这个题理解起来就不难了。还是选用中序遍历递归。递归三步曲：1、传入参数：根节点，最小值，最大值；返回值为根节点；2、终止条件：如果节点为空，直接返回空；3、递归逻辑：如果最小值小于该节点，递归调用该节点的右孩子（检查右孩子......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99