二叉搜索树的原理与C++实现
二叉搜索树的基本特性
二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树结构，它满足以下递归性质：
- 对于任意节点，其左子树中所有节点的值均小于该节点的值。
- 其右子树中所有节点的值均大于该节点的值。
- 左右子树也必须是二叉搜索树。
这种有序性使得二叉搜索树在查找、插入和删除操作上具有天然优势。特别地，对BST进行中序遍历可得到一个升序序列。
核心数据结构设计
使用模板类实现通用性，支持不同类型键值存储：
template<typename T>
struct TreeNode {
T data;
TreeNode* left;
TreeNode* right;
TreeNode(const T& val) : data(val), left(nullptr), right(nullptr) {}
};
template<typename T>
class BinarySearchTree {
private:
TreeNode<T>* root;
// 辅助函数声明
void inorderTraversal(TreeNode<T>* node) const;
TreeNode<T>* insertRecursive(TreeNode<T>*& node, const T& value);
bool searchRecursive(TreeNode<T>* node, const T& target) const;
TreeNode<T>* findMinNode(TreeNode<T>* node);
public:
BinarySearchTree() : root(nullptr) {}
~BinarySearchTree();
void insert(const T& value);
bool search(const T& value) const;
bool remove(const T& value);
void printInOrder() const;
};
关键操作详解
查找操作
基于比较策略逐层下降：
bool BinarySearchTree::search(const T& value) const {
TreeNode<T>* current = root;
while (current != nullptr) {
if (value == current->data)
return true;
else if (value < current->data)
current = current->left;
else
current = current->right;
}
return false;
}
插入逻辑
定位空位并创建新节点：
void BinarySearchTree::insert(const T& value) {
TreeNode<T>** pos = &root;
while (*pos != nullptr) {
if (value == (*pos)->data)
return; // 已存在则不重复插入
else if (value < (*pos)->data)
pos = &((*pos)->left);
else
pos = &((*pos)->right);
}
*pos = new TreeNode<T>(value);
}
删除机制
需处理三种情况：
- 叶子节点：直接释放内存并断开连接。
- 单侧子树：用子树替代当前节点位置。
- 双子树共存：寻找右子树中的最小节点（或左子树最大节点）替换原节点值，再递归删除替代节点。
bool BinarySearchTree::remove(const T& value) {
TreeNode<T>** current = &root;
while (*current != nullptr) {
if (value == (*current)->data)
break;
else if (value < (*current)->data)
current = &((*current)->left);
else
current = &((*current)->right);
}
if (*current == nullptr) return false;
TreeNode<T>* nodeToDelete = *current;
// 情况1: 只有右子树 或 无子树
if ((*current)->left == nullptr) {
*current = (*current)->right;
delete nodeToDelete;
}
// 情况2: 只有左子树
else if ((*current)->right == nullptr) {
*current = (*current)->left;
delete nodeToDelete;
}
// 情况3: 双子树均存在
else {
TreeNode<T>** successor = &((*current)->right);
while ((*successor)->left != nullptr)
successor = &((*successor)->left);
(*current)->data = (*successor)->data;
nodeToDelete = *successor;
*successor = (*successor)->right;
delete nodeToDelete;
}
return true;
}
键值映射扩展应用
将BST扩展为KV模型可用于构建字典或计数器：
template<typename Key, typename Value>
class MapBST {
struct PairNode {
Key key;
Value value;
PairNode* left;
PairNode* right;
PairNode(const Key& k, const Value& v)
: key(k), value(v), left(nullptr), right(nullptr) {}
};
PairNode* root;
public:
void put(const Key& k, const Value& v) {
PairNode** loc = &root;
while (*loc) {
if (k == (*loc)->key) {
(*loc)->value = v; // 更新已有键
return;
} else if (k < (*loc)->key)
loc = &((*loc)->left);
else
loc = &((*loc)->right);
}
*loc = new PairNode(k, v);
}
Value* get(const Key& k) {
PairNode* cur = root;
while (cur) {
if (k == cur->key) return &(cur->value);
else if (k < cur->key) cur = cur->left;
else cur = cur->right;
}
return nullptr;
}
};
实际应用场景示例
词典查询系统：
MapBST<string, string> dictionary;
dictionary.put("algorithm", "算法");
dictionary.put("binary", "二进制");
string query = "algorithm";
auto meaning = dictionary.get(query);
if (meaning) cout << *meaning << endl;
频率统计器：
MapBST<string, int> wordCount;
vector<string> words = {"apple", "banana", "apple", "cherry"};
for (const auto& w : words) {
int* count = wordCount.get(w);
if (count) (*count)++;
else wordCount.put(w, 1);
}
性能分析与局限性
理想情况下，BST各项操作的时间复杂度为 O(log n)，其中 n 为节点数量。然而当数据按顺序插入时，树会退化为链表结构，导致最坏情况下的时间复杂度上升至 O(n)。
为解决此问题，后续发展出平衡二叉树结构如AVL树和红黑树，通过旋转操作维持树的高度平衡，从而保证操作效率稳定。
