C++ 二叉搜索树基础实现：增删查改详解
什么是二叉搜索树？
二叉搜索树（Binary Search Tree, BST）又称二叉排序树。它或者是一棵空树，或者满足以下性质：
- 左子树上所有节点的值都小于等于根结点的值；
- 右子树上所有节点的值都大于等于根结点的值；
- 它的左右子树也分别为二叉搜索树。
注意：BST 是否支持插入相等值取决于具体场景定义。例如
std::set不支持重复键，而std::multiset支持。后续实现中我们默认处理不重复值的情形。
性能分析
在最优情况下，BST 为完全二叉树，高度约为 log2 N，平均时间复杂度为 O(log n)。但在最差情况下（退化为单支树），高度为 N，时间复杂度降为 O(n)。
虽然二分查找也能达到 O(log2 N) 的查找效率，但它有两个明显缺陷：
- 需要存储在支持下标随机访问的结构中，且必须有序。
- 插入和删除数据效率低，因为涉及大量数据移动。
相比之下，BST 在动态维护有序数据方面更具优势。
Key 类型二叉搜索树的实现
节点与类结构
我们先定义节点结构，存储键值和指向左右孩子的指针。
template<class K>
struct BSTNode {
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key = 0)
:_key(key), _left(nullptr), _right(nullptr) {}
};
类结构则包含根节点指针：
template<class K>
class BSTree {
using Node = BSTNode<K>;
public:
// ... 成员函数
private:
Node* _root = nullptr;
};
插入操作
插入的核心在于找到合适的位置。如果树为空，直接设为根；否则从根开始遍历，比当前节点小往左走，大往右走，直到遇到空位插入新节点。
bool Insert(const K& key) {
(_root == ) {
_root = (key);
;
}
Node* parent = ;
Node* cur = _root;
(cur) {
(key < cur->_key) {
parent = cur;
cur = cur->_left;
} (key > cur->_key) {
parent = cur;
cur = cur->_right;
} {
;
}
}
(key < parent->_key) {
parent->_left = (key);
} {
parent->_right = (key);
}
;
}
