【数据结构】二叉搜索树

目录

1. 二叉搜索树的概念

2. 二叉搜索树的性能分析

3.二叉搜索树的实现

3. 1.二叉搜索树的插入

3.2. 二叉搜索树的查找

3.3. 二叉搜索树的删除

3.4. 二叉搜索树的实现代码

4. 二叉搜索树key和key/value两种使用场景

4.1 key搜索场景：

4.2 key/value搜索场景：

4.3 key/value二叉搜索树代码实现

---

在数据结构专栏，笔者介绍了，单纯的二叉树实际意义并不大，但是单二叉树变成平衡二叉搜索树就会很有用，那么本文就先来介绍一下什么是二叉搜索树。

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
• 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值
• 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值
• 它的左右子树也分别为二叉搜索树

以上图为例，8为树的根节点，以3为根节点的左子树上的所有数都比8小，以10为根节点的右子树上的所有树都比8大，以14为根节点的右子树上的数都比10大，同时作为以10为根节点的树的一部分，必须满足以14为根节点的树上所以书比8大的性质；对于以3为根节点的数来说，以1为根的左子树上的数都比3小，以6为根节点右子树上的数都比3大，但是都比8小，因为作为3这棵左子树的一部分，必须满足比8小的性质。

又以二叉搜索树的插入形成为例，我们可以人为的规定大的数与小的数插在每一棵树的那一边

我们同意规定小的数插在左边，大的数插在右边（也可以反过来，这个没有本质区别）

如3比8小，所以我们将3插入到8的左边，10比8大，我们插入到8的右边，1比8小，插到左边，同时又比3小，所以插到3的左边，6比8小插到左边，但是又比3大，所以插到3的右边，10比8大插到8的右边，14比8大，插到8的右边，又比10大，所以14插到10的右边。其他数的插入依次类推。这样我们就确保对于每一棵树来说左子树上的数都比根小，右子树上的数都比根大。（重复的相等数据的处理需要根据具体的情形。）

• 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续介绍的map/set/multimap/multiset系列容器底层就是二叉搜索树，其中map/set不支持插入相等值，multimap/multiset支持插入相等值。（相等值具体是插入在左边还是右边没有硬性规定。）

2. 二叉搜索树的性能分析

比起一般的二叉树来说，二叉搜索树最大的作用在于它高效的查找效率。

因为我们规定了大数据与小数据的相对位置，小数据都在左子树，大数据都在右子树，如上图查找，达到一种类似二分查找的效果，时间复杂度是二叉树的高度，即。

但是如果遇到下图中的第二种情况，如果插入到二叉树中的数据是一组有序的数据，那么，假如说我们要查找1，这个时候我们就需要近似遍历整个数据才行，时间复杂度是。

所以二叉搜索树的时间复杂度如下：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为:
所以综合而言二叉搜索树增删查改时间复杂度为：

我们提到二叉搜索树的价值在于快捷的查找，数组、链表等结构如果链表用来查找也可以达到的效率，所以在设计二叉搜索树这样复杂结构下，这样的效率显然是无法满足我们需求的。

我们发现导致二叉搜素树性能大幅退化主要是数据有序导致的二叉树的高度不均衡，为了解决这个问题，平衡二叉搜索树、AVL、红黑数应运而生。（后续文章继续介绍二叉搜索树的变形，本文不做过多介绍）实际运用中，平衡二叉搜索树、AVL树和红黑树，才能适用于我们在内存中存储和搜索数据。
另外需要说明的是，二分查找也可以实现 O(logN)级别的查找效率，但是二分查找有两大缺陷：
1. 需要存储在支持下标随机访问的结构中，并且有序。
2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数
据。

所以二分查找在实际应用中价值并没有那么大，这也就体现出了平衡二叉搜索树的价值。

3.二叉搜索树的实现

3. 1.二叉搜索树的插入

插入的具体过程如下：
1. 树为空，则直接新增结点，赋值给root指针。
2. 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）；如果不插入，直接退出循环。

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

为了保持二叉搜索树的的特性，二叉搜索树不允许在任意位置插入。二叉搜索树的插入，我们规定比当前值小往左走，比当前值大往右走。

如果树为空，我们直接插入；如果不为空，我们需要根据二叉树的特性（比当前值小往左走，比当前值大往右走），先进行遍历，找到要插入值所在位置，但这时我们是无法知道插入节点再父节点的左子树还是右子树上，所以我们还记录一下当前插入位置的父节点，判断一下插入位置在左子树还是右子树上。

3.2. 二叉搜索树的查找

1. 从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。
2. 最多查找高度次，走到到空，还没找到，这个值不存在。
3. 如果不支持插入相等的值，找到x即可返回
4. 如果支持插入相等的值，意味着有多个x存在，一般要求查找按中序遍历的第一个x。如下图，查找3，要找到1的右孩子的那个3返回

注：因为按照比根植小的插入在左子树，比跟大的插入在右子树，所以对于任意的树来说始终满足左子树<根<右子树，因此当我们按照中序遍历的结果就是一个由小到大的有序数组，因此如果支持插入相等的值，我们返回中序遍历的第一个值，剩下的值都可以++遍历获得。

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;//遍历到空节点，找不到该值。
}

3.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右子树的值最小结点R(最左结点)替代N，因为这两个结点中任意一个，放到N的位置，都满足二叉搜索树的规则（中间根节点的值比左子树大，比右子树小）。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合情况2或情况3，可以直接删除。

bool Erase(const K& key)
{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{// 删除// 左为空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* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}return true;}}return false;
}

3.4. 二叉搜索树的实现代码

namespace key
{template<class K>struct BSTNode{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}};// Binary Search Tree// Keytemplate<class K>class BSTree{//typedef BSTNode<K> Node;using Node = BSTNode<K>;public: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;}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;//遍历到空节点，找不到该值。}bool Erase(const K& key){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{// 删除// 左为空// 0-1个孩子的情况// 删除情况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{// 左右都不为空// 2个孩子的情况// 删除情况4，替换法删除// 假设这里我们取右子树的最小结点作为替代结点//去删除// 这里尤其要注意右子树的根就是最小情况的情况//的处理，对应图中删除8的情况// 一定要把cur给replaceParent，否会报错。Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}return true;}}return false;}void InOrder()//中序遍历，遍历出来的一组数据是有序的{_InOrder(_root);//_root是私有的，在外部无法获取，因此这里我们可以套一层cout << endl;}private:void _InOrder(Node* root)//递归方式进行中序遍历{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;};
}

4. 二叉搜索树key和key/value两种使用场景

4.1 key搜索场景：

当只有key作为关键码，二叉搜索树节点结构中只需要存储key，关键码即为需要搜索到的值。

这种搜索场景下，我们往往是只需要判断某一数据释放存在在数据库中，即只需要判断key在不在二叉搜索树已保存的节点数据中。

key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，因此key只是作为标识，方便我们判断对应数据是否在数据库中，没有修改的需要，同时直接修改节点存储的key就破坏搜索树结构左子树值<根值<右子树的特性了。

场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌，在二叉搜索树中查找是否存在对应车牌的节点，在则抬杆，不在则提示非本小区车辆，无法进入。
场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。

4.2 key/value搜索场景：

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

key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，因为二叉搜索树中根据key来插入查找对应节点，直接修改key破坏搜索树结构了，但是可以修改value，value只是存储的对应数据，不起到标识的作用。

场景1：简单中英互译字典，二叉搜索树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时根据输入英文key来查找，则同时查找到了英文对应的中文value,返回value。
场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌key和入场时间value，出口离场时，扫描车牌key，在二叉搜索树中查找对应车牌key，然后找到对应入场时间value，用当前时间-入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。
场景3：统计一篇文章中单词出现的次数，读取一个单词key，在二叉搜索树中查找单词key是否存在，不存在这个说明第一次出现，单词存在，则++单词对应的次数value。

4.3 key/value二叉搜索树代码实现

key/value二叉搜索树代码与前面key二叉搜索树逻辑一直，只是节点中多存储value

namespace key_value
{template<class K, class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};// Binary Search Tree// Key/valuetemplate<class K, class V>class BSTree{//typedef BSTNode<K> Node;using Node = BSTNode<K, V>;public:// 强制生成构造BSTree() = default;//有拷贝构造，不再生成默认构造，强制生成BSTree(const BSTree& t)//深拷贝、拷贝构造{_root = Copy(t._root);}BSTree& operator=(BSTree tmp){swap(_root, tmp._root);//现代写法，直接交换根节点指向return *this;}~BSTree(){Destroy(_root);//后续遍历释放资源_root = nullptr;}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->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool Erase(const K& key){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{// 删除// 左为空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* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}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->_value << endl;_InOrder(root->_right);}void Destroy(Node* root)//后序递归释放资源{if (root == nullptr)return;Destroy(root->_left);//先释放左子树Destroy(root->_right);//再释放右子树delete root;//释放根节点}Node* Copy(Node* root)//前序遍历递归、拷贝构造{if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;};
}