一、什么是二叉搜索树
在 C++ 数据结构体系中，搜索二叉树（Binary Search Tree，简称 BST）是连接线性结构与高级树结构的关键桥梁。它既保留了二叉树的层级特性，又通过严格的节点值规则实现高效的查找、插入与删除操作。
定义规则：
- 若左子树不为空，则左子树上所有结点的值都小于等于根结点的值；
- 若右子树不为空，则右子树上所有结点的值都大于等于根结点的值；
- 左右子树也分别为二叉搜索树；
- 关于相等值的处理：具体取决于使用场景，有的实现允许重复，有的不允许。
二、性能分析
BST 的效率高度依赖于树的形态。
-
时间复杂度
- 最优情况：树接近完全二叉树，高度为 logN，操作效率 O(logN)。
- 最差情况：数据有序插入导致退化为单支树，高度为 N，操作效率 O(N)。
- 注意：通常我们讨论的时间复杂度指最坏情况，即 O(N)。这也是为什么后续需要引入 AVL 树或红黑树等平衡树的原因。
-
与二分查找的对比 二分查找虽然也能达到 O(logN)，但依赖数组且需支持随机访问。一旦涉及频繁的插入和删除，数组需要大量挪动数据，效率低下。BST 则在动态集合操作上更具优势。
三、核心实现逻辑
1. 节点定义
namespace key {
template<class K>
struct BSTreeNode {
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key) :_left(nullptr), _right(nullptr), _key(key) {}
};
}
2. 插入操作
从根节点开始比较，比当前值小往左走，大往右走，直到找到空位置插入新节点。如果实现不支持重复值，遇到相等直接返回 false。
namespace key {
template<class K>
class BSTree {
typedef BSTreeNode<K> Node;
public:
bool Insert(const K& key) {
if (_root == nullptr) {
_root = new Node(key);
;
}
Node* parent = ;
Node* cur = _root;
(cur) {
(cur->_key < key) {
parent = cur;
cur = cur->_right;
} (cur->_key > key) {
parent = cur;
cur = cur->_left;
} {
;
}
}
cur = (key);
(parent->_key < key)
parent->_right = cur;
parent->_left = cur;
;
}
:
Node* _root = ;
};
}
