C++二叉搜索树&&搜索二叉树&&二叉排序树

admin2024-05-15  2

C++二叉搜索树

1. 二叉搜索树的概念

二叉搜索树BST,Binary Search Tree),也称为二叉排序树或二叉查找树。它与一般二叉树的区别在于:每个结点必须满足“左孩子大于自己,右孩子小于自己”的规则。在这种规则的约束下,二叉搜索树使用中序遍历出来的数据是一个由小到大排列的结果。

C++二叉搜索树&&搜索二叉树&&二叉排序树,在这里插入图片描述,第1张

优点:

缺点:

2. 二叉搜索树的插入

二叉搜索树的插入很简单,首先用插入的值从根结点开始比较。插入值小于结点值向左,插入值大于结点值向右,直到结点的左孩子或右孩子为空时结束,为空的位置就是插入的位置。

C++二叉搜索树&&搜索二叉树&&二叉排序树,在这里插入图片描述,第2张

C++二叉搜索树&&搜索二叉树&&二叉排序树,在这里插入图片描述,第3张

3. 二叉搜索树的删除

二叉搜索的删除需要分两种情况:

3.1 删除的结点是叶子结点

如果删除的结点是叶子结点,将该结点的父结点指针制空,再释放该结点即可。

C++二叉搜索树&&搜索二叉树&&二叉排序树,在这里插入图片描述,第4张

3.2 删除的结点不是叶子结点

如果删除的结点不是叶子结点,可以分为三种情况讨论:

3.2.1 左子树为空

如果删除的结点的左子树为空,此时需要判断删除结点与其父子树的关系:我是父结点的左孩子,就让父结点的左指向我的右子树;我是父结点的右孩子,就让父结点的右指向我的右子树

C++二叉搜索树&&搜索二叉树&&二叉排序树,在这里插入图片描述,第5张

C++二叉搜索树&&搜索二叉树&&二叉排序树,在这里插入图片描述,第6张

3.2.2 右子树为空

右子树为空,原理与上相同,只是父结点改变的是左的指向。

C++二叉搜索树&&搜索二叉树&&二叉排序树,在这里插入图片描述,第7张

C++二叉搜索树&&搜索二叉树&&二叉排序树,在这里插入图片描述,第8张

3.2.3 左右子树不为空

如果删除结点的左右子树都不为空,那么此时就需要使用替换法的思想。替换法可以使用左子树的最大结点或右子树的最小结点作为替换结点来替换当前结点,再将替换结点删除。所谓“替换”在实际操作中不是把两个结点的值互换,而是将替换结点的值赋给原删除结点,因为替换节点最终要删除,所以不必要对其进行真正的替换操作。

使用最左结点替换:

C++二叉搜索树&&搜索二叉树&&二叉排序树,在这里插入图片描述,第9张

使用最右结点替换:

C++二叉搜索树&&搜索二叉树&&二叉排序树,在这里插入图片描述,第10张

4.二叉搜索树的退化问题

二叉搜索树的最优情况下,查找效率为logN。但当插入的顺序有序或部分有序时,二叉搜索树的查找效率会下降,极端情况下会退化至N

C++二叉搜索树&&搜索二叉树&&二叉排序树,在这里插入图片描述,第11张

5. 参考代码

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->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
	bool Erase(const K& key)
	{
		//先找到该结点
		Node* cur = _root;
		Node* parent = cur;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//如果删除的是叶子结点,直接删除
				if (cur->_left == nullptr && cur->_right == nullptr)
				{
					if (cur == parent->_left)
						parent->_left = nullptr;
					else if (cur == parent->_right)
						parent->_right = nullptr;
					delete cur;
				}
				//如果左为空
				else if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else if (cur == parent->_right)
						{
							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 if (cur == parent->_right)
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}
				// 如果左右都不为空
				else
				{
					//查找右子树的最左结点替换
					Node* RightMinParent = cur;
					Node* RightMin = cur->_right;
					while (RightMin->_left)
					{
						RightMinParent = RightMin;
						RightMin = RightMin->_left;
					}
					cur->_key = RightMin->_key;
					cur->_value = RightMin->_key;
					cur->_value = RightMin->_value;
					if (RightMinParent->_left == RightMin)
					{
						RightMinParent->_left = nullptr;
					}
					else
					{
						RightMinParent->_right = nullptr;
					}
					delete RightMin;
				}
				return true;

			}
		}
		return false;
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << ":" << root->_value << endl;
		_InOrder(root->_right);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:
	Node* _root = nullptr;
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!