二叉搜索树的原理与实现
一、引入背景
在数据结构中，符号表是常见需求。传统实现方式各有优劣：
- 无序链表：插入时间复杂度为
O(1)，但查找需遍历全部元素，最坏情况为O(N)。 - 有序数组：支持二分查找，查找效率为
O(log N)，但插入时需移动元素，时间复杂度为O(N)。
二叉搜索树（BST）结合两者优点，在理想情况下可实现插入和查找均为 O(log N) 的性能，同时保持键值的自然有序性。
二、核心性质
BST 的关键特征是：对于任意节点，其左子树中所有键均小于该节点键，右子树中所有键均大于该节点键。
这一性质使得从根节点出发，每次比较都能排除一半的候选节点，类似于二分查找。
三、节点结构设计
每个节点包含以下字段：
key：用于比较的键值。val：关联的值。left、right：分别指向左子树和右子树的指针。N：以该节点为根的子树中节点总数。
节点计数满足不变式：
N(x) = N(x.left) + N(x.right) + 1
空节点的 N 值定义为 0，便于递归处理。
四、核心操作实现
1. 查找操作
递归查找基于比较判断方向：
- 若目标键小于当前节点键，向左子树继续查找。
- 若目标键大于当前节点键，向右子树继续查找。
- 相等则命中，返回对应值。
Value* get(Node* x, const Key& key) const {
if (!x) return nullptr;
if (key < x->key)
return get(x->left, key);
else if (x->key < key)
return get(x->right, key);
else
return &x->val;
}
2. 插入操作
插入逻辑与查找一致，直到遇到空链接处创建新节点。回溯过程中更新路径上所有节点的 N 值。
Node* put(Node* x, const Key& key, const Value& val) {
if (!x) return new Node(key, val, 1);
if (key < x->key)
x->left = put(x->left, key, val);
else if (x->key < key)
x->right = put(x->right, key, val);
else
x->val = val;
x->N = size(x->left) + size(x->right) + 1;
return x;
}
3. 删除最小值
通过不断向左走找到最小节点，将其右子树接替原位置。
Node* deleteMin(Node* x) {
if (!x->left) {
Node* right = x->right;
delete x;
return right;
}
x->left = deleteMin(x->left);
x->N = size(x->left) + size(x->right) + 1;
return x;
}
4. 删除任意节点（Hibbard 方法）
当节点有两个子节点时，用其右子树中的最小节点（后继）替换它，并从右子树中删除该后继。
Node* remove(Node* x, const Key& key) {
if (!x) return nullptr;
if (key < x->key)
x->left = remove(x->left, key);
else if (x->key < key)
x->right = remove(x->right, key);
else {
if (!x->right) return x->left;
if (!x->left) return x->right;
Node* t = x;
x = min(t->right);
Node* newNode = new Node(x->key, x->val);
newNode->right = deleteMin(t->right);
newNode->left = t->left;
delete t;
x = newNode;
}
x->N = size(x->left) + size(x->right) + 1;
return x;
}
五、有序操作支持
BST 天然支持按顺序访问数据，主要扩展操作包括：
- 最小/最大键：分别沿左/右链走到末尾。
- floor / ceiling：分别查找小于等于或大于等于给定键的最大/最小键。
- select(k)：获取第
k小的键（从 0 开始）。 - rank(key)：统计小于
key的键的数量。 - 范围查询：使用中序遍历剪枝，仅收集指定区间内的键。
六、性能分析
在随机插入的情况下，树的高度约为 1.39 log₂N，平均查找和插入操作需要约 1.39 log₂N 次比较。
然而，若键按升序或降序插入，树将退化为链表，最坏时间复杂度为 O(N)。
为此，后续章节介绍红黑树等自平衡结构，以保证最坏情况仍为 O(log N)。
七、完整代码示例
以下是完整的模板类实现，包含所有核心功能：
#include <iostream>
#include <string>
#include <vector>
#include <stdexcept>
template <typename Key, typename Value>
class BST {
private:
struct Node {
Key key;
Value val;
Node* left;
Node* right;
int N;
Node(const Key& k, const Value& v) : key(k), val(v), left(nullptr), right(nullptr), N(1) {}
};
Node* root;
int size(Node* x) const { return x ? x->N : 0; }
// 其他私有方法省略...
public:
BST() : root(nullptr) {}
~BST() { destroy(root); }
int size() const { return size(root); }
bool isEmpty() const { return root == nullptr; }
Value* get(const Key& key) const { return get(root, key); }
void put(const Key& key, const Value& val) { root = put(root, key, val); }
void remove(const Key& key) { root = remove(root, key); }
Key min() const { return min(root)->key; }
Key max() const { return max(root)->key; }
std::vector<Key> keys() const {
std::vector<Key> result;
inorder(root, result);
return result;
}
std::vector<Key> keys(const Key& lo, const Key& hi) const {
std::vector<Key> result;
keys(root, result, lo, hi);
return result;
}
};
八、总结
二叉搜索树是一种高效且灵活的数据结构，适用于频繁查找、插入与有序遍历的场景。尽管最坏情况性能不佳，但其简洁的设计和对有序操作的强大支持使其成为基础算法的重要组成部分。通过引入自平衡机制，可进一步提升其稳定性与可靠性。
