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;
;
}


