从零开始掌握二叉搜索树（C++ 完整实现与深度解析）

二叉搜索树（Binary Search Tree, BST）是最基础、最经典的树形数据结构之一。它不仅是理解更高级树结构（如 AVL 树、红黑树、B 树）的基石，在许多实际场景中也直接发挥作用。本文将从定义出发，手把手带你用 C++ 实现一个完整的二叉搜索树，并深入分析其性能与局限。

一，什么是二叉搜索树？

二叉搜索树 是一种特殊的二叉树，它满足以下性质：

1，若左子树非空，则左子树上所有节点的值 均小于 根节点的值。

2，若右子树非空，则右子树上所有节点的值 均大于 根节点的值。

3，左、右子树本身也各是一棵二叉搜索树。

（通常我们默认树中不存在值相等的节点；若需支持重复键值，可通过计数或规则约定处理，本文以无重复为例。）

得益于这种有序性，BST 能够以 O(h)的时间完成查找、插入、删除操作，其中 h 是树的高度。最优情况下 h=log⁡n，退化为链表时 h=n。

二，节点定义与基本框架

我们用 C++ 模板来实现，以便支持不同数据类型。节点结构包含数据域、左右孩子指针。为便于管理内存，这里使用原始指针，并在析构函数中递归释放整棵树。

template<class T> struct TreeNode { T _key; TreeNode<T>* _left; TreeNode<T>* _right; TreeNode(const T& key) :_key(key) , _left(nullptr) ,_right(nullptr) { } }; template<class T> class BSTree { struct Less { bool operator()(const T& x, const T& y) { return x < y; } }; struct Greater { bool operator()(const T& x, const T& y) { return x > y; } }; typedef TreeNode<T> Node; public: BSTree() :_root(nullptr) { } ~BSTree() { _postorder_traversal(_root); } private: void _postorder_traversal(Node* root) { if (root == nullptr) return; _postorder_traversal(root->_left); _postorder_traversal(root->_right); delete root; } Node* _root;

（一），查找

从根节点开始，若目标值等于当前节点值则找到；若小于则进入左子树；若大于则进入右子树。递归与非递归版本都很简洁。

bool find(const T& key)const { if (_root == nullptr) return false; Node* root = _root; while (root) { if (key < root->_key) { root = root->_left; } else if (key > root->_key) { root = root->_right; } else { return true; } } return false; }

（二），插入

插入的过程与查找类似：寻找合适的位置（即查找失败时所在的空位），然后将新节点挂载上去。下图展示了插入的过程。

bool insert(const T& key) { Node* root = _root; Node* parent = nullptr; while (root) { if (Less()(key, root->_key)) { parent = root; root = root->_left; } else if (Greater()(key, root->_key)) { parent = root; root = root->_right; } else { return false; } } Node* newnode = new Node(key); if (_root == nullptr) { _root = newnode; } else { if (Less()(key, parent->_key)) parent->_left = newnode; else parent->_right = newnode; } return true; }

（三），删除

删除操作需要处理三种情况：

1，叶子节点：直接删除。

2，只有一个孩子：用其孩子替换该节点。

3，有两个孩子：找到 后继节点（左右都不为空，找到左子树的最大节点或者右子树的最小节点），本文是找左子树的最大节点，右子树最小节点同理。然后将要删除的值与该节点的值交换，交换之后，再将其删除。

bool erase(const T& key) { Node* node = _root; Node* parent = nullptr; while (node) { if (key < node->_key) { parent = node; node = node->_left; } else if (key > node->_key) { parent = node; node = node->_right; } else { if (node->_left == nullptr) { if (parent == nullptr) _root = _root->_right; else { if (parent->_left == node) parent->_left = node->_right; else parent->_right = node->_right; } delete node; return true; } else if (node->_right == nullptr) { if (parent == nullptr) _root = _root->_left; else { if (parent->_left == node) parent->_left = node->_left; else parent->_right = node->_left; } delete node; return true; } else { //左右都不为空，找到左子树的最大节点或者右子树的最小节点 Node* maxleft = node->_left; Node* maxleftparent = node; while (maxleft->_right) { maxleftparent = maxleft; maxleft = maxleft->_right; } swap(node->_key, maxleft->_key); if (maxleftparent->_left == maxleft) maxleftparent->_left = maxleft->_left; else maxleftparent->_right = maxleft->_left; delete maxleft; return true; } } } return false; }

三，性能分析与退化问题

理想情况下，BST 高度 h≈log⁡2nh≈log2​n，查找、插入、删除时间复杂度均为 O(log⁡n)O(logn)。但如果插入序列本身有序（如1,2,3,4,5），BST 将退化为一根“向右的链表”，树高变为 nn，时间复杂度恶化为 O(n)O(n)。

这是基础 BST 的最大痛点。解决办法是使用 自平衡二叉搜索树，如：

1，AVL 树：严格平衡（左右子树高度差不超过 1），查找极快，但插入/删除旋转开销稍大。

2，红黑树：近似平衡（最长路径不超过最短路径的两倍），综合性能优异，是c++ std::map和std::set 的底层实现。

3，Treap、Splay 树：利用随机优先级或访问局部性进行平衡。

理解 BST 是进阶这些平衡树的前提。

四，总结

二叉搜索树将“二分查找”的思想扩展到了动态数据结构上，实现简单且功能强大。它让我们看到：仅仅通过维护“左小右大”这一简单的规则，就能高效组织、检索数据。而其退化的缺陷又顺理成章地引出了平衡树等数据结构。