C++ 二叉搜索树：从原理到增删查实现
二叉搜索树（Binary Search Tree, BST）是数据结构中非常基础且重要的一种树形结构。它通过简单的规则实现了高效的查找、插入和删除操作，是理解平衡树（如 AVL、红黑树）的基石。
1. 核心概念与性质
一棵二叉搜索树满足以下两个条件：
- 若左子树不空，则左子树上所有节点的值均小于根节点的值。
- 若右子树不空，则右子树上所有节点的值均大于根节点的值。
- 左右子树也分别为二叉搜索树。
简单来说，就是对于任意节点，其左子树的所有值都小于它，右子树的所有值都大于它。这一特性决定了我们不需要遍历整棵树就能快速定位目标。
2. 基本操作逻辑
我们将树封装为一个类 BSTree，内部维护一个指向根节点的指针 _root。
2.1 查找节点
查找的逻辑与二分查找类似。从根节点出发，比较当前节点值与目标值：
- 如果目标值小于当前值，向左走；
- 如果目标值大于当前值，向右走；
- 如果相等，则找到目标。
在平衡状态下，时间复杂度为 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.2 插入节点
插入时需要保持 BST 的性质。流程如下：
- 查找位置：从根节点开始，根据大小关系向下遍历，直到遇到空指针。
- 创建节点：在空指针处新建节点。
注意两点：
- BST 通常不允许重复键值，若已存在则直接返回。
- 需要记录父节点
curPre，以便在遍历结束时将新节点挂接到正确的位置。
bool insert(const K& val) {
// 空树情况
if (_root == nullptr) {
_root = new Node(val);
return ;
}
Node* cur = _root;
Node* curPre = ;
(cur) {
(val == cur->_key)
;
(val < cur->_key) {
curPre = cur;
cur = cur->_left;
} {
curPre = cur;
cur = cur->_right;
}
}
Node* newNode = (val);
(curPre->_left == )
curPre->_left = newNode;
curPre->_right = newNode;
;
}
