C++镌刻数据密码的树之铭文：二叉搜索树

继数据结构的二叉树学习，本篇进行更进一步的搜索二叉树，是一种更为常见的结构

二叉搜索树的概念

二叉搜索树简单来说就是一个排序树

它是具有以下性质的二叉树:

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

🔥值得注意的是： 每棵子树都满足该性质

二叉搜索树的实现

二叉搜索树的结构

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

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

• _left： 指向左子节点的指针。
• _right： 指向右子节点的指针。
• _key： 存储节点的键值

二叉搜索树的节点寻找

非递归

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

借助 cur 指针从根节点开始遍历二叉搜索树：

• 若 cur->_key 小于 key，则转向右子树继续查找
• 若 cur->_key 大于 key，则转向左子树继续查找
• 若 cur->_key 等于 key，说明找到了目标键值，返回 true
• 若遍历结束 cur 为 nullptr，表示未找到目标键值，返回 false

递归

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

	if (root->_key < key)
	{
		return _FindR(root->_right, key);
	}
	else if (root->_key > key)
	{
		return _FindR(root->_left, key);
	}
	else
	{
		return true;
	}
}

检查基本情况： 查看当前节点 root 是否为空。若为空，返回 false，递归结束
比较键值： 若当前节点不为空，将当前节点的键值 root->_key 与目标键值 key 进行比较重复，每次递归调用都会将问题规模缩小，直至满足基本情况或者找到目标节点

🔥值得注意的是： 注意这些非递归要放在 private，因为 root 也是 private，由于要控制子树，必须要传入 root，如果是 public 的话，就只能传入自己的 root，而不是二叉搜索树的 root，无法保证 root 的正确性

二叉搜索树的插入

非递归

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

当 cur 为空时，说明已经找到了插入位置。创建一个新节点，并根据 parent 的键和要插入的键的大小关系，将新节点插入到 parent 的左子树或右子树中

🔥值得注意的是： 首先检查树是否为空，如果为空，则直接创建一个新节点作为根节点，并返回 true

递归

bool _InsertR(Node*& root, const K& key)
{
	if (root == nullptr)
	{
		root = new Node(key);
		return true;
	}

	if (root->_key < key)
	{
		return _InsertR(root->_right, key);
	}
	else if (root->_key > key)
	{
		return _InsertR(root->_left, key);
	}
	else
	{
		return false;
	}
}

这里递归的流程和查找的递归代码几乎一样，唯一不同的是要传入的 root 需要加引用，这是因为这里的代码只执行了节点寻找创建的操作，那么当我们找到空节点并创建的时候，由于 root 是上一个 _InsertR 函数 root->_left 或 root->_right 的别名，创建的时候相当于 root->_left = new Node(key) 或 root->_right = new Node(key)，这样才能完成链接

二叉搜索树的删除

非递归

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

	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)
			{
				// 左为空
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->_right = cur->_right;
					}
				}
			}// 右为空
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_right == cur)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}
				}
			}// 左右都不为空 
			else
			{
				Node* parent = cur;
				Node* leftMax = cur->_left;
				while (leftMax->_right)
				{
					parent = leftMax;
					leftMax = leftMax->_right;
				}

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

				if (parent->_left == leftMax)
				{
					parent->_left = leftMax->_left;
				}
				else
				{
					parent->_right = leftMax->_left;
				}

				cur = leftMax;
			}

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

首先先找到需要删除的节点，接着就需要分了讨论：

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

🔥值得注意的是： 第一点可以直接看成只有一个节点的情况，即链接的是空节点

删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除

如果待删除节点 cur 的左子树为空，分两种情况处理：
如果 cur 就是根节点，那么将根节点更新为 cur 的右子树；如果 cur 不是根节点，则根据 cur 是其父节点 parent 的左子节点还是右子节点，相应地将 parent 的左指针或右指针指向 cur 的右子树

删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除

如果待删除节点 cur 的右子树为空，同样分两种情况：

若 cur 是根节点，将根节点更新为 cur 的左子树；若 cur 不是根节点，根据 cur 是 parent 的左子节点还是右子节点，将 parent 的左指针或右指针指向 cur 的左子树

在删除节点的左子树中寻找最大节点或者在它的右子树中寻找最小节点，用它的值填补到被删除节点中，再来处理该节点的删除问题–替换法删除

当待删除节点 cur 的左右子树都不为空时，为了保持二叉搜索树的性质，找到 cur 左子树中的最大节点 leftMax（即左子树中最右侧的节点）。通过一个 while 循环找到 leftMax，并记录其父亲节点 parent。然后交换 leftMax 和 cur 的键值，这样就将删除 cur 节点的问题转化为删除 leftMax 节点的问题，leftMax 由于是最大的节点，所以要么没有节点，要么只有左节点

🔥值得注意的是：

Node* parent = cur 而不是 Node* parent = nullptr，因为如果第一个左子节点就是 leftMax，那么 parent 就不会改变，使用 parent 的时候就会出问题

2.4.2 递归

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* del = root;

		// 1、左为空
		// 2、右为空
		// 3、左右都不为空
		if (root->_left == nullptr)
		{
			root = root->_right;
		}
		else if (root->_right == nullptr)
		{
			root = root->_left;
		}
		else
		{
			Node* leftMax = root->_left;
			while (leftMax->_right)
			{
				leftMax = leftMax->_right;
			}

			swap(root->_key, leftMax->_key);

			return _EraseR(root->_left, key);
		}

		delete del;
		return true;
	}
}

将即 root 和 leftMax 的键值进行交换，此时原本 leftMax 节点处的键值变为要删除的 key，由于交换后要删除的节点在左子树中，所以递归调用 _EraseR(root->_left, key) 继续在左子树中查找并删除这个键值为 key 的节点。因为在左子树中删除节点时，可能又会遇到不同的情况（如左子树为空、右子树为空或左右子树都不为空），所以递归调用可以继续处理这些情况，直到成功删除节点或者确定节点不存在

🔥值得注意的是：

这里 return _EraseR(root->_left, key) 不能写成 return _EraseR(leftMax, key)

因为 leftMax 只是个局部变量，对其进行操作没法改变 8 与 1 的链接

2.5 二叉搜索树的拷贝

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

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

1. 为当前节点创建一个新的节点 copyroot，新节点的键值和原节点 root 的键值相同
2. 递归调用 Copy 函数来拷贝原节点 root 的左子树，将拷贝结果赋值给新节点 copyroot 的左子节点指针 _left
3. 同样地，递归调用 Copy 函数来拷贝原节点 root 的右子树，把拷贝结果赋值给新节点 copyroot 的右子节点指针 _right
4. 最后返回新创建的节点 copyroot，该节点及其子树构成了原节点及其子树的深拷贝

二叉树的应用

🚩K模型： 即只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值，主要判断在不在的场景

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

• 以词库中所有单词集合中的每个单词作为 key，构建一棵二叉搜索树
• 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

🚩KV模型： 每一个关键码 key，都有与之对应的值 value，即 <key, value> 的键值对，通过一个值找另外一个值

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

namespace key_value
{
	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:
		BSTree()
			:_root(nullptr)
		{
		}

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

		Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}

		bool InsertR(const K& key, const V& value)
		{
			return _InsertR(_root, key, value);
		}

		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}

	private:
		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* del = root;

				// 1、左为空
				// 2、右为空
				// 3、左右都不为空
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_right)
					{
						leftMax = leftMax->_right;
					}

					swap(root->_key, leftMax->_key);

					return _EraseR(root->_left, key);
				}

				delete del;
				return true;
			}
		}

		bool _InsertR(Node*& root, const K& key, const V& value)
		{
			if (root == nullptr)
			{
				root = new Node(key, value);
				return true;
			}

			if (root->_key < key)
			{
				return _InsertR(root->_right, key, value);
			}
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key, value);
			}
			else
			{
				return false;
			}
		}

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

			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
			{
				return root;
			}
		}

		void _InOrder(Node* root)
		{
			if (root == NULL)
			{
				return;
			}

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root;
	};

key_value 模型主要是通过一个节点里包含两个值：key 和 value 实现的，只要找到了key 就能顺便找到 value，其余的函数逻辑等都与 K 模型几乎一致

🔥值得注意的是： 二叉搜索树的性能是不错的，插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能，

• 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：$log_2 N$
• 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$\frac{N}{2}$

如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们涉及到后续章节学习的 AVL树 和 红黑树

---

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！