C++ 二叉搜索树实现与性能分析
一、概念与性能分析
二叉搜索树（Binary Search Tree, BST），又称二叉排序树。它要么是一棵空树，要么满足以下性质：
- 若左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
- 若右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
- 左右子树本身也是二叉搜索树。
关于相等值的处理，取决于具体场景定义。例如 std::map/std::set 不支持插入相等键，而 multimap/multiset 支持。
性能表现
由于中序遍历必然得到升序序列，BST 非常适合有序数据的存储。其时间复杂度高度依赖于树的形态：
- 最优情况：完全二叉树或接近完全二叉树，高度为
log2(N)，增删查操作均为O(log N)。 - 最差情况：退化为单支树（类似链表），高度为
N，操作退化为O(N)。
为了应对最坏情况，实际工程中常使用平衡二叉搜索树（如 AVL 树、红黑树）。相比二分查找，BST 的优势在于插入和删除效率更高，不需要像数组那样频繁移动数据，且支持动态扩容。
二、核心结构实现
1. 节点定义
为了方便访问成员，我们使用 struct 定义节点，默认公有权限。
template<class K> struct BSTreeNode {
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
BSTreeNode(const K& key) :_left(nullptr), _right(nullptr), _key(key) {}
};
2. 类的基本框架
我们需要管理根节点指针，并处理资源的生命周期（构造、拷贝、析构）。
template<class K> class BSTree {
typedef BSTreeNode<K> Node;
private:
Node* _root = nullptr;
public:
// 默认构造
BSTree() = default;
// 析构函数：递归释放内存
~BSTree() { Destroy(_root); }
// 拷贝构造：深拷贝
( BSTree<K>& t) { _root = (t._root); }
BSTree& =(BSTree t) {
(_root, t._root);
*;
}
:
;
;
};
