二叉搜索树介绍与实现

以下代码环境为 VS2022 C++。

前言：

在上篇博客 二叉树链式结构与简单实现 中我们对二叉树进行了简单的了解，这里我们在二叉树链式结构的基础上进一步探讨对数据进行排序的二叉搜索树。

一、二叉搜索树的概念

二叉搜索树又称二叉排序树或搜索二叉树，它或者是一棵空树，或者是具有以下性质的二叉树：

1. 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值。

2. 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值。

3. 它的左右子树也分别为二叉搜索树。

4. 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，C++ STL 中 map / set / multimap / multiset 系列容器底层就是二叉搜索树，其中 map / set 不支持插入相等值，multimap / multiset 支持插入相等值。
   

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

性能分析：

1. 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为：O(log N)（注意，这里与以下出现的 log 都是以 2 为底）

2. 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为： O(N / 2)

所以综合而言二叉搜索树增删查改时间复杂度为： O(N)

这样的效率显然是无法满足要求的，需要在二叉搜索树之上进行变形，也就是平衡二叉搜索树 AVL树 和 红黑树，才能适用于我们在内存中存储和搜索数据。

另外需要说明的是，二分查找也可以实现 O(log N) 级别的查找效率，但是二分查找有两大缺陷：

1. 需要存储在支持下标随机访问的结构中，并且有序。

2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

这里也就体现出了平衡二叉搜索树的价值。

三、二叉搜索树的插入

插入的具体过程如下：

1. 树为空，则直接新增结点，赋值给 root 指针。

2. 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。

3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）
   

四、二叉搜索树的查找

1. 从根开始比较，查找 x ，x 比根的值大则往右边走查找，x 比根值小则往左边走查找。

2. 最多查找高度次，走到空，还没找到，则这个值不存在。

3. 如果不支持插入相等的值，找到 x 即可返回。

4. 如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。如下图，查找 3，要找到 1 的右孩子的那个 3 返回。
   

五、二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。
如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为 N）

1. 要删除结点 N 左右孩子均为空

2. 要删除的结点 N 左孩子位空，右孩子结点不为空

3. 要删除的结点 N 右孩子位空，左孩子结点不为空

4. 要删除的结点 N 左右孩子结点均不为空

对应以上四种情况的解决方案：

1. 把 N 结点的父亲对应孩子指针指向空，直接删除 N 结点（情况 1 可以当成 2 或者 3 处理，效果是一样的）

2. 把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点

3. 把 N 结点的父亲对应孩子指针指向 N 的左孩子，直接删除 N 结点

4. 无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除。找 N 左子树的值最大结点 R(最右结点) 或者 N 右子树的值最小结点 L(最左结点) 替代 N，因为这两个结点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代 N 的意思就是 N 和 R(或L) 的两个结点的值交换，转而变成删除 R(或L) 结点，R(或L) 结点符合情况 2 或情况 3，可以直接删除。

注意当删除的是头节点时需要额外判断。

六、二叉搜索树key和key/value的实现代码

这里实现了 key 和 key/value 两种，代码基本一样。
在 BinarySearchTree.hpp 中：

#pragma once#include <iostream>namespace key
{template<class K>struct BSTNode			// binary search tree node 二叉搜索树节点{BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){;}K _key;BSTNode<K>* _left;BSTNode<K>* _right;};template<class K>class BSTree			// binary search tree 二叉搜索树{typedef BSTNode<K> Node;typedef Node* pNode;public:bool insert(const K& key){pNode parent = nullptr;pNode child = _root;while (child != nullptr){if (child->_key == key)			// 已存在则退出{return false;}parent = child;child = child->_key < key ? child->_right : child->_left;}pNode temp = BSTreeCreateNode(key);if (parent == nullptr){_root = temp;}else if (parent->_key < key){parent->_right = temp;}else{parent->_left = temp;}return true;}pNode find(const K& key){pNode cur = _root;while (cur != nullptr){if (cur->_key == key){return cur;}cur = (cur->_key < key ? cur->_right : cur->_left);}return nullptr;}bool erase(const K& key){pNode parent = nullptr;pNode child = _root;while (child != nullptr){if (child->_key == key){break;}parent = child;child = child->_key < key ? child->_right : child->_left;}if (child == nullptr)						// child 为空则节点不存在{return false;}if (parent == nullptr)						// 注意删除根节点判断{if (_root->_left == nullptr){_root = _root->_right;}else if (_root->_right == nullptr){_root = _root->_left;}else{pNode prev = child->_right;pNode cur = child->_right;while (cur->_left != nullptr){prev = cur;cur = cur->_left;}std::swap(cur->_key, child->_key);if (prev != cur){prev->_left = cur->_right;}else{child->_right = cur->_right;}child = cur;}}else if (child->_left == nullptr)			// 情况 1 和 2{if (parent->_right == child){parent->_right = child->_right;}else{parent->_left = child->_right;}}else if (child->_right == nullptr)			// 情况 3{if (parent->_right == child){parent->_right = child->_left;}else{parent->_left = child->_left;}}else										// 情况 4{pNode prev = child->_right;pNode cur = child->_right;while (cur->_left != nullptr){prev = cur;cur = cur->_left;}std::swap(cur->_key, child->_key);if (prev != cur){prev->_left = cur->_right;}else{child->_right = cur->_right;}child = cur;}delete child;return true;}void inOrder()				// 中序遍历{_inOrder(_root);}private:pNode BSTreeCreateNode(const K& key){return new BSTNode<K>(key);}void _inOrder(pNode root){if (root == nullptr){return;}_inOrder(root->_left);std::cout << root->_key << " ";_inOrder(root->_right);}private:pNode _root = nullptr;};
}namespace key_value
{template<class K, class V>struct BSTNode			// binary search tree node 二叉搜索树节点{BSTNode(const K& key, const V& value):_key(key),_value(value),_left(nullptr),_right(nullptr){;}K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;};template<class K, class V>class BSTree			// binary search tree 二叉搜索树{typedef BSTNode<K, V> Node;typedef Node* pNode;public:bool insert(const K& key, const V& value){pNode parent = nullptr;pNode child = _root;while (child != nullptr){if (child->_key == key){return false;}parent = child;child = child->_key < key ? child->_right : child->_left;}pNode temp = BSTreeCreateNode(key, value);if (parent == nullptr){_root = temp;}else if (parent->_key < key){parent->_right = temp;}else{parent->_left = temp;}return true;}pNode find(const K& key){pNode cur = _root;while (cur != nullptr){if (cur->_key == key){return cur;}cur = (cur->_key < key ? cur->_right : cur->_left);}return nullptr;}bool erase(const K& key){pNode parent = nullptr;pNode child = _root;while (child != nullptr){if (child->_key == key){break;}parent = child;child = child->_key < key ? child->_right : child->_left;}if (child == nullptr){return false;}if (parent == nullptr){if (_root->_left == nullptr){_root = _root->_right;}else if (_root->_right == nullptr){_root = _root->_left;}else{pNode prev = child->_right;pNode cur = child->_right;while (cur->_left != nullptr){prev = cur;cur = cur->_left;}std::swap(cur->_key, child->_key);std::swap(cur->_value, child->_value);if (prev != cur){prev->_left = cur->_right;}else{child->_right = cur->_right;}child = cur;}}else if (child->_left == nullptr){if (parent->_right == child){parent->_right = child->_right;}else{parent->_left = child->_right;}}else if (child->_right == nullptr){if (parent->_right == child){parent->_right = child->_left;}else{parent->_left = child->_left;}}else{pNode prev = child->_right;pNode cur = child->_right;while (cur->_left != nullptr){prev = cur;cur = cur->_left;}std::swap(cur->_key, child->_key);std::swap(cur->_value, child->_value);if (prev != cur){prev->_left = cur->_right;}else{child->_right = cur->_right;}child = cur;}delete child;return true;}void inOrder(){_inOrder(_root);}private:pNode BSTreeCreateNode(const K& key, const V& value){return new BSTNode<K, V>(key, value);}void _inOrder(pNode root){if (root == nullptr){return;}_inOrder(root->_left);std::cout << root->_key << " " << root->_value << " " << std::endl;_inOrder(root->_right);}private:pNode _root = nullptr;};
}

七、二叉搜索树key和key/value使用场景

1. key搜索场景：

只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值，搜索场景只需要判断 key 在不在。key 的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改 key 则会破坏搜索树结构。

场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，反之提示非本小区车辆，无法进入。

场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，反之波浪线标红提示。

2. key/value搜索场景：

每一个关键码 key，都有与之对应的值 value，value 可以任意类型对象。树的结构中(结点)除了需要存储 key 还要存储对应的 value，增 / 删 / 查还是以 key 为关键字走二叉搜索树的规则进行比较，可以快速查找到 key 对应的 value。key / value 的搜索场景实现的二叉树搜索树支持修改，但是不支持修改 key，修改 key 破坏搜索树结构了，可以修改 value。

场景1：简单中英互译字典，树的结构中(结点)存储 key(英文) 和 value(中文)，搜索时输入英文，则同时查找到了英文对应的中文。

场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用 当前时间 - 入场时间 计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。

场景3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在。若不存在说明其第一次出现，则插入（单词，1）。若单词存在，则 ++ 单词对应的次数。

#include "BinarySearchTree.hpp"
#include <iostream>
using namespace std;void test1()
{key_value::BSTree<string, string> dict;dict.insert("insert", "插入");dict.insert("erase", "删除");dict.insert("left", "左边");dict.insert("string", "字符串");string str;while (cin >> str){auto ret = dict.find(str);if (ret){cout << str << ":" << ret->_value << endl;}else{cout << "单词拼写错误" << endl;}}string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };// 统计水果出现的次key_value::BSTree<string, int> countTree;for (auto& str : strs){auto ret = countTree.find(str);if (ret == NULL){countTree.insert(str, 1);}else{ret->_value++;}}countTree.inOrder();
}int main()
{test1();return 0;
}