C++ 二叉搜索树详解：核心原理与完整实现
一、概念与性能分析
1.1 什么是二叉搜索树
二叉搜索树（Binary Search Tree, BST），又称二叉排序树。它要么是一棵空树，要么满足以下性质：
- 若左子树不为空，则左子树上所有节点的值均小于或等于根节点的值。
- 若右子树不为空，则右子树上所有节点的值均大于或等于根节点的值。
- 左右子树本身也必须是二叉搜索树。
关于相等值的处理，取决于具体场景定义。例如 std::map/std::set 底层不支持插入相等值，而 multimap/multiset 支持。我们在实现时通常默认不支持重复键，但逻辑上可调整。
1.2 性能分析
由于中序遍历二叉搜索树会得到一个升序序列，因此它也被称为二叉排序树。
时间复杂度：
- 最优情况：树接近完全二叉树，高度为 $O(\log_2 N)$。此时增删查效率较高。
- 最差情况：树退化为单支树（类似链表），高度为 $O(N)$。此时效率等同于线性查找。
综合而言，普通二叉搜索树的平均时间复杂度为 $O(\log_2 N)$，最坏为 $O(N)$。当数据量较大且分布不均时，性能可能无法满足需求，这时就需要引入平衡二叉搜索树（如 AVL 树、红黑树）来优化高度。
虽然二分查找也能达到 $O(\log_2 N)$ 的查找效率，但它要求数据存储在支持随机访问的有序结构中，且插入删除需要大量移动数据。相比之下，二叉搜索树在动态增删操作上更具优势。
二、核心功能实现
这里我们实现一个通用的二叉搜索树类，包含基本结构、拷贝构造、赋值重载、析构以及增删查操作。注意：修改 Key 会破坏树的结构，因此本实现仅支持增删查，不支持直接修改 Key。
2.1 基础结构与内存管理
首先定义节点结构，使用 struct 方便默认公有访问。我们需要手动管理资源，因此必须实现深拷贝和析构逻辑。
template<class K>
struct BSTreeNode {
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
BSTreeNode(const K& key)
: _left(nullptr), _right(nullptr), _key(key) {}
};
template<class K>
class BSTree {
typedef BSTreeNode<K> Node;
public:
// 默认构造
BSTree() = default;
// 拷贝构造
BSTree(const BSTree& other) {
_root = (other._root);
}
BSTree& =( BSTree& other) {
( != &other) {
(_root);
_root = (other._root);
}
*;
}
~() {
(_root);
}
:
{
(!root) ;
Node* newNode = (root->_key);
newNode->_left = (root->_left);
newNode->_right = (root->_right);
newNode;
}
{
(!root) ;
(root->_left);
(root->_right);
root;
}
:
Node* _root = ;
};
