博客

二叉搜索树

  • Post author:
  • Post category:其他




二叉搜索树概念


二叉搜索树又称二叉排序树，具有一下性质：

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

在这里插入图片描述

在二叉搜索树中，我们最多查找高度次，这也就是为什么叫搜索二叉树的原因。但是二叉树并不完美，如果左右两边的元素分布比较均匀，那么时间复杂度为可以近似为logn，但是如果不均匀，甚至最差的时间复杂度为n

在这里插入图片描述



二叉搜索树操作



二叉搜索树的构建

二叉树的构建相对还是很简单的，每个节点中的成员类似于二叉树，有指向左边的指针，也有指向右边的节点指针，还有一个以模板定义的key值 

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

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

而在BSTree这个类中，需要内嵌一个BSTreeNode的类：要在其中实现增删查改。


二叉搜索树的节点插入

先来说一下插入：在插入的过程中，要与每个节点的值进行对别，如果比节点值大就向右走，反之则反，如果相等则不允许插入。在插入的时候一定注意要将创建的节点与上一个节点链接起来。当然还要注意最后链接时候，需要与parent节点进行比较后再链接。 

// 搜索二叉树的插入
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur != nullptr)
		{
			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;
	}

如果想要遍历这颗树并实现排序，可以使用中序遍历，中序遍历这里就不做详细介绍了。


二叉搜索树的查找

搜索二叉树的查找也是相对简单的，和插入一开始的操作类似，插入也是去寻找一个合适的位置实现插入。代码如下： 

// 查找
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur != nullptr)
		{
			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* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				// 1.左为空
				// 2.右为空
				// 3.左右都不为空，替换删除
				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;
				}
				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* minRight = cur->_right;
					Node* parent = cur;
					while (minRight->_left)
					{
						parent = minRight;
						minRight = minRight->_left;
					}
                    cur->_key = minRight->_key;
					if (minRight == parent->_left)
						parent->_left = minRight->_right;
					else
						parent->_right = minRight->_right;
                    delete minRight;
				}
				return true;
			}
		}
		return false;
	}

解读一下代码：

首先找到需要被删除的节点，然后开始对其进行删除，删除的情况要视节点而定，有可能被删除的节点的左边为空，也有可能被删除的节点的右边为空，还有一种特殊的情况就是被删除的节点是根节点，所以还需要特殊讨论一下这种情况；最后就是左右都不为空，替换删除，替换删除需要先找到被删除节点的右子树的最小值，之后要注意删除完成之后要进行适当的链接，具体请看代码理解。


二叉搜索树的构造，拷贝构造与析构

构造函数就很简单了，对元素进行一些基本的构造即可

析构函数这里可以使用后序遍历进行析构，实现的方法也是很简单的： 

~BSTree()
	{
		Destroy(_root);
		_root = nullptr;
	}	
void Destroy(Node* root)
	{
		if (root == nullptr)
			return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

拷贝构造函数在实现的时候切记是不可以直接进行值的插入的，因为直接插入数值，随着插入顺序的不同，会导致树的形状和之前树的形状有所不同；实际我们可以使用前序遍历直接对其拷贝，构造出整颗树 

	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newRoot = new Node(root->_key);
		newRoot->_left = new Node(root->_left);
		newRoot->_right = new Node(root->_right);
		return newRoot;
	}



递归版本


查找函数的递归版本

查找函数的递归版本相对简单，如果找到的是空树，那么说明没有找到这个树，返回false；通过比较确定要去这个树的左子树还是右子树进行查找，找到后返回true 

bool _FindR(Node*& root)
	{
		if (root == nullptr)
			return false;
		if (key < root->_key)
			_FindR(root->_left, key);
		else if (key > root->_key)
			_FindR(root->_right, key);
		else
			return true;
	}


插入函数的递归版本

插入函数这里有一个很好的写法如下： 

	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (key < root->_key)
			_InsertR(root->_left, key);
		else if (key > root->_key)
			_InsertR(root->_right, key);
		else
			return false;
	}

插入函数中的第一个参数是一个引用，在递归的过程中，使用引用可以很好解决最后的链接问题，不需要再创建更多的节点进行最后的链接。


删除函数的递归版本

删除函数递归调用本质上也是先找到需要被删除的节点，之后将该节点进行判断，同非递归版本一样，也分为三种情况，第三种比较复杂，这里单独说一下：

如过被删除的节点的左树和右树都有节点，那么首先需要找到右子树中最小的值的那个节点，之后对被删除节点的的值进交换，但是很明显交换之后的节点的所处的位置一定是前两种删除节点的情况，所以这个时候只需要再递归调用一次删除函数即可实现删除的目的。 

	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* ptr = root;
			if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else
			{
				Node* minRight = root->_right;
				while (minRight->_left)
				{
					minRight = minRight->_left;
				}
				swap(root->_key, minRight->_key); 
				return _EraseR(root->_right, key);
			}
			delete ptr;
			return true;
		}
	}



二叉搜索树的拓展模型


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

​ 应用场景比如：词库中单词都存放在搜索树中，Key的搜索模型，判断某个单词在不在这个树中；或者车库的出入系统…


  1. KV模型：每一个关键码key，都有与之对应的值value，通常是通过key值查找或修改value

​ 在实现的时候其实很简单，就是在存储key值的基础上再存储一个value，使用模板来构造两个类型的参数即可


版权声明：本文为weixin_63108237原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。