C++ 二叉搜索树：原理与增删查实现详解
二叉搜索树（Binary Search Tree, BST）是数据结构中非常基础且重要的一种树形结构。它不仅仅是面试中的常客，更是理解红黑树、AVL 树等平衡树的基础。今天我们就从原理出发，结合 C++ 代码，把它的增删查操作彻底搞懂。
理解二叉搜索树
一棵二叉搜索树必须满足以下两个核心性质：
- 左小右大：若根节点存在，其左子树中所有节点的值都小于根节点的值，右子树中所有节点的值都大于根节点的值。
- 递归定义：任意节点的左右子树也必须是二叉搜索树。
这意味着，对于树中的任意节点，其左侧的所有后代都比它小，右侧的所有后代都比它大。这种有序性使得查找效率远高于普通链表或无序树。
需要注意的是，如果插入的数据本身是有序的（例如 1, 2, 3, 4...），BST 会退化成一条链表，此时性能会急剧下降至 O(n)。这也是后续学习平衡树的原因，但在掌握 BST 本身之前，我们先专注于其基本逻辑。
核心操作解析
我们将树封装为一个模板类 BSTree，内部维护一个指向根节点的指针 _root。
1. 查找操作
查找的逻辑其实和二分查找非常像。给定目标值 val，我们从根节点开始比较：
- 如果
val < cur->_key，说明目标在左边，往左走； - 如果
val > cur->_key，说明目标在右边，往右走； - 如果相等，直接返回当前节点。
当遍历到空指针时，说明树中不存在该值。平均情况下，时间复杂度为 O(log n)，最坏情况（退化链表）为 O(n)。
Node* find(const K& val) {
Node* cur = _root;
while (cur) {
if (val < cur->_key)
cur = cur->_left;
else if (val > cur->_key)
cur = cur->_right;
else
break; // 找到目标
}
return cur;
}
2. 插入操作
插入的核心在于保持'左小右大'的性质。流程如下：
- 处理空树：如果树是空的，新节点直接成为根节点。
- 寻找位置：从根节点出发，根据大小关系向下遍历，直到遇到空指针。
- 插入节点：在空指针处挂上新节点。
这里有个细节要注意：BST 通常不允许重复键值。如果在查找过程中发现已存在该值，应直接返回失败，不执行插入。
bool insert(const K& val) {
// 空树情况
if (_root == ) {
_root = (val);
;
}
Node* cur = _root;
Node* curPre = ;
(cur) {
(val == cur->_key)
;
(val < cur->_key) {
curPre = cur;
cur = cur->_left;
} {
curPre = cur;
cur = cur->_right;
}
}
(curPre->_key > val)
curPre->_left = (val);
curPre->_right = (val);
;
}
