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

二叉搜索树Binary Search Tree, BST是最基础、最经典的树形数据结构之一。它不仅是理解更高级树结构如 AVL 树、红黑树、B 树的基石在许多实际场景中也直接发挥作用。本文将从定义出发手把手带你用 C 实现一个完整的二叉搜索树并深入分析其性能与局限。一什么是二叉搜索树二叉搜索树 是一种特殊的二叉树它满足以下性质1若左子树非空则左子树上所有节点的值 均小于 根节点的值。2若右子树非空则右子树上所有节点的值 均大于 根节点的值。3左、右子树本身也各是一棵二叉搜索树。通常我们默认树中不存在值相等的节点若需支持重复键值可通过计数或规则约定处理本文以无重复为例。得益于这种有序性BST 能够以 O(h)的时间完成查找、插入、删除操作其中 h 是树的高度。最优情况下 hlog⁡n退化为链表时 hn。二节点定义与基本框架我们用 C 模板来实现以便支持不同数据类型。节点结构包含数据域、左右孩子指针。为便于管理内存这里使用原始指针并在析构函数中递归释放整棵树。templateclass T struct TreeNode { T _key; TreeNodeT* _left; TreeNodeT* _right; TreeNode(const T key) :_key(key) , _left(nullptr) ,_right(nullptr) { } }; templateclass 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 TreeNodeT 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,5BST 将退化为一根“向右的链表”树高变为 nn时间复杂度恶化为 O(n)O(n)。这是基础 BST 的最大痛点。解决办法是使用 自平衡二叉搜索树如1AVL 树严格平衡左右子树高度差不超过 1查找极快但插入/删除旋转开销稍大。2红黑树近似平衡最长路径不超过最短路径的两倍综合性能优异是c std::map和std::set 的底层实现。3Treap、Splay 树利用随机优先级或访问局部性进行平衡。理解 BST 是进阶这些平衡树的前提。四总结二叉搜索树将“二分查找”的思想扩展到了动态数据结构上实现简单且功能强大。它让我们看到仅仅通过维护“左小右大”这一简单的规则就能高效组织、检索数据。而其退化的缺陷又顺理成章地引出了平衡树等数据结构。