1. AI技术聚合首页
  2. IT

【数据结构】二叉搜索树

社会演员多 • • IT • 阅读 20

一、概念

二、操作

2.1 使用二叉搜索树排序

2.2 二叉搜索树的查找

2.3 二叉搜索树的插入

2.4 二叉搜索树的删除

三、二叉搜索树的实现

四、二叉搜索树的应用

（1）key模型

（2）key/value模型

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

是久违的数据结构~如果有第一次学习二叉树结构的同学可以移步

数据结构——二叉树-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/Eristic0618/article/details/135723033?spm=1001.2014.3001.5501

一、概念

二叉搜索树（Binary Search Tree），又称为二叉查找树、二叉排序树，它有以下性质：

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

例如下图，左边的是一颗二叉搜索树，右边的则不是：

二、操作

2.1 使用二叉搜索树排序

二叉搜索树之所以又叫二叉排序树，是因为在其独特的性质下，如果我们使用中序遍历，就会得到一个有序的序列

例如：

2.2 二叉搜索树的查找

既然叫二叉搜索树，肯定主要用于查找数据

二叉搜索树的性质就决定了它的查找方法：

  1. 从根开始查找，如果目标比根节点大则往右子树走，如果比根节点小就往左子树走
  2. 当走到空还没找到，则不存在

例如：

如果换成16的话，因为二叉搜索树中没有这个值，到最后就会走到空

 

2.3 二叉搜索树的插入

二叉搜索树的插入分为两种情况：

  1. 树为空，则直接new一个节点并赋值给根
  2. 树不为空，则按照二叉搜索树查找的方式寻找插入位置，插入新节点

例如上面的例子，我们此时插入一个16

2.4 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在就返回false

如果存在，那么此时要删除的节点可能分为以下四种情况：

  1. 要删除的节点无子节点
  2. 要删除的节点只有左子节点
  3. 要删除的节点只有右子节点
  4. 要删除的节点有左、右子节点

第一种情况是最好处理的，我们先跳过

第二种情况，要删除的节点只有左子节点，我们还是用上面的例子，此时18就是一个只有左子节点的节点

如果我们要删除18，只需要将18的父节点和18的左子节点链接，然后直接删除18即可。

第三种情况，要删除的节点只有右子节点，此时23就是一个只有右子节点的节点

如果我们要删除23，只需要将23的父节点和23的右子节点链接，然后直接删除23即可

第二种和第三种情况的删除方式也适用于第一种情况，因为无子节点，也就是左右都为空，此时父节点链接的是一个空指针，并删除目标节点即可

重点：

第四种情况，要删除的节点有左、右节点，此时14符合要求

我们的目标是，在14的子树中寻找一个值，将14与这个值交换。这种方法叫做替换法。

要寻找的值必须满足交换后二叉搜索树的性质不变，所以我们需要在14的左子树找出一个最大值，或者在14的右子树找出一个最小值。

前面提到过对二叉搜索树中序遍历可以得到一个有序的序列，所以14的左子树的最大值，也就是在左子树中做一次中序遍历下的最后一个数，也就是9。简单来说，我们只需要从14向左走一步，然后一直向右走，就可以找到左子树的最大值了

而14的右子树的最小值，也就是在右子树中做一次中序遍历下的第一个数，也就是15。和上面类似的，我们只需要从14向右走一步，然后一直向左走，就可以找到右子树的最小值了。

因此，我们可以将9和14替换，或者将15和14替换

这里就只展示9和14替换的情况，当学会规律后，另一种情况也就学会了。

替换后，还需要把14的父节点和14的子节点链接，这里又有两种情况需要区分，否则导致错误：

  1. 替换后14的父节点位于14原先的位置
  2. 替换后14的父节点不位于14原先的位置

可以看出，在这种情况下14的父节点位于14原先的位置，那么就要将此时14的左子节点赋值给父节点的left，然后就可以直接删除14了

我们改造一下这颗二叉搜索树，让替换后14的父节点不位于14原先的位置：

（改造后14的左子树的最大值为11） 

此时，就需要将14的左子节点赋值给父节点的right，然后直接删除14。

这里是一个易错点，需要注意情况的判断。以上是对二叉搜索树的操作部分，可以与后面二叉搜索树的实现结合食用。

三、二叉搜索树的实现

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:

	bool insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* prev = nullptr;
		Node* cur = _root;

		while (cur)
		{
			prev = cur;
			if (key > cur->_key)
				cur = cur->_right;
			else if (key < cur->_key)
				cur = cur->_left;
			else
				return false;
		}

		cur = new Node(key);

		if (key > prev->_key)
			prev->_right = cur;
		else
			prev->_left = cur;
		return true;
	}

	bool insertR(const K& key) //递归版本
	{
		return _insertR(_root, key);
	}

	bool find(const K& key)
	{
		Node* cur = _root;

		while (cur)
		{
			if (key > cur->_key)
				cur = cur->_right;
			else if (key < cur->_key)
				cur = cur->_left;
			else
				return true;
		}

		return false;
	}

	bool findR(const K& key) //递归版本
	{
		return _findR(_root, key);
	}

	bool erase(const K& key) //替换法：把目标替换成左子树的最大值或右子树的最小值
	{
		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				if (cur->_left == nullptr) //左子树为空
				{
					if (cur == _root)
						_root = cur->_right;
					else
					{
						if (cur == parent->_right)
							parent->_right = cur->_right;
						else
							parent->_left = cur->_right;
					}
				}
				else if(cur->_right == nullptr) //右子树为空
				{
					if (cur == _root)
						_root = cur->_left;
					else
					{
						if (cur == parent->_left)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}
				}
				else //左右子树都不为空
				{
					parent = cur;
					Node* leftmid = cur->_left;
					while (leftmid->_right)
					{
						parent = leftmid;
						leftmid = leftmid->_right;
					}
					swap(cur->_key, leftmid->_key);
					if (parent == cur)
						parent->_left = leftmid->_left;
					else
						parent->_right = leftmid->_left;
					cur = leftmid;
				}

				delete cur;
				return true;
			}
		}
		return false;
	}

	bool eraseR(const K& key) //递归版本
	{
		return _eraseR(_root, key);
	}

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

	BSTree() = default;

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

	~BSTree()
	{
		Destroy(_root);
	}

private:
	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;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

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

		if (key > root->_key)
			return _findR(root->_right, key);
		else
			return _findR(root->_left, key);
	}

	bool _insertR(Node*& root, const K& key) //参数中指针一定要用引用，不然链接不上
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (key > root->_key)
			return _insertR(root->_right, key);
		else if (key < root->_key)
			return _insertR(root->_left, key);
		else
			return false;
	}

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

		if (key > root->_key)
			return _eraseR(root->_right, key);
		else if (key < root->_key)
			return _eraseR(root->_left, key);
		else
		{
			if (root->_left == nullptr)
			{
				Node* tmp = root;
				root = root->_right; //由于引用，root是父节点子树的别名，所以可以直接修改
				delete tmp;
			}
			else if (root->_right == nullptr)
			{
				Node* tmp = root;
				root = root->_left;
				delete tmp;
			}
			else
			{
				Node* leftmid = root->_left;
				while (leftmid->_right)
					leftmid = leftmid->_right;
				swap(root->_key, leftmid->_key);
				return _eraseR(root->_left, key);
			}
			return true;
		}
	}
private:
	Node* _root = nullptr;
};

四、二叉搜索树的应用

（1）key模型

即只有key作为关键码，只需要在二叉搜索树中存储一个key即可

例如我们将业主的信息作为key，将整个小区所有业主的key存储进二叉搜索树中，如果此时要查询一个人是否是小区的业主，只需要将他的key在二叉搜索树中查找一下就可以知道这个人是否是业主了

后面要学习的set，就是一个key模型

（2）key/value模型

每一个关键码key，都有与之对应的值value，也就是要在二叉搜索树中存储<key, value>的键值对

例如字典就是一个key/value模型，英文单词作为key，中文作为value，通过key就可以查找到value

又例如哈希表或者类似的用于统计某个物品出现次数的结构，通过查找该物品就可以快速得到其出现次数，这也是一个key/value模型。

后面要学习的map，就是一个key/value模型

我们可以将二叉搜索树改造为key/value的结构，让节点中多存储一个value，再进行一些修改即可

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

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

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	bool insert(const K& key, const V& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(key, val);
			return true;
		}

		Node* prev = nullptr;
		Node* cur = _root;

		while (cur)
		{
			prev = cur;
			if (key > cur->_key)
				cur = cur->_right;
			else if (key < cur->_key)
				cur = cur->_left;
			else
				return false;
		}

		cur = new Node(key, val);

		if (key > prev->_key)
			prev->_right = cur;
		else
			prev->_left = cur;
		return true;
	}

	Node* find(const K& key)
	{
		Node* cur = _root;

		while (cur)
		{
			if (key > cur->_key)
				cur = cur->_right;
			else if (key < cur->_key)
				cur = cur->_left;
			else
				return cur;
		}

		return nullptr;
	}

	bool erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				if (cur->_left == nullptr)
				{
					if (cur == _root)
						_root = cur->_right;
					else
					{
						if (cur == parent->_right)
							parent->_right = cur->_right;
						else
							parent->_left = cur->_right;
					}
				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
						_root = cur->_left;
					else
					{
						if (cur == parent->_left)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}
				}
				else
				{
					parent = cur;
					Node* leftmid = cur->_left;
					while (leftmid->_right)
					{
						parent = leftmid;
						leftmid = leftmid->_right;
					}
					swap(cur->_key, leftmid->_key);
					if (parent == cur)
						parent->_left = leftmid->_left;
					else
						parent->_right = leftmid->_left;
					cur = leftmid;
				}

				delete cur;
				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->_val << endl;
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;
};

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

因为插入和删除操作必须先查找，因此查找效率直接代表了二叉搜索树中各种操作的性能

可能很多人认为二叉搜索树查找的时间复杂度为O(logN)，但这是在最优情况下二叉搜索树接近完全二叉树的情况

我们需要把目光放到最差情况：如果将一个有序的序列存入二叉搜索树，此时二叉搜索树就会退化成单支树或近似单支树

例如：

此时，时间复杂度就会退化为O(N)，出现丢失性能的情况

为了避免出现这种情况，需要对二叉搜索树进行平衡，这里涉及到后面要学习的AVL树和红黑树。

完.

版权声明：本文为博主作者：阿瑾0618原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/Eristic0618/article/details/137919573

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
社会演员多的头像社会演员多普通用户
0
上一篇 2024年4月22日
下一篇 2024年4月22日

相关推荐