目录

二叉搜索树

概念性质

性能分析

实现代码

前置准备

插入

查找

删除（重点）

​编辑

key和key/value的使用场景

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

---

二叉搜索树

概念性质

二叉搜索树（Binary Search Tree，简称BST），也称为二叉排序树或者二叉查找树，是一种具有特殊性质的二叉树，可以用于数据的快速查找、插入和删除。

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

性质

• 节点的键值大于左子树上任何节点的键值。
• 节点的键值小于右子树上任何节点的键值。
• 左右子树也必须分别为二叉搜索树。
• 左子树所有节点的键值比根节点的键值小，右子树所有节点的键值比根节点的键值大。

优点

• 有序性：易于实现有序相关操作，如查找最大最小值、元素排序等。
• 搜索效率：在平衡的情况下，搜索、插入和删除操作的时间复杂度为O(log N)。
• 动态性：可以动态插入和删除数据。

缺点

• 会退化：在最坏的情况下（输入数据有序或逆序），二叉搜索树会退化成单链表，操作的时间复杂度退化O(N)。
• 需要平衡：为了保持高效的操作，可能需要通过额外的算法（AVL树、红黑树）来保持树的平衡。

性能分析

最优情况下，二叉搜索树接近为完全二叉树，其高度为logN。

最差情况下，二叉搜索树退化成近似链或者链，其高度为N。

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

只有在平衡的情况下，二叉搜索树增删查改的时间复杂度为O(log N)。

 二分查找也能实现O(log N)级别对的查找效率，但二分查找有两个缺点：

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

2.插入删除数据需要挪动数据，效率较低。

实现代码

我们来实现一棵没有冗余的二叉搜索树（不允许相同值的插入）。

前置准备

二叉搜索树的节点

template<class K>
struct BSTNode
{K _key;BSTNode* _left;BSTNode* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};

二叉搜索树

​
template<class K>
class BSTree
{//typedef BSTNode<K> Node;using Node = BSTNode<K>;
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;}void InOrder(){_InOrder(_root);cout << endl;}private: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);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node * _root = nullptr;
};​

要点

1.C++11可以使用using进行重定义。

2.我们写了拷贝构造函数后，就不会生成构造函数了，我们可以使用default强制生成构造函数。

3.拷贝构造需要用到前序遍历，析构、遍历二叉搜索树需要用到中序遍历（中序遍历得到有序的数据），而这都需要用到递归，但是递归需要传递root节点，这几个函数直接传递root节点都会出问题，以析构函数为例子，析构函数是无参的，传了参数就会出问题。所以类里写递归的方达是套多一层函数就行了。

 4.对于赋值重载，传递一个普通的BSTree对象就行了，由于是传值传参，会发生拷贝构造，所以在函数里就有了一个临时的tmp对象，直接将_root与tmp._root的值交换就可以完成赋值重载的目的。（tmp对象在函数结束后就调用析构函数销毁了，也不用我们主动调用了）

5.写一个中序遍历遍历二叉搜索树，以便观察结果。

插入

bool Insert(const K& key)
{//树为空if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;//树不为空，找到应该插入的位置while (cur){//插入的key大于当前节点的key，cur往右走，小于往左走，相等返回flaseif (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);//注意判断新节点连接在parent的左边还是右边if (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;
}

插入有以下几种情况：

1.树为空，新增节点，赋值给root指针。

2.树不为空，按照二叉树的性质，插入值比当前节点大往右走，插入值比当前节点小往左走，找到空位值，插入新节点。

3.如果支持插入相等的值，插入值跟当前节点的值相等，可以往右走也可以往左走，找到空位置插入就行，但要保持二叉搜索树的性质。我们这里实现的二叉搜索树不允许插入相等的值，返回false就行了。

注意插入的时候，因为cur走到空了，说明找到插入位置了，但具体的插入应该是当前节点的父亲节点连接新节点，所以我们还需要一个parent节点记录当前节点的父亲节点。

我们测试一下。

int main()
{BSTree<int> t;int arr[] = { 8, 3, 1, 7, 4, 15, 13 };for (auto e : arr){t.Insert(e);}t.InOrder();return 0;
}

查找

在二叉搜索树查找某个值x就比较简单了，x比当前节点的值大往左走，比当前节点的值小往右走，最多查找高度次，走到空，那就说明没找到，返回false，找到了就返回true。

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

删除（重点）

给定一个元素，删除与该元素相等的节点。

删除操作是二叉搜索树增删查中最为复杂的操作，我应该如下考虑。

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

如果元素存在则有以下情况：（假设删除节点为N）

1. N节点的左孩子为空或者右孩子为空（左右孩子为空的情况也属这类）。
2. N节点的左孩子和右孩子都不为空。

解决方案如下：

• 对于情况1，假如N节点的左孩子为空，把N节点的父亲对应孩子指针指向N的右孩子，删除N节点。（N节点的右孩子为空也类似这样处理）
• 对于情况2，无法直接删除N节点，因为N的两个孩子无处安放，只能用替代法删除。首先找N的左子树的最大节点或者右子树的最小节点（记为R节点），将其替代N节点，然后删除R节点。至于为什么这样做？是因为只有这两个特定节点中的一个去替代N节点才能继续满足二叉搜索树的性质。

删除操作还需思考以下的特殊情况：

1.在情况1的条件下，删除的节点是根节点要特殊处理；要找到N节点的对应孩子指针（判断N节点是父亲的左孩子还是右孩子），因为要把父亲节点和N节点的孩子连接，如果不知道N节点是父亲的左孩子还是右孩子就随便乱连，二叉树就会被破坏。

2.在情况2的条件下，假设找的R节点是右子树的最小节点，N节点的右子树的最小节点就是N节点的右孩子（右子树的第一个节点）的情况，这种情况的存在就导致了在删除R节点时无法确定R节点是其父亲的左孩子还是右孩子，要特殊处理。

该特殊情况如下图：

一般删除的情况：

 

下面看删除的具体代码

bool Erase(const K& key)
{Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else // key == cur->_key; 删除{if (cur->_left == nullptr) //左为空，连接cur->_right{if (cur == _root){_root = cur->_right;}else{//判断要删除的cur节点是parent节点的左节点还是右节点if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr) //右为空，连接cur->_left{if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}}else //左右孩子都不为空{//找替代节点（右子树的最小节点）Node* ReplaceParent = cur; //这里R节点的父亲的初始值不能给成nullptr，不然在特殊情况下会出现解引用空指针的错误Node* Replace = cur->_right;while (Replace->_left){ReplaceParent = Replace;Replace = Replace->_left;}//直接覆盖要删除的节点值cur->_key = Replace->_key;//判断R节点是其父亲的左孩子还是右孩子，连接R节点的右孩子（左为空的情况）if (ReplaceParent->_left == Replace){ReplaceParent->_left = Replace->_right;}else{ReplaceParent->_right = Replace->_right;}delete Replace;}return true;}}return false;
}

测试

int main()
{BSTree<int> t;int arr[] = { 8, 3, 1, 7, 4, 15, 13 };for (auto e : arr){t.Insert(e);}t.InOrder();for (auto e : arr){t.Erase(e);t.InOrder();}return 0;
}

假如我们让R节点的父亲节点的初值给成空指针，编译器是会报警告的。

key和key/value的使用场景

key搜索场景

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

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

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

key/value搜索场景

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

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

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

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

只需要对上面代码做些许修改即可，不过多讲解。

template<class K, class V>
struct BSTNode
{K _key;V _value;BSTNode* _left;BSTNode* _right;BSTNode(const K& key, const V& value):_key(key),_value(value), _left(nullptr), _right(nullptr){}
};template<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){//插入的key大于当前节点的key，cur往右走，小于往左走，相等返回flaseif (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key, value);//注意判断新节点连接在parent的左边还是右边if (key > parent->_key){parent->_right = cur;}else{parent->_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* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else // key == cur->_key; 删除{if (cur->_left == nullptr) //左为空，连接cur->_right{if (cur == _root){_root = cur->_right;}else{//判断要删除的cur节点是parent节点的左节点还是右节点if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr) //右为空，连接cur->_left{if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}}else //左右孩子都不为空{//找替代节点（右子树的最小节点）Node* ReplaceParent = cur; //这里R节点的父亲的初始值不能给成nullptr，不然在特殊情况下会出现解引用空指针的错误Node* Replace = cur->_right;while (Replace->_left){ReplaceParent = Replace;Replace = Replace->_left;}//直接覆盖要删除的节点值cur->_key = Replace->_key;//判断R节点是其父亲的左孩子还是右孩子，连接R节点的右孩子（左为空的情况）if (ReplaceParent->_left == Replace){ReplaceParent->_left = Replace->_right;}else{ReplaceParent->_right = Replace->_right;}delete Replace;}return true;}}return false;}void InOrder(){_InOrder(_root);cout << endl;}private: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;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}private:Node* _root = nullptr;
};

测试

int main()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int> countTree;for (const auto& str : arr){// 先查找水果在不在搜索树中// 1、不在，说明水果第一次出现，则插入<水果, 1>// 2、在，则查找到的结点中水果对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == nullptr){countTree.Insert(str, 1);}else{// 修改valueret->_value++;}}countTree.InOrder();BSTree<string, int> copy = countTree;copy.InOrder();return 0;
}

---

拜拜，下期再见😏

摸鱼ing😴✨🎞