📌 个人主页： 孙同学_
🔧 文章专栏：C++
💡 关注我，分享经验，助你少走弯路

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它要么是一棵空树，要么是具有一下性质的二叉树

• 若它的左子树不为空，则左子树上所有节点的值都小于根结点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根结点的值
• 它的左右子树分别为二叉搜索树
• 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体要看使用场景的定义，map/set/multimap/multiset系列容器底层就是二叉搜索树,其中map/set不支持插入相等值，multimap/multiset支持插入相等值

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

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：log2 N
最差情况下，二叉搜索树退化为单指树，其高度为：N
所以综合而言二叉搜索树增删查改的时间复杂度为：O(N)

这样的效率显然是无法满足我们的需求的，后面的平衡二叉搜索树AVL树和红黑树才能适用于才内存中存储和搜索数据。

• 二分查找也能实现O（log2N）级别的查找效率，但是二分查找有两大缺陷：

1. 需要存储在支持下标随机访问的结构中，并且有序
2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除需要挪动数据。

3. 二叉搜索树的插入

插入的具体过程如下：

1. 树为空，则直接新增结点，赋值给root指针。
2. 树不为空，则按照二叉搜索树的性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置插入新结点。
3. 如果支持插入相等的值，插入值和当前结点的值相等，可以往左走也可以往右走，找到空位置，插入新结点。（注意：插入时要保证逻辑的一致性，不要一次往左走，一次往右走）

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

4. 二叉搜素树的查找

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

5. 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回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，可以直接删除。

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

template<class K>
struct BSTNode//定义搜索二叉树的结点
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};//class SearchBinaryTree
template<class K>
class BSTree
{typedef BSTNode<K> Node;
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* 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 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{//删除if (cur->_left == nullptr) //左为空，父亲指向我的右{if (cur == _root){_root = cur->_right;}else{if (cur == parent->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;}else if (cur->_right == nullptr) //右为空，父亲指向我的左{if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;}else //左右都不为空{//找右子树的最小结点（最左结点）替代我的位置Node* minRightParent = cur;Node* minRight = cur->_right;while (minRight->_left){minRightParent = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (minRightParent->_left == minRight){minRightParent->_left = minRight->_right;}else{minRightParent->_right = minRight->_right;}delete minRight;}return true;}}return false;}void InOrder() //外面不能访问私有，但是里面可以{_InOrder(_root);std::cout << std::endl;}private://中序遍历void _InOrder(Node* root) //这里有个问题就是我在外面想传这个根结点，但是根节点是私有的，所以有两种解决方案1.写一个GetRoot2.我们再套一层{if (root == nullptr){return;}_InOrder(root->_left);std::cout << root->_key << " ";_InOrder(root->_right);}Node* _root = nullptr;};

7. 二叉搜索树的key和key/value对的使用场景

7.1 key搜索场景

当数据结构的核心需求是快速判断元素是否存在、维护有序性，或者不需要关联额外数据，仅使用key即可。

典型场景：

• 集合（Set）的实现： 例如std::set。
• 存在性检查： 如检测某个用户名是否已经被注册。
• 有序遍历： 直接按key的顺序输出元素（如从下到大遍历）。
• 去重操作： 自动过滤重复的key，保证唯一性。

7.2 key/value对的场景

当需要通过key关联并管理额外数据时，使用key/value对。此时BST类似于一个有序的字典（Map）,例如std::map

典型场景：

• 字典/映射结构： 存储值对，如学号（key）关联学生信息（value）。
• 词频统计： 单词（key）关联出现次数（value）。
• 缓存系统： 通过key快速检索缓存的值。
• 数据库索引： 通过key（如主键）快速定位记录。

7.3 核心区别总结

特性	仅 Key	Key/Value 对
数据结构目的	维护有序的唯一元素集合	建立键到值的映射关系
典型操作	插入、删除、存在性检查	插入、删除、按 key 查 value
应用举例	用户名的唯一性校验	学号关联学生详细信息
库实现	TreeSet（Java）	TreeMap（Java）

7.4 如何选择？

• 仅需 key：如果问题仅涉及元素的存在性、有序性或去重。
• 需要 key/value：如果问题需要通过 key 快速访问或修改关联的复杂数据。

7.5 key/value对的代码实现

template<class K,class V>
struct BSTNode//定义key/value对的结点
{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){}
};
//class SearchBinaryTree
template<class K,class V>
class BSTree
{typedef BSTNode<K,V> Node;
public: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* 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 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 (cur == parent->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;}else if (cur->_right == nullptr) //右为空，父亲指向我的左{if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;}else //左右都不为空{//找右子树的最小结点（最左结点）替代我的位置Node* minRightParent = cur;Node* minRight = cur->_right;while (minRight->_left){minRightParent = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (minRightParent->_left == minRight){minRightParent->_left = minRight->_right;}else{minRightParent->_right = minRight->_right;}delete minRight;}return true;}}return false;}void InOrder() //外面不能访问私有，但是里面可以{_InOrder(_root);std::cout << std::endl;}private://中序遍历void _InOrder(Node* root) //这里有个问题就是我在外面想传这个根结点，但是根节点是私有的，所以有两种解决方案1.写一个GetRoot2.我们再套一层{if (root == nullptr){return;}_InOrder(root->_left);std::cout << root->_key << " " << root->_value << std::endl;;_InOrder(root->_right);}Node* _root = nullptr;
};

int main()
{//1.查找单词BSTree<string, string> dict;//BSTree<string, string> copy = dict;dict.Insert("left", "左边");dict.Insert("right", "右边");dict.Insert("insert", "插入");dict.Insert("string", "字符串");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << "->" << ret->_value << endl;}else{cout << "无此单词，请重新输入" << endl;}}//2.统计出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int> countTree;for (auto& e : arr){//先查找水果在不在搜索树中//不在，则第一次出现，插入到搜索树中//在，则只需要++查找的水果的次数BSTNode<string, int>* ret = countTree.Find(e);if (ret == nullptr){countTree.Insert(e, 1);}else{ret->_value++;}}countTree.InOrder();return 0;}

---

👍 如果对你有帮助，欢迎：

• 点赞 ⭐️
• 收藏 📌
• 关注 🔔