【C++进阶之路】第三篇：二叉搜索树 & kv模型-CSDN博客

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

文章目录

一、二叉搜索树

1.二叉搜索树概念

二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:

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

在这里插入图片描述

2.二叉搜索树操作

在这里插入图片描述

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

1二叉搜索树的查找

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

b、最多查找高度次走到到空还没找到这个值不存在。

2二叉搜索树的插入

插入的具体过程如下

a. 树为空则直接新增节点赋值给root指针

b. 树不空按二叉搜索树性质查找插入位置插入新节点

在这里插入图片描述

3二叉搜索树的删除

首先查找元素是否在二叉搜索树中如果不存在则返回否则要删除的结点可能分下面四种情况

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

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

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

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

看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下

  • 情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
  • 情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
  • 情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题–替换法删除

注意

  • 使用替换法删除我们通常替换所需删除节点右树中的最小节点即所需删除节点右树区域的最左节点。需要与被删除节点替换的节点可能左为空所以我们不能直接删除它我们还要多做一些工作–要考虑情况c发生的可能性做情况c一样的工作。

  • 使用替换法删除还要考虑根节点的删除问题根节点就是所需删除节点右树区域的最左节点
    在这里插入图片描述

3.二叉搜索树的实现

  • BSTree.h
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() = default; // 制定强制生成默认构造

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

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

		~BSTree()
		{
			Destroy(_root);
			//_root = nullptr;
		}

		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
				{
					// 删除
					// 1、左为空
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;

					} // 2、右为空
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else
					{
						// 找右树最小节点替代也可以是左树最大节点替代
						Node* pminRight = cur;
						Node* minRight = cur->_right;
						while (minRight->_left)
						{
							pminRight = minRight;
							minRight = minRight->_left;
						}

						cur->_key = minRight->_key;

						if (pminRight->_left == minRight) //考虑根节点做判断
						{
							pminRight->_left = minRight->_right; //正常节点
						}
						else
						{
							pminRight->_right = minRight->_right; //根节点
						}

						delete minRight;
					}

					return true;
				}
			}

			return false;
		}



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

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

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

			Destroy(root->_left);
			Destroy(root->_right);

			delete root;
			root = nullptr;
		}



	private:
		Node* _root = nullptr;
	};
}
  • Test.cpp
void TestBSTree1()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	key::BSTree<int> t1;

	for (auto e : a)
	{
		t1.Insert(e);
	}

	//t1.InOrder(t1.GetRoot());
	t1.InOrder();

	/*t1.Erase(7);
	t1.InOrder();

	t1.Erase(14);
	t1.InOrder();

	t1.Erase(3);
	t1.InOrder();*/

	t1.Erase(8);
	t1.InOrder();


	for (auto e : a)
	{
		t1.Erase(e);
		t1.InOrder();
	}

	t1.InOrder();
}


int main()
{
	TestBSTree1();

	return 0;
}

二、二叉搜索树的应用

1.kv模型

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

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

    • 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树

    • 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误

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

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

2.kv模型的实现

  • 改造二叉搜索树为KV结构
// 改造二叉搜索树为KV结构
namespace key_value
{
	// BinarySearchTree -- BSTree
	// SearchBinaryTree

	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:

		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
				{
					// 删除
					// 1、左为空
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;

					} // 2、右为空
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else
					{
						// 找右树最小节点替代也可以是左树最大节点替代
						Node* pminRight = cur;
						Node* minRight = cur->_right;
						while (minRight->_left)
						{
							pminRight = minRight;
							minRight = minRight->_left;
						}

						cur->_key = minRight->_key;

						if (pminRight->_left == minRight)
						{
							pminRight->_left = minRight->_right;
						}
						else
						{
							pminRight->_right = minRight->_right;
						}

						delete minRight;
					}

					return true;
				}
			}

			return false;
		}


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

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

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};
}
  • 测试用例
// 测试用例
void TestBSTree2()
{
	key_value::BSTree<string, string> dict;
	dict.Insert("sort", "排序");
	dict.Insert("left", "左边");
	dict.Insert("right", "右边");
	dict.Insert("string", "字符串");
	dict.Insert("insert", "插入");
	dict.Insert("erase", "删除");

	string str;
	while (cin >> str)
	{
		auto ret = dict.Find(str);
		if (ret)
		{
			cout << ":" << ret->_value << endl;
		}
		else
		{
			cout << "无此单词" << endl;
		}
	}
}

void TestBSTree3()
{
	string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };

	key_value::BSTree<string, int> countTree;
	for (auto str : arr)
	{
		//key_value::BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == nullptr)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}

	countTree.InOrder();
}

int main()
{
	TestBSTree3();

	return 0;
}

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

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

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

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

在这里插入图片描述

  • 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为log_2 N以2为底N的对数
  • 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N

结论如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优依据AVL树和红黑树的知识可以很好的解决这两个知识小编会在后续章节讲解此处先不做深入赘述。

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: c++
返回列表

上一篇：ASPICE项目实战-CSDN博客

下一篇：BES2700 蓝牙协议之RFCOMM通道使用方法-CSDN博客

“【C++进阶之路】第三篇：二叉搜索树 & kv模型-CSDN博客” 的相关文章

【C/C++】动态顺序表详解（附完整源码）1年前 (2023-02-02)
C++ 居然超过了 Python？1年前 (2023-02-02)
C/C++ noexcept NRVO1年前 (2023-02-02)
c/c++内存管理1年前 (2023-02-02)
【C++】STL容器：list的模拟实现1年前 (2023-02-02)
Conan：C/C++的依赖管理1年前 (2023-02-02)
c++入门篇之C++ 信号处理1年前 (2023-02-02)
蓝桥杯2019年第十届省赛C++B组1年前 (2023-02-02)
C/C++路面导航系统[2023-01-16]1年前 (2023-02-02)
（黑马C++）L09 C++类型转换 异常 输入输出流1年前 (2023-02-02)

阿里云国际版