在数据结构与算法的世界里，二叉搜索树（Binary Search Tree, BST）无疑是我们手中的一把利剑。它以其高效的查找、插入和删除性能（在平衡状态下为 O(log n)）而闻名。然而，正如我们在实际开发中经常遇到的那样，理论模型与实际应用之间总存在着一些微妙的差距。
你是否遇到过这样的场景：当你试图向 BST 中插入一个已经存在的键时，标准的定义会告诉你：“嘿，这个键已经存在了，它是唯一的。”但在现实世界中，数据往往不是唯一的。比如，我们需要建立一个商品销售排行榜，同一个商品可能会被多次购买；或者是建立一个用户访问日志，同一个用户可能会多次访问。在这些情况下，简单地忽略重复值或者报错显然不是我们想要的结果。
在这篇文章中，我们将深入探讨一个经典且实用的问题：如何在二叉搜索树中优雅地处理重复值？ 我们将从 BST 的基本定义出发，分析为什么标准定义会“排斥”重复值，然后带你一起探索两种主要的解决方案——一种直观但存在隐患，另一种高效且被广泛应用。我们不仅会讨论理论，还会通过完整的代码示例，带你一步步实现这些逻辑。
为什么 BST 默认排斥重复值？
首先，让我们快速回顾一下 BST 的核心属性，这有助于我们理解后续的解决方案。在一个标准的 BST 中，对于任意一个节点：
- 其左子树中的所有节点的键都必须小于该节点的键。
- 其右子树中的所有节点的键都必须大于该节点的键。
请注意这里的“严格小于”和“严格大于”。正是这种严格的定义，保证了 BST 中每个键的唯一性。如果我们在遇到重复键时强行插入，就会破坏这个结构，使得基于大小关系的查找逻辑失效。
那么，当业务逻辑要求我们必须处理重复值时（即“增加一个带有该值的键”），我们该怎么做呢？
方法一：朴素方法 —— 侧放策略（向右子树妥协）
核心思想：遇到重复值时，不要停下来，而是继续将其插入到右子树中（当然，统一放到左子树也是可以的，关键在于保持一致性）。
这种方法对标准 BST 插入算法的修改非常小。通常情况下，如果 INLINECODEb750f40e，标准做法是直接返回或报错。而在“侧放策略”中，我们只需要把这行判断逻辑改为：INLINECODE8180c54f。
#### 它是如何工作的？
让我们通过一个具体的例子来看看。假设我们要按顺序插入以下键：
12, 10, 20, 9, 11, 10, 12, 12
如果采用“右子树策略”，树的生长过程如下：
- 插入 12：作为根节点。
- 插入 10：10 < 12，放在 12 的左边。
- 插入 20：20 > 12，放在 12 的右边。
- 插入 9：9 < 10，放在 10 的左边。
- 插入 11：11 > 10，放在 10 的右边。
- 插入第二个 10：10 == 当前节点(10)。根据策略，我们将其视为“大于或等于”，移动到右子树。在右子树中，遇到了 11。10 < 11，所以它最终成为了 11 的左孩子。
- 插入第二个 12：12 == 根节点(12)。移动到右子树，遇到 20。12 < 20，成为 20 的左孩子。
#### 这种方法存在的问题
虽然这种方法实现起来很快，但作为一名有追求的开发者，你可能一眼就看出了它的隐患：
- 树的高度增加：如果有大量的重复数据，这些重复值会形成一条长长的“链”，而不是分散在树中。最坏的情况下，如果我们插入了一万个 10，树的高度会变成一万。这会让 BST 退化为链表，将查找性能从 O(log n) 拉低到 O(n)。
- 自平衡树的噩梦：如果你使用的是 AVL 树或红黑树，这种策略会变得非常棘手。因为这些树依赖于旋转来保持平衡。当重复键存在时，旋转操作可能会改变树的子结构，导致原本在“右边”的重复键跑到了“左边”，从而破坏了 BST 的查找语义（你本来以为在右边找，结果旋转后去左边才找得到）。
方法二：进阶方案 —— 计数器策略（最佳实践）
核心思想：不要重复存储节点。相反，我们让每个节点“记住”自己出现了多少次。
这是我们在处理重复数据时最推荐的方法。我们在每个节点的结构中增加一个 count 字段（计数器）。
- 当插入一个已存在的键时，我们不再创建新节点，而是将现有节点的
count加 1。 - 当删除一个键时，如果 INLINECODE20143779 大于 1，我们只需将 INLINECODE3e220a77 减 1；只有当
count减为 0 时，我们才真正从树中移除这个节点。
#### 为什么这是更好的方案？
- 保持树的结构紧凑：无论有多少个重复值，它们在逻辑上都只占用一个节点的位置。这意味着树的高度始终由不同键的数量决定，而不是总数据量决定。这极大地保证了 O(log n) 的性能。
- 操作逻辑统一：它完美契合自平衡 BST（如 AVL 和红黑树），因为我们不需要改变树的拓扑结构来处理重复值，旋转逻辑不受影响。
#### 代码实现：一步步带你写
让我们用 C++ 来实现这个带有计数功能的 BST。我们将重点关注插入、删除和查找的逻辑。
首先，定义节点结构。注意我们在构造函数中初始化了 count = 1。
#include
using namespace std;
// 定义树节点
struct Node {
int key;
int count; // 计数器，记录该键出现的次数
Node *left;
Node *right;
// 构造函数
Node(int k) {
key = k;
count = 1; // 新节点初始计数为 1
left = right = nullptr;
}
};
#### 1. 插入操作
在插入时，我们递归地寻找合适的位置。如果我们找到了键值相同的节点，我们只增加计数，然后直接返回。这避免了不必要的节点创建和树的深度增加。
// 插入操作
Node* insert(Node* root, int key) {
// 1. 如果树为空，创建新节点
if (root == nullptr) {
return new Node(key);
}
// 2. 如果键值已存在，增加计数并返回
// 这是我们处理重复值的核心逻辑
if (key == root->key) {
(root->count)++;
return root;
}
// 3. 否则，递归地在左子树或右子树中插入
if (key key) {
root->left = insert(root->left, key);
} else {
root->right = insert(root->right, key);
}
// 返回（可能更新后的）根节点
return root;
}
#### 2. 查找操作
查找操作几乎与标准 BST 相同，唯一的区别在于我们不仅要找到节点，还要知道它出现了多少次。这极大地增强了查找功能的信息量。
// 查找操作：返回键为 key 的节点数量
// 如果不存在返回 0，否则返回节点的 count 字段
int search(Node* root, int key) {
// 基准情况：树为空或找到目标
if (root == nullptr || root->key == key) {
// 如果 root 为 nullptr，返回 0；否则返回计数
return root == nullptr ? 0 : root->count;
}
// 如果 key 小于当前节点的 key，在左子树查找
if (root->key > key) {
return search(root->left, key);
}
// 如果 key 大于当前节点的 key，在右子树查找
else {
return search(root->right, key);
}
}
#### 3. 删除操作 —— 最复杂的部分
删除逻辑需要仔细处理。我们有几种情况：
- 节点不存在：直接返回。
- 节点存在，且 count > 1：这是“软删除”。我们只需将
count减 1，不需要改变树结构。 - 节点存在，且 count == 1：这是真正的“硬删除”。我们需要从树中彻底移除这个节点。这涉及到标准的 BST 删除逻辑（寻找后继节点来替换当前节点等）。
下面是详细的实现代码，包含了寻找最小节点的辅助函数（用于寻找后继）。
// 辅助函数：找到给定树中键值最小的节点
Node* minValueNode(Node* node) {
Node* current = node;
// 一直向左走，直到没有左孩子
while (current && current->left != nullptr) {
current = current->left;
}
return current;
}
// 删除操作
Node* deleteNode(Node* root, int key) {
// 1. 基准情况：树为空
if (root == nullptr) {
return root;
}
// 2. 递归寻找要删除的键
if (key key) {
// 目标在左子树
root->left = deleteNode(root->left, key);
} else if (key > root->key) {
// 目标在右子树
root->right = deleteNode(root->right, key);
} else {
// 3. 找到了目标节点 (key == root->key)
// 情况 A：重复值计数大于 1
if (root->count > 1) {
(root->count)--;
return root;
}
// 情况 B：计数为 1，需要真正删除该节点
// 此时 root->count 一定是 1（或者我们可以把它当作 0）
// 节点只有一个子节点或没有子节点
if (root->left == nullptr) {
Node* temp = root->right;
delete root; // 释放内存
return temp;
} else if (root->right == nullptr) {
Node* temp = root->left;
delete root; // 释放内存
return temp;
}
// 节点有两个子节点：获取中序后继（右子树中的最小值）
Node* temp = minValueNode(root->right);
// 复制后继的内容到当前节点
// 注意：这里我们复制 key 和 count。因为后继节点可能是重复值！
root->key = temp->key;
root->count = temp->count;
// 为了防止重复计数问题，我们将后继节点的 count 设置为 1
// （或者直接作为唯一的节点来删除）
// 实际上，因为我们把后继节点的数据“搬”过来了，
// 我们需要在右子树中删除原来的后继节点。
// 这里的技巧是：我们再次调用 deleteNode，传入 temp->key。
// 既然 temp->key 已经被“搬运”上来了，右子树里的那个 temp 节点就必须被移除。
root->right = deleteNode(root->right, temp->key);
}
return root;
}
实战演练与测试
为了验证我们的逻辑，让我们写一个简单的测试用例，模拟数据的插入和删除。
// 中序遍历打印树 (验证结构)
void inorder(Node* root) {
if (root != nullptr) {
inorder(root->left);
cout << "(" <key << ", " <count <right);
}
}
int main() {
/* 让我们创建如下序列的 BST:
12(1)
/ \
10(2) 20(1)
/ \ /
9(1) 11(1) 12(1)
注意：这里我们用“朴素方法”里提到的序列 12, 10, 20, 9, 11, 10, 12
来测试“计数器方法”。
*/
Node* root = nullptr;
root = insert(root, 12);
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 9);
root = insert(root, 11);
root = insert(root, 10); // 插入重复的 10
root = insert(root, 12); // 插入重复的 12
cout << "中序遍历: ";
inorder(root);
// 预期输出: (9, 1) (10, 2) (11, 1) (12, 2) (20, 1)
cout << endl;
// 测试查找
cout << "查找 10 的计数: " << search(root, 10) << endl;
cout << "查找 99 的计数: " << search(root, 99) << endl;
// 测试删除
cout << "
删除值为 10 的节点..." << endl;
root = deleteNode(root, 10);
cout << "删除后的中序遍历: ";
inorder(root);
// 预期输出: (9, 1) (10, 1) (11, 1) (12, 2) (20, 1)
cout << endl;
cout << "再次删除值为 10 的节点..." << endl;
root = deleteNode(root, 10);
cout << "删除后的中序遍历: ";
inorder(root);
// 预期输出: (9, 1) (11, 1) (12, 2) (20, 1)
cout << endl;
return 0;
}
常见陷阱与最佳实践
在处理 BST 重复值时，有几个容易踩的坑，值得你注意：
- 删除时的计数混淆：在删除有两个子节点的节点时（上述代码中的情况 B），很多人容易忘记 INLINECODE52c06e00 这一行。如果你只是简单地把 INLINECODEe6d1cd32 赋值给 INLINECODE5b785002，而保留 INLINECODE2f37b41a 原来的 INLINECODE12b42b00（也就是 1），那么如果后继节点本身是一个计数为 5 的重复节点，你就丢失了 4 个数据！一定要记得复制 INLINECODEb8b8d33f。
- 内存泄漏：在 C++ 中，手动内存管理是必须的。在 INLINECODEa51a31fe 中，当我们确定要移除节点时，务必使用 INLINECODE92290060，否则在小程序里可能看不出来，但在长期运行的服务程序中，这会导致严重的内存泄漏。
- 不要忽视递归的威力：虽然在大型生产环境中我们可能会担心递归导致的栈溢出（极端情况下），但对于绝大多数 BST 实现和学习算法来说，递归代码的可读性和正确性远远优于迭代的版本。当你还在为如何处理父节点指针而焦头烂额时，递归已经帮你优雅地解决了所有问题。
总结
在这篇文章中，我们探讨了如何在二叉搜索树（BST）中处理重复值这一常见但棘手的问题。
我们比较了两种主要策略：
- 侧放策略（朴素方法）：实现简单，但会导致树的高度增加，在数据量大时性能较差，且不适用于自平衡树。
- 计数器策略（推荐方法）：通过在节点中增加
count字段来记录频率。这种方法保持了树的结构紧凑，确保了操作的效率，并且完美兼容 AVL 树和红黑树等高级结构。
作为开发者，理解数据结构背后的权衡是至关重要的。当你下次需要设计一个支持重复元素的有序集合时，希望你能自信地选择“计数器策略”，并用我们今天讨论的代码模式去实现它。
如果你对更高级的平衡树（如 AVL 或红黑树）中的重复值处理感兴趣，不妨尝试将上述逻辑应用到旋转算法中，你会发现计数器带来的便利是显而易见的。