C++算法
C++ 二叉搜索树原理与代码实现
C++ 中二叉搜索树（BST）的概念、性能分析及完整实现。内容涵盖 BST 的定义与性质，最优与最坏情况下的时间复杂度分析，以及插入、查找、删除等核心操作的循环实现逻辑。详细讨论了删除节点时的四种情况及替换策略，并实现了拷贝构造、析构等默认成员函数。此外，文章区分了仅 Key 模型和 Key/Value 模型的应用场景，提供了完整的命名空间代码示例，适用于理解底层数据结构如 map/set 的实现原理。
C++ 中二叉搜索树（BST）的概念、性能分析及完整实现。内容涵盖 BST 的定义与性质，最优与最坏情况下的时间复杂度分析，以及插入、查找、删除等核心操作的循环实现逻辑。详细讨论了删除节点时的四种情况及替换策略，并实现了拷贝构造、析构等默认成员函数。此外，文章区分了仅 Key 模型和 Key/Value 模型的应用场景，提供了完整的命名空间代码示例，适用于理解底层数据结构如 map/set 的实现原理。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
二叉搜索树又称二叉排序树，它或者是一颗空树，或者是具有以下性质的二叉树：若它的左子树不为空，则左子树上所有节点的值都小于等于根节点的值；若它的右子树不为空，则右子树上所有节点的值都大于等于根节点的值；它的左右子树也都是二叉搜索树。二叉搜索树种可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义。后续我们学习 map / set / multimap / multiset 系列容器底层就是二叉搜索树，其中 map / set 不支持插入相等值，multiset / multimap 支持插入相等值。
最优情况下，二叉搜索树为
完全二叉树（或者接近完全二叉树），其高度为：O(log N)。最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：O(N)。
所以综合而言二叉搜索树增删查改时间复杂度为：O(N)
这样的二叉搜索树并不稳定，树的形状与数据的插入顺序息息相关（插入的数据是有序或较为有序的，二叉搜索树就退化成链式结构），这样的效率显然是无法满足时间的需求的。因此后续我们还将学习二叉搜索树的变形：AVL 树 和 红黑树，他们才能适用于我们在内存中存储和搜索数据。
另外需要说明的是，二分查找也可以实现 O(logN) 级别的查找效率，但是二分查找有两大缺陷：需要存储在
支持下标随机访问的结构中，并且有序下插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。（我们查找一个数据往往不是单纯的查找，还要对其进行增删查改等相关操作）
这也就体现出了平衡二叉搜索树的价值。
搜索二叉树分为两种：允许插入相等的值和不允许插入相等的值。一般我们会分开用，实现两份搜索二叉树。本文实现的是不容许数值冗余的搜索二叉树。
首先我们要定义二叉树节点，及二叉搜索树的基本结构。
template <class K>
struct BSTNode {
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key) : _key(key), _left(nullptr), _right(nullptr) {}
};
template <class K>
class BSTree {
using Node = BSTNode<K>;
public:
private:
Node* _root = nullptr;
};
注：关于类型重命名，C++11 给了一个新用法：using。using 与 typedef 的功能是一样的，只有一些细微的差别，现阶段可认为是一样的。
搜索二叉树，模板参数我们就不用 T 了，而用 K。因为一般搜索的时候，我们都要进行一个比较：比他大往右边走，比他小往左边走。我们一般把用来比较的这个值称为 Key，也就是关键字。所以我们一般用 K 来做模版参数。
实现插入要怎么实现呢？前面我们学习二叉树的时候都是用递归，那这里也要用递归吗？可以用。递归的逻辑是这样的：要插入的值比当前根大，递归到其右子树；若比它小递归到其左子树；遇到空就插进去。
但是这里没必要用递归，我们直接用循环就能够搞定。我们最开始定义一个 cur 指针指向树的根，假设现在插入的是 16，cur 指向 8；16 比 8 大，cur 往右边走；若比 cur 小，往左边走，直到遇到空位。既能用循环又能用递归的情况下，我们无脑用循环。因为递归有栈溢出的风险，却需要建立栈帧，消耗一般比循环大。但我们不能直接 new 一个结点给 cur。因为 cur 只是一个临时变量，只给 cur，树并没有将这个节点链接起来，所以我们还要有个指针 parent 记录 cur 的父节点。
当然，还有一种特殊的情况：空树。这时直接让 _root 指向一个 new 出的新节点即可。
bool Insert(const K& key) {
if (nullptr == _root) {
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr) {
if (cur->_key > key) {
parent = cur;
cur = cur->_left;
} else if (cur->_key < key) {
parent = cur;
cur = cur->_right;
} else
return false;
}
if (parent->_key > key)
parent->_left = new Node(key);
else
parent->_right = new Node(key);
return true;
}
如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）
搜索二叉树有一个性质：中序遍历时，是有序的。中序遍历我们前面学习普通二叉树时实现过了，这里就不再过多介绍。
void InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
但是这个中序有一个问题：不好调用。因为想要调用中序来遍历搜索二叉树，要传递一个根节点 root。但是根是私有的，无法外面无法访问。
解决方式如下：友有元提供 Get() 函数
但这些方法或多或少有些麻烦，C++ 解决这种问题时，一般选择在外面套一层函数。
class BSTNode {
public:
void InOrder() { _InOrder(_root); cout << endl; }
private:
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
};
虽然我们在类外不能访问 _root，但是类里面可以啊。这样，对外公开的接口我们就可以不用传根了。
怎样才能找到中序第一个 3 呢？按中序遍历一遍吗？这样太慢了。这里讲一下大致思路，感兴趣的小伙伴可自行实现：查找方式与上述步骤一致，有些许不同。我们知道中序遍历是：左子树、根、右子树，中序往往是先遍历左子树。因此我们按上述方式找到了 8 左节点的 3，还要进入这个 3 的左子树查找；若其左子树中有 3，再进入这个 3 的左子树；若左子树中无 3，则回退，表明这个左子树的根是中序第一个 3。
Node* Find(const K& key) {
Node* cur = _root;
while (cur != nullptr) {
if (key > cur->_key) {
cur = cur->_right;
} else if (key < cur->_key) {
cur = cur->_left;
} else
return cur;
}
return nullptr;
}
二叉搜索树的删除比较麻烦，需分情况讨论要删除的节点 N 左右节点都为空，即叶子节点；要删除的结点 N 左孩子为空，右孩子结点不为空；要删除的结点 N 右孩子为空，左孩子结点不为空；要删除的节点 N 左右子树都不为空。
对应以上四种解决方案：第一种情况：这种情况最好解决，
将 N 节点的父亲对应孩子指针指向空，直接删除 N 节点（情况一可以当成情况二、三来处理，效果是一样的）。第二种情况：把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点。第三种情况：把 N 结点的父亲对应孩子指针指向 N 的左孩子，直接删除 N 结点。第四种情况：无法直接删除 N 节点，因为 N 的两个孩子无处安放，我们可以用替换法删除。找到N 左子树的值最大节点 R（最右节点）或者N 右子树的最小节点 R（最左节点）替代 N，因为这两个节点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代的意思就是 N 和 R 的两个节点的值交换，转而变成删除 R 节点，R 结点符合情况 2 或情况 3，可以直接删除。
首先是查找，代码逻辑与 Find 的实现相似。不同的是，当找到相等的值（走到 else 时），Erase 是进行删除；Find 是直接退出，当走出循环，表示没有找到要删除的值，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 {
// 删除
}
return false;
}
}
左为空： 虽然要删除的节点 N 左为空，但是并不知道 N 节点是父节点 R 的左节点还是右节点，因此需要先进行判断。
// 左树为空
if (cur->_left == nullptr) {
if (parent->_left == cur) {
parent->_left = cur->_right;
} else {
parent->_right = cur->_right;
}
delete cur;
}
右为空： 右为空的判断逻辑与左为空时一样的。
// 右树为空
else if (cur->_right == nullptr) {
if (parent->_left == cur) {
parent->_left = cur->_left;
} else {
parent->_right = cur->_left;
}
delete cur;
}
但是上述情况还有一种坑的情况，如图：假设现在我们要删除的是 8。这时就需要特殊处理，需要更新 _root 了。
// 左树为空
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 = nullptr;
Node* replace = cur->_right;
// replace 不断往右边走
while (replace->_left) {
replaceParent = replace;
replace = replace->_left;
}
// 将替代节点 replace 的 val 值赋值给本来要删除的节点 cur
cur->_key = replace->_key;
// 再删除 replace 节点，此时的 replace 只可能是前三种情况
replaceParent->_left = replace->_right;
delete replace;
}
删除 replace 还有一种很坑的情况：cur 的右孩子就是最左节点。假设我们现在要删除 8。因为 cur 的右孩子就是最左节点，此时并没有进入循环，replaceParent 还是空，执行 replaceParent->_left = replace->_right; 语句就会报错。解决办法就是 replaceParent 初值不要给 nullptr，而是给 cur。最后删除 replace 节点时，因为 replace 是 replaceParent 的右节点，所以应是将 replace 的孩子给 replaceParent 的右孩子，而不是左孩子。所以最后删除 replace 节点时，要判断 replace 是 replaceParent 的左孩子还是右孩子。
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;
else
replaceParent->_right = replace->_right;
delete replace;
}
二叉树的拷贝构造一定要自己实现深拷贝，如果是编译器默认生成的浅拷贝，将是一个大坑。我们使用前序的方式来拷贝：
BSTree(const BSTree& t) { _root = Copy(t._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;
}
注：这里不能用一个一个插入的方式进行拷贝，因为这样的话树的形状就变了。这里拷贝构造我们在外面套一层壳。
这里编译器默认生成的构造函数就能满足我们的需求，但是我们已经实现了拷贝构造，拷贝构造本身也是一种构造，因此编译器就不会再生成构造函数。我们可以用 default 强制编译器生成构造函数。
// 强制生成构造
BSTree() = default;
赋值重载我们直接用现代写法，让拷贝构造去干活。
BSTree& operator=(BSTree tmp) {
swap(_root, tmp._root);
return *this;
}
析构函数，我们一次通过后序的方式遍历所有节点，并将他们释放。
~BSTree() {
Destroy(_root);
_root = nullptr;
}
void Destroy(Node* root) {
if (root == nullptr) return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
同理，析构函数我们在外面套一层外壳。
搜索二叉树的使用场景分为两个：key 搜索场景和 key/value 搜索场景。
key 搜索场景：即只有 key 作为关键值，结构中只需要存储 key 即可，关键值即为需要搜索到的值，搜索场景只需要判断 key 在不在。key 的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改 key 破坏搜索树结构了。
一句话来说 key 搜索场景就是用来判断在不在。
场景一：校区无人值守车库，小区车库只有买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统（后台系统可以用搜索二叉树的结果来存储车牌号），车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。
场景二：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。
key/value 搜索场景：每一个关键值 key，都有与之对应的值 value，value 可以任意类型对象。树结构中（节点）除了需要存储 key 还要存储对应的 value，增/删/查还是以 key 为关键字走二叉搜索树的规则进行比较，可以快速查找到 key 对应的 value。key/value 的搜索场景实现的二叉搜索树支持修改，那时不支持修改 key，修改 key 破坏搜索树结构了，可以修改 value。
场景 1：简单中英互译字典。树的结构中（节点）存储 key（英文）和 value（中文），搜索黑丝输入英文，则同时查找到了引文对应的中文。
场景 2：商场无人值守车库，入口进场时扫描车牌，记录车牌（key）和入场时间（value）；出口离场时，扫描车牌，查找入场时间，用当前时间 - 入场时间计算出停车时长，计算出听出费用，缴费后抬杆，车辆离场。
场景 3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在说明这个单词第一次出现，存在则++单词对应的次数。
key/value 模型的应用： 输入单词，查找单词对应的中文翻译。
void TestBSTree1() {
BSTree<string, string> dict;
dict.Insert("string", "字符串");
dict.Insert("left", "左边");
dict.Insert("insert", "插入");
string str;
while (cin >> str) {
// 搜索二叉树结点的地址
BSTreeNode<string, string>* cur = dict.Find(str);
if (cur) {
cout << cur->_value << endl;
} else {
cout << "没有此单词" << endl;
}
}
}
统计水果个数：
void TestBSTree2() {
// 统计水果的个数
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "苹果", "草莓", "苹果", "草莓" };
BSTree<string, int> countTree;
for (const auto& str : arr) {
// BSTreeNode<string, int>* cur = countTree.Find(str);
auto cur = countTree.Find(str);
// 没有该水果则插入
if (cur == nullptr) {
countTree.Insert(str, 1);
}
// 有该水果则将 value 值++
else {
cur->_value++;
}
}
countTree.InOrder();
}
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
// Key
template <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 {
// 删除
// 左为空
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;
else
replaceParent->_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 << " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
}
namespace key_value {
template <class K, class V>
struct BSTNode {
const 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/value
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) {
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;
else
replaceParent->_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;
};
}