首页 > 编程语言 >C++：二叉搜索树进阶

C++：二叉搜索树进阶

时间：2024-10-31 12:46:14浏览次数：3  
标签：right return 进阶 cur C++ 二叉 key root left

文章目录

前言

前面我们学习的二叉搜索树迭代的版本，今天我们来学习递归的版本~

递归版本在结构，以及遍历等这些地方都是一样的，最大的区别就在于插入和删除，代码量会简单很多。

在这里插入图片描述

一、二叉搜索树的查找（递归版本）

在这里插入图片描述

代码如下：

bool _FindR(Node* root, const K& key)
{
	if (root == nullptr)
	{
		return false;
	}

	if (key < root->_key)
	{
		return _FindR(root->_left, key);
	}
	else if (key > root->_key)
	{
		return _FindR(root->_right, key);
	}
	else
	{
		return true;
	}
}

但是这样还有一个问题，同样就是外部_root我们调不到，就无法递归了，因此我们可以包一层：

bool _FindR(const K& key)
{
	return _FindR(_root, key);
}

二、二叉树搜索树的插入（递归版本）

在这里插入图片描述

代码如下：

bool InsertR(const K& key)
{
	return InsertR(_root, key);
}

bool InsertR(Node*& root, const K& key)
{
	if (root->_key == nullptr)
	{
		root = new Node(key);
		return true;
	}

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

三、二叉搜索树的删除（递归版本）

在这里插入图片描述

bool EraseR(const K& key)
{
	return EraseR(_root, key);
}

bool EraseR(Node*& root, const K& key)
{
	if (root == nullptr)
	{
		return false;
	}

	if (key < root->_key)
	{
		return EraseR(root->_left, key);
	}
	else if (key > root->_key)
	{
		return EraseR(root->_right, key);
	}
	else
	{
		Node* del = root;
		if (root->_left == nullptr)
		{
			root = root->_right;
		}
		else if (root->_right == nullptr)
		{
			root = root->_left;
		}
		else
		{
			Node* left_Max = root->_left;
			while (left_Max->_right)
			{
				left_Max = left_Max->_right;
			}

			swap(root->_key, left_Max->_key);

			EraseR(root->_left, key);

		}

		delete del;
		return true;
	}
}

四、析构函数

~BSTree()
{
	Destroy(_root);
}

递归去删除：
这里要注意的是，删除的时候要使用后序遍历！

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

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}

五、拷贝构造

BSTree(const BSTree<K>& t)
{
	_root = Copy(t._root);
}

同样，递归去拷贝：

Node* Copy(Node* root)
{
	if (root == nullptr)
		return nullptr;

	Node* copyroot = new Node(root->_key);
	copyroot->_left = Copy(root->_left);
	copyroot->_right = Copy(root->_right);
	return copyroot;
}

六、赋值重载

直接使用现代写法：

BSTree<K>& operator= (BSTree<K> t)
{
	swap(_root, t._root);
	return *this;
}

七、代码总结

这里总结了递归版本以及非递归版本的代码总和：

namespace key
{
	template<class K>
	struct BSTreeNode
	{
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;

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

	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}

		BSTree(const BSTree<K>& t)
		{
			_root = Copy(t._root);
		}

		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}

		~BSTree()
		{
			Destroy(_root);
		}

		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 (parent->_right == cur)
							{
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}
					}// 右为空
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_right == cur)
							{
								parent->_right = cur->_left;
							}
							else
							{
								parent->_left = cur->_left;
							}
						}
					} // 左右都不为空 
					else
					{
						// 找替代节点
						Node* parent = cur;
						Node* leftMax = cur->_left;
						while (leftMax->_right)
						{
							parent = leftMax;
							leftMax = leftMax->_right;
						}

						swap(cur->_key, leftMax->_key);

						if (parent->_left == leftMax)
						{
							parent->_left = leftMax->_left;
						}
						else
						{
							parent->_right = leftMax->_left;
						}

						cur = leftMax;
					}

					delete cur;
					return true;
				}
			}

			return false;
		}

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

		bool FindR(const K& key)
		{
			return _FindR(_root, key);
		}

		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}

		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}

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

			Node* copyroot = new Node(root->_key);
			copyroot->_left = Copy(root->_left);
			copyroot->_right = Copy(root->_right);
			return copyroot;
		}

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

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}

		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
				return false;

			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _EraseR(root->_left, key);
			}
			else
			{
				Node* del = root;

				// 1、左为空
				// 2、右为空
				// 3、左右都不为空
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_right)
					{
						leftMax = leftMax->_right;
					}

					swap(root->_key, leftMax->_key);

					return _EraseR(root->_left, key);
				}

				delete del;
				return true;
			}
		}

		bool _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}

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

		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return false;

			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
			{
				return true;
			}
		}

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

			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
	private:
		Node* _root;
	};

八、二叉搜索树性能对比

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

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

在这里插入图片描述

  • 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为： l o g 2 N log_2 N log2​N
  • 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为： N 2 \frac{N}{2} 2N​

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上场了。

九、key_value模型

  1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

  • 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

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

  1. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：

  • 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对

  • 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

这里我们要改的也就是模板参数初始化和插入，其他都不变。

namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _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:
		BSTree()
			:_root(nullptr)
		{}

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

		Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}

		bool InsertR(const K& key, const V& value)
		{
			return _InsertR(_root, key, value);
		}

		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}

	private:
		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
				return false;

			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _EraseR(root->_left, key);
			}
			else
			{
				Node* del = root;

				// 1、左为空
				// 2、右为空
				// 3、左右都不为空
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_right)
					{
						leftMax = leftMax->_right;
					}

					swap(root->_key, leftMax->_key);

					return _EraseR(root->_left, key);
				}

				delete del;
				return true;
			}
		}

		bool _InsertR(Node*& root, const K& key, const V& value)
		{
			if (root == nullptr)
			{
				root = new Node(key, value);
				return true;
			}

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

		Node* _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return nullptr;

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

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

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root;
	};

	void TestBSTree1()
	{
		//BSTree<string, Date> carTree;

		BSTree<string, string> dict;
		dict.InsertR("insert", "插入");
		dict.InsertR("sort", "排序");
		dict.InsertR("right", "右边");
		dict.InsertR("date", "日期");

		string str;
		while (cin >> str)
		{
			BSTreeNode<string, string>* ret = dict.FindR(str);
			if (ret)
			{
				cout << ret->_value << endl;
			}
			else
			{
				cout << "无此单词" << endl;
			}
		}
	}

	void TestBSTree2()
	{
		// 统计水果出现的次数
		string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		BSTree<string, int> countTree;
		for (auto& str : arr)
		{
			auto ret = countTree.FindR(str);
			if (ret == nullptr)
			{
				countTree.InsertR(str, 1);
			}
			else
			{
				ret->_value++;
			}
		}

		countTree.InOrder();
	}
}

总结

到这里二叉搜索树的内容就都结束啦，接下来我们需要学习有关于AVL树以及红黑树的知识，以此解决二叉搜索树效率不稳定的问题。

创作不易，求求观众老爷多多支持

标签：right,return,进阶,cur,C++,二叉,key,root,left
From： https://blog.csdn.net/Jdxxwu/article/details/143377655

相关文章

  • 南沙C++信奥赛陈老师解一本通题 1345：【例4-6】香甜的黄油
    ​ 【题目描述】农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1≤N≤500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。农夫John很狡猾。像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时......
  • VSCode进阶之路
    VSCode进阶之路：从入门到高效率开发......
  • LUOGU_进阶算法思想
    进阶算法思想单调数据结构单调队列，单调栈都是均摊\(O(1)\)，是不支持撤销的，只能按照正常过程加入。单调栈求最近的大于小于其的值CF280BMaximumXorSecondary：枚举最大值，次大值并不容易确定，但枚举次大值的位置，这样最大值就是其左右两边第一个比其大的值，用单调栈可求出。其实就......
  • LUOGU_进阶数据结构
    LUOGU_进阶数据结构二叉堆P10977CuttheSequence：因为DP的值是单调递增的，所以可能的决策点只有最远的合法位置与那些后缀最大值段的左端点，用单调队列+可删除堆（懒标记）做。如果\(\exista<0\)，怎么做？CDQ优化DP，可以做！！并查集P10350ModernizacjaBajtocji：把二选一的居民放进一......
  • CMDB平台（进阶篇）：CMDB的应用场景剖析
    配置管理数据库（ConfigurationManagementDatabase，简称CMDB）是IT服务管理（ITSM）中的核心组件。随着信息技术的快速发展，大型企业的IT环境变得越来越复杂，为了更好地管理和维护这些复杂的IT基础设施，近些年来国内CMDB平台越来越多，如乐维CMDB、华为CMDB等。CMDB不仅是一个存储系统，用于记录......
  • 奥数与C++小学四年级（第十五题 希望数）
    参考程序代码：#include<iostream>#include<vector>usingnamespacestd;//每个数字所需的火柴棍数量vector<int>matchsticks={6,2,5,5,4,5,6,3,7,6};//函数来计算一个数的火柴棍总数和数字和voidcheckHopeNumber(intnumber){inttotalMatchst......
  • ​Leetcode 166.珠宝的最高价值​ 网格图dp C++实现
    问题：Leetcode166.珠宝的最高价值现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：只能从架子的左上角开始拿珠宝每次可以移动到右侧或下侧的相邻位置到达珠宝架子的右下角时，停止拿取注意：珠宝的价值都是大于0的。除非这个......
  • 新手逆向实战三部曲之三——通过进入关键call追码注册软件（进阶）
    教程开始：通过前两次的学习，是不是感觉逆向也蛮有意思的呢，感兴趣的同学可以先看看前二次的内容再继续向下学习新手逆向实战三部曲之一新手逆向实战三部曲之二有了上次爆破的基础，这次便省力了许多，这次从载入开始，虽前头的几个步骤与之前相同，温故而知新嘛（也可直接往后看）用OD......
  • c++ string 识别标志位并解析标志位后面的字符
    解析字符串中的固定标志位正则表达式和iterator的配合应用#include<string>#include<map>#include<regex>#include<iostream>//替换\\M+后面的字符//\\M+195B6替换为文std::regexpattern(R"(\\M+[^\\M]*)");//匹配\\M+后跟任意非\\M的字符（0次或多次）......
  • C++多线程应用
    一个进程就是一个程序，一个程序里不止一个功能，每个功能的实现就可以交给一个线程去完成。一个进程就像是一个工程，这个工程里，有设计，有监理，有施工，就相当于三个线程，各干各的又相互配合。https://cplusplus.com/reference/thread/thread/thread/是C++的官方参考，个人觉得比较权威，比经......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99