正文
1. 二叉搜索树的概念
二叉搜索树（Binary Search Tree, BST）又称二叉排序树。它要么是一棵空树，要么满足以下性质：
- 若左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
- 若右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
- 左右子树也分别为二叉搜索树。
关于相等值的处理，具体取决于使用场景的定义。后续学习的 std::set/std::map 不支持插入相等值，而 std::multiset/std::multimap 支持插入相等值。
2. 二叉搜索树的性能分析
在最优情况下，二叉搜索树接近完全二叉树，其高度为 log₂N；而在最差情况下，树退化为单支树（类似链表），高度为 N。
因此，综合而言，二叉搜索树增删查改的时间复杂度介于 O(logN) 到 O(N) 之间。
单纯的二叉搜索树效率在某些极端数据下无法满足要求，这也是后续衍生出平衡搜索二叉树（如 AVLTree、红黑树 RBTree）的原因，它们通过特殊设计将效率稳定在 log₂N 级别。
大家可能有个疑问：既然有了时间复杂度为 logN 的二分查找算法，为什么还要设计搜索二叉树？
二分查找的缺陷：
- 需要存储在支持下标随机访问的结构中，并且必须有序，例如有序数组。
- 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除通常需要挪动大量数据。
正是二分查找的这些缺陷体现了二叉搜索树的价值。
3. 二叉搜索树的插入
插入过程遵循以下逻辑：
- 若树为空，则直接新增结点，赋值给 root 指针。
- 若树不空，按二叉搜索树性质比较：插入值比当前结点大往右走，小往左走。
- 找到空位置后插入新结点。
- 如果支持插入相等的值，插入值跟当前结点相等时可以往右或往左走，但需保持逻辑一致性。
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
基于上述数据的二叉搜索树结构如下：
此时再插入 16 和 13：
4. 二叉搜索树的查找
从根开始比较：
- 若 x 比根的值大，则往右边查找。
- 若 x 比根的值小，则往左边查找。
- 最多查找高度次，走到空节点还没找到，说明该值不存在。
如果不支持插入相等值，找到 x 即可返回；如果支持插入相等值，意味着有多个 x 存在，一般要求查找中序的第一个 x。
遍历方式包括前序（根左右）、中序（左根右）、后序（左右根）。
5. 二叉搜索树的删除
首先查找元素是否在树中，如果不存在则返回 false。如果存在，根据要删除的结点 N 的孩子情况分四种处理：
- 要删除结点 N 左右孩子均为空。
- 要删除的结点 N 左孩子为空，右孩子不为空。
- 要删除的结点 N 右孩子为空，左孩子不为空。
- 要删除的结点 N 左右孩子均不为空。
在代码实现上，其实可以划分为两种情况：
- 没有孩子和只有一个孩子：视为一种情况，因为没有孩子可视作只有一个孩子是 nullptr。
- 有两个孩子：无法直接删除，需要使用替换法。
解决方案：
第一种情况：以只有右孩子为例，把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点。没有孩子时，N 结点的父亲对应孩子的指针指向 nullptr，符合逻辑。
第二种情况：无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除。找 N 左子树的值最大结点 R（最右结点）或者 N 右子树的值最小结点 R（最左结点）替代 N。因为这两个结点中任意一个放到 N 的位置，都满足二叉搜索树的规则。替代 N 的意思就是 N 和 R 的两个结点的值交换，转而变成删除 R 结点。
6. 二叉搜索树 key 和 key/value 使用场景
6.1 key 搜索场景
只有 key 作为关键码，结构中只需要存储 key 即可。关键码即为需要搜索到的值，搜索场景只需要判断 key 在不在。
key 的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改 key 会破坏搜索树结构。
简单举例：
- 车牌抬杆识别系统，判断车牌字符是否存在（后台将车牌号录入搜索二叉树）。
- 检查一篇英文文章是否有错（词典录入二叉树）。
- 编译器的语法检查（将库、自定义、关键词放入二叉树）。
总之，key 的搜索二叉树一般用于快速查询数据是否存在。
6.2 key/val 搜索场景
每一个关键码 key，都有与之对应的值 value，value 可以是任意类型对象。树的结构中除了需要存储 key 还要存储对应的 value，增/删/查还是以 key 为关键字走二叉搜索树的规则进行比较，可以快速找到 key 对应的 value。
key/value 的搜索场景实现的二叉搜索树支持修改 value，但是不支持修改 key，修改 key 会破坏搜索树性质。
简单举例：
- 检查中英文互译系统（key 即英文，value 即中文）。
- 商场车库系统（收费自助类，通过存车票号和入场时间计算租金）。
- 读取一篇文章中英文出现的次数。
7. 二叉搜索树的实现代码
7.1 key 模型代码实现
这里的 set 不是完全 set 的底层封装，本代码只是二叉搜索树 key 模型的实现代码。
#pragma once
#include <assert.h>
#include <iostream>
using namespace std;
// 去重版 set
namespace twg {
template<class K>
struct BSTnode {
K _key;
BSTnode* left;
BSTnode* right;
BSTnode(const K& key = K()) : _key(key), left(nullptr), right(nullptr) {}
};
template<class K>
class set {
typedef BSTnode<K> Node;
public:
bool Insert(const K& key) {
if (_root == nullptr) {
_root = new Node(key);
}
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
parent = cur;
cur = cur->right;
} else {
return true; // 已存在
}
}
cur = new Node(key);
if (parent->right == nullptr) {
parent->right = cur;
} else {
parent->left = cur;
}
return true;
}
bool Erase(const K& key) {
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
parent = cur;
cur = cur->right;
} else {
if (cur->left == nullptr) {
if (parent == nullptr) {
_root = cur->right;
} else if (parent->left == cur) {
parent->left = cur->right;
} else {
parent->right = cur->right;
}
delete cur;
return true;
} else {
Node* rightMinf = cur;
Node* rightMin = cur->left;
while (rightMin->left) {
rightMinf = rightMin;
rightMin = rightMin->left;
}
if (parent->left == cur) {
parent->left = rightMin;
} else {
parent->right = rightMin;
}
rightMinf->left = rightMin->right;
rightMin->left = cur->left;
rightMin->right = cur->right;
delete cur;
return true;
}
}
}
cout << "没有该节点" << endl;
return false;
}
bool Find(const K& key) {
Node* cur = _root;
while (cur) {
if (key < cur->_key) {
cur = cur->left;
} else if (key > cur->_key) {
cur = cur->right;
} else {
return true;
}
}
return false;
}
void Inorder() {
assert(_root);
inorder(_root);
}
private:
void inorder(const Node* root) {
if (root == nullptr) return;
inorder(root->left);
cout << root->_key << endl;
inorder(root->right);
}
Node* _root = nullptr;
};
}
// 模拟 unordered_set 即不去重版
namespace Twg {
template<class K>
struct BSTnode {
K _key;
BSTnode* left;
BSTnode* right;
BSTnode(const K& key = K()) : _key(key), left(nullptr), right(nullptr) {}
};
template<class K>
class set {
typedef BSTnode<K> Node;
public:
bool Insert(const K& key) {
if (_root == nullptr) {
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key <= cur->_key) {
parent = cur;
cur = cur->left;
} else {
parent = cur;
cur = cur->right;
}
}
cur = new Node(key);
if (parent->right == nullptr) {
parent->right = cur;
} else {
parent->left = cur;
}
return true;
}
bool Erase(const K& key) {
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
parent = cur;
cur = cur->right;
} else {
if (cur->left == nullptr) {
if (parent == nullptr) {
_root = cur->right;
} else if (parent->left == cur) {
parent->left = cur->right;
} else {
parent->right = cur->right;
}
delete cur;
return true;
} else {
Node* rightMinf = cur;
Node* rightMin = cur->left;
while (rightMin->left) {
rightMinf = rightMin;
rightMin = rightMin->left;
}
if (parent->left == cur) {
parent->left = rightMin;
} else {
parent->right = rightMin;
}
rightMinf->left = rightMin->right;
rightMin->left = cur->left;
rightMin->right = cur->right;
delete cur;
return true;
}
}
}
cout << "没有该节点" << endl;
return false;
}
bool Find(const K& key) {
Node* cur = _root;
while (cur) {
if (key < cur->_key) {
cur = cur->left;
} else if (key > cur->_key) {
cur = cur->right;
} else {
return true;
}
}
return false;
}
void Inorder() {
assert(_root);
inorder(_root);
}
private:
void inorder(const Node* root) {
if (root == nullptr) return;
inorder(root->left);
cout << root->_key << endl;
inorder(root->right);
}
Node* _root = nullptr;
};
}
7.2 key/val 代码实现
#pragma once
#include <iostream>
using namespace std;
namespace twg {
template<class K, class V>
struct BSTnode {
K _key;
V _val;
BSTnode* left;
BSTnode* right;
BSTnode(const K& key, const V& val) : _key(key), _val(val), left(nullptr), right(nullptr) {}
};
template<class K, class V>
class map {
typedef BSTnode<K, V> Node;
public:
map() = default;
~map() { Destory(_root); }
map(const map<K, V>& a) {
_root = Copy(a._root);
}
map<K, V>& operator=(map<K, V> a) {
std::swap(_root, a._root);
return *this;
}
bool Insert(const K& key, const V& val) {
if (_root == nullptr) {
_root = new Node(key, val);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key <= cur->_key) {
parent = cur;
cur = cur->left;
} else {
parent = cur;
cur = cur->right;
}
}
cur = new Node(key, val);
if (cur->_key <= parent->_key) {
parent->left = cur;
} else {
parent->right = cur;
}
return true;
}
bool Find(const K& key) {
Node* cur = _root;
while (cur) {
if (key < cur->_key) {
cur = cur->left;
} else if (key > cur->_key) {
cur = cur->right;
} else {
return true;
}
}
return false;
}
bool Erase(const K& key) {
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
parent = cur;
cur = cur->right;
} else {
if (cur->right != nullptr) {
if (parent == nullptr) {
_root = cur->right;
} else if (parent->left == cur) {
parent->left = cur->right;
} else {
parent->right = cur->right;
}
delete cur;
return true;
} else {
Node* leftMax = cur->right;
Node* leftMaxf = cur;
while (leftMax->right) {
leftMaxf = leftMax;
leftMax = leftMax->right;
}
cur->_val = leftMax->_val;
cur->_key = leftMax->_key;
leftMaxf->right = leftMax->left;
delete leftMax;
return true;
}
}
}
cout << "没有该节点，删除失败" << endl;
return false;
}
V& operator[](const K& key) {
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (key < cur->_key) {
parent = cur;
cur = cur->left;
} else if (key > cur->_key) {
parent = cur;
cur = cur->right;
} else {
return cur->_val;
}
}
cur = new Node(key, V());
if (parent == nullptr) {
_root = cur;
} else {
if (key < parent->_key) parent->left = cur;
else parent->right = cur;
}
return cur->_val;
}
void Inorder() {
_inorder(_root);
cout << endl;
}
private:
Node* Copy(const Node* root) {
if (root == nullptr) return nullptr;
Node* newNode = new Node(root->_key, root->_val);
newNode->left = Copy(root->left);
newNode->right = Copy(root->right);
return newNode;
}
void Destory(Node* root) {
if (root == nullptr) return;
Destory(root->left);
Destory(root->right);
delete root;
}
void _inorder(const Node* root) {
if (root == nullptr) return;
_inorder(root->left);
cout << root->_key << ": " << root->_val << endl;
_inorder(root->right);
}
Node* _root = nullptr;
};
}
结语
二叉搜索树的'左小右大'特性背后，是高效数据查询的核心逻辑。它既弥补了二分查找在插入删除上的短板，也为后续学习平衡树（AVL、红黑树）打下基础。掌握双场景适配与增删查改的边界处理后，你已能应对简单的数据存储需求。