首页 > 其他分享 >二叉搜索树详解

二叉搜索树详解

时间:2024-06-30 20:59:33浏览次数:18  
标签:right cur parent 二叉 详解 搜索 key else left

一、二叉搜索树的概念

二叉搜索树又名二叉排序树以及二叉查找树,它是一颗空树或者是具有以下性质的二叉树

*若它的左子树不为空,则左子树上所有节点的值都小于根节点的值

*若它的右子树不为空,则右子树上所有节点的值都大于根节点的值

*它的左右子树分别为二叉搜索树。

二、基本操作

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

1、二叉树的查找

a、从根节点开始查找,比根大的值往右边走查找,比根值小则往左边查找。

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


		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、二叉搜索树的插入

插入的具体过程为

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

b、如果树不为空。按照二叉搜索树的查找方式找到插入位置,插入新节点。

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、首先要查找元素是否在二叉搜索树中,如果不存在则返回false,如果存在,则删除所在节点位置,并可能对其他节点进行调整。有以下四种情况。

a、要删除的节点无孩子节点

b、要删除的节点只有左孩子节点

c、要删除的节点只有右孩子节点

d、要删除的节点即有左孩子节点又有右孩子节点

情况a可以与情况b和情况c进行合并。

情况b、删除该节点并使该节点的父亲指针被删除指针指向被删除节点的右孩子指针。

情况c、删除该节点并使该节点的父亲指针被删除指针指向被删除节点的左孩子指针。

情况d、在它的右子树中寻找中序下的第一个节点,用它 的值填补到被删除节点中,再去处理该节点的删除问题----替换删除

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(parent == 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(parent == nullptr)
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					// 右为空,父亲指向我的左
					if (cur == parent->_left)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}
				}

				delete cur;
			}
			else//第三种情况
			{
				// 左右都不为空,替换法删除
				// 
				// 查找右子树的最左节点替代删除
				Node* rightMinParent = cur;
				Node* rightMin = cur->_right;
				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}

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

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

				delete rightMin;
			}

			return true;
		}
	}

	return false;
}

4、性能分析

由上述可知,删除和插入操作都必须先查找,查找效率决定了二叉搜索树各种功能的操作的性能。

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

在最理想的情况下,即二叉树为完全二叉树,其平均比较次数为0(logn);

最坏情况发下,即二叉树为单叉树,其平均比较次数为o(n);这个时间复杂度是十分可怕的!!!

所有在“大佬“的改进下,我们有引入的平衡二叉树和红黑树的概念,使得二叉树的性能有了较大的提升,下一篇内容将会给大家介绍平衡二叉数。

三、二叉树的应用

二叉树有多种应用场景,有k模型以及kv模型

1、K模型:只有Key作为关键值,节点中只存储key即可,关键值为需要搜索到该节点的值。

比如给定一个单词word,搜索其拼写是否正确,我们只需要得到一个由所有单词作为键值的二叉搜索树,在二叉搜索树中检索其是否存在即可,不存在即为拼写错误。

2、KV模型:每一个关键值,都有一个唯一的value值与之对应。即<Key,Value>的键值对。

比如:1、英汉词典就是英文和中文的对应关系,通过英文可以快速找到其对应的中文,。

2、统计单词的次数,给定一个单词的拼写,就可以快速找到其出现的次数单词由其出现次数就是<Word,Count>的一种键值对。

以下附二叉搜索树底层实现的源代码。!~!!

#pragma once
#include<string>

namespace key
{
	template<class K>
	//struct BinarySearchTreeNode
	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:
		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(parent == 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(parent == nullptr)
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							// 右为空,父亲指向我的左
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else//第三种情况
					{
						// 左右都不为空,替换法删除
						// 
						// 查找右子树的最左节点替代删除
						Node* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

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

						if (rightMinParent->_left == rightMin)
							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;
	};


	void TestBSTree1()
	{
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		BSTree<int> t1;
		for (auto e : a)
		{
			t1.Insert(e);
		}

		t1.InOrder();

		//t1.Erase(3);
		t1.Erase(8);

		t1.InOrder();

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

namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;

		// pair<K, V> _kv;

		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:
		// logN
		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 cur;
		}

		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(parent == 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(parent == nullptr)
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							// 右为空,父亲指向我的左
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else
					{
						// 左右都不为空,替换法删除
						// 
						// 查找右子树的最左节点替代删除
						Node* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

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

						if (rightMinParent->_left == rightMin)
							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 << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};
	// 20:18
	// 查找
	// 二分查找
	// 二叉搜索树查找 -> AVL树和红黑树
	// 哈希查找
	// 跳表查找
	// 多叉搜索树查找 B树系列
	void TestBSTree2()
	{
		BSTree<string, string> dict;
		dict.Insert("string", "字符串");
		dict.Insert("left", "左边");
		dict.Insert("insert", "插入");
		//...

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

	void TestBSTree3()
	{
		// 统计次数
		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
		BSTree<string, int> countTree;
		for (const auto& str : arr)
		{
			auto ret = countTree.Find(str);
			if (ret == nullptr)
			{
				countTree.Insert(str, 1);
			}
			else
			{
				ret->_value++;
			}
		}

		countTree.InOrder();
	}
}

标签:right,cur,parent,二叉,详解,搜索,key,else,left
From: https://blog.csdn.net/2302_79215415/article/details/139965460

相关文章

  • mysql默认存储引擎--innodb存储引擎(详解)
    官方解释:    InnoDB,是MySQL的数据库引擎之一,现为MySQL的默认存储引擎,为MySQLAB发布binary的标准之一。InnoDB由InnobaseOy公司所开发,2006年五月时由甲骨文公司并购。与传统的ISAM与MyISAM相比,InnoDB的最大特色就是支持了ACID兼容的事务(Transaction)功能,类似于Postgre......
  • Gateway 路由(详解)
    Gateway网关的路由功能可不是简简单单的“转发”请求,在请求到达网关再流转到指定服务之间发生了很多事儿,它不光可以拒绝请求,甚至可以“篡改”请求的参数,我们接下来就去看看路由这里面的门道。路由三重门Gateway中可以定义很多个Route,一个Route就是一套包含完整转发规则的路由......
  • 验证二叉搜索树 前序 中序 后序的三种解法 - 灵神视频总结
    这节课用三种方法来验证一颗二叉树是否是搜索树。递归的基础知识:看到递归就晕?带你理解递归的本质!--灵神视频总结-CSDN博客如何灵活运用递归?-灵神视频总结-CSDN博客98.验证二叉搜索树二叉搜索树的定义:给你一个二叉树的根节点root,判断其是否是一个有效的二叉搜索树......
  • 运维锅总详解Prometheus
    本文尝试从Prometheus简介、架构、各重要组件详解、relable_configs最佳实践、性能能优化及常见高可用解决方案等方面对Prometheus进行详细阐述。希望对您有所帮助!一、Prometheus简介Prometheus是一个开源的系统监控和报警工具,最初由SoundCloud开发,现在是CloudNative......
  • ConcurrentLinkedQueue详解(详细图文+动画演示)
    目录ConcurrentLinkedQueue详解1、ConcurrentLinkedQueue简介2、ConcurrentLinkedQueue继承体系3、ConcurrentLinkedQueue的构造函数4、ConcurrentLinkedQueue的数据结构ConcurrentLinkedQueue类的属性注释ConcurrentLinkedQueue真正存储元素的类`Node<E>`ConcurrentLink......
  • 【C语言】--操作符详解
    ......
  • 79. 单词搜索
    给定一个mxn二维字符网格board和一个字符串单词word。如果word存在于网格中,返回true;否则,返回false。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例1......
  • 力扣每日一题 特别的排列 DFS 记忆化搜索 位运算 状态压缩DP
    Problem:2741.特别的排列......
  • 力扣每日一题 6/30 记忆化搜索/动态规划
    博客主页:誓则盟约系列专栏:IT竞赛专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞......
  • 【C++】 ——【模板初阶】——基础详解
    目录1.泛型编程1.1泛型编程的概念1.2泛型编程的历史与发展1.3泛型编程的优势1.4泛型编程的挑战2.函数模板2.1函数模板概念2.2函数模板格式2.3函数模板的原理2.4函数模板的实例化2.5模板参数的匹配原则2.6函数模板的特化2.7函数模板的使用注意事项2.......