最近在项目里要写一个缓存模块里面既要维护一个单纯的 ID 集合又要维护一份键值映射关系。用现成的容器当然是省事但考虑到想在这套逻辑上加一些自定义的统计和淘汰策略同时还想彻底搞清楚树结构内部的细节于是我决定手写一棵二叉搜索树。而且用了点小技巧让这棵树既能当 set 用也能当 map 用。如果你也遇到过类似的场景比如想深入理解二叉搜索树、或者正在应付面试里手写红黑树的前置练习再或者就是想自己封装一套带统计功能的容器那这篇文章应该能帮上忙。我会把这棵树的模板设计、插入、查找、删除这些核心操作的思路全部讲清楚重点是解释每个关键步骤背后的“为什么选这条路”而不是只丢一段能跑的代码给你。1. 动工前的核心决策怎么做到一套代码同时支持 key 和 key-value动手写之前我先把需求拆了一下。所谓的“既支持 key 又支持 key-value”用 C 的语言翻译过来就是同一个类模板实例化之后既能表现成集合set 语义又能表现成映射表map 语义。这不是要在里面塞两个不同的树结构而是要用模板参数把“节点里存什么”这件事抽象出来。1.1 用模板参数控制存储粒度最朴素的想法是定义一个节点结构里面两个字段一个 key一个 value。value 允许为空。但这样写有几个明显的问题一是存储浪费只用 key 的时候 value 字段空着每个节点白白多占内存二是语义混乱什么时候该写 value、什么时候不该写全靠调用方自觉根本没法在编译期约束。我采用的方案是NodeValue 这个类型由模板参数 T 决定。树本身只关心 TT 的内部结构由上层传入。templatetypename Key, typename Value struct KeyValuePair { Key key; Value value; }; templatetypename T struct TreeNode { T data; TreeNode* left; TreeNode* right; TreeNode* parent; };这样设计之后当你想用集合时传入TreeNodeint节点里就是一个纯粹的 int当你想用映射时传入TreeNodeKeyValuePairint, std::string节点里就是 key-value。同一个 TreeNode 结构根节点的 data 类型不同整棵树的语义就不同了这就是模板的威力所在。1.2 比较策略如何应对两种模式树的核心操作——插入、查找、删除——都必须基于“比较”来决策往左走还是往右走。如果节点里只有一个 key比较逻辑很简单如果节点里是 key-value那比较必须只针对 key 进行value 不能参与排序。这里我又做了一个关键的抽象让树模板额外接收一个比较器参数Compare并且为不同的存储模式提供不同的比较器实现。templatetypename T, typename Compare class BinarySearchTree { // ... };集合模式下的比较器直接比较元素本身映射模式下先取出 key 再比较。这样树的核心代码里只需要调用Compare()(a, b)至于 a 和 b 到底是不是 pair树完全不关心。顺着这个思路我需要为 T 单独写一个萃取方法让树在 insert 时知道“你传进来的参数是裸 key 还是一个完整的节点数据”。简单地写两个重载也可以但如果能统一成一种写法更好。我在下文的第四部分会给出具体的模板代码那里面用了一个函数extractKey来做这件事。2. 把关键代码落地节点结构、插入与查找的完整实现下面这部分我直接给出核心实现边写边解释每个细节。为了保持代码可读性先给出树类的整体骨架再逐个展开函数。2.1 树的整体框架与类型萃取templatetypename T, typename Compare std::lessT class BinarySearchTree { public: using Node TreeNodeT; using NodePtr Node*; private: NodePtr root_ nullptr; Compare comp_; // 从完整节点数据中提取用于比较的 key templatetypename K static const K extractKey(const K key) { return key; } templatetypename K, typename V static const K extractKey(const KeyValuePairK, V kv) { return kv.key; } public: BinarySearchTree() default; ~BinarySearchTree() { clear(); } // ... 后续函数 };extractKey的重载是整个设计里最核心的“暗线”。树在插入时先调用extractKey(data)提取出参与比较的字段再用Compare做大小判断。无论你往里面塞的是裸 key 还是KeyValuePair树内部的比较逻辑都不用改。这里补充一个我个人用得比较顺手的做法extractKey用 static 模板函数实现它没有访问任何实例成员所以放在类里也好、放成自由函数也好效果都一样。后续如果你想把这棵树扩展成红黑树这个萃取函数可以直接复用。2.2 插入操作的两个版本与原地调整插入和普通教材里的写法有一点不一样我保留了重复键的处理策略。很多人写 BST 直接不允许重复节点插入时发现相等就返回。但在实际项目里key-value 场景经常要做“覆盖写”也就是 key 相同就替换 value而不是忽略。因此我提供了两个入口insert和insertOrAssign。bool insert(const T data) { return insertImpl(data, false); } bool insertOrAssign(const T data) { return insertImpl(data, true); }insertImpl内部做的事情是从根节点出发用extractKey提取待插入数据的 key和当前节点的 key 做比较。小于则向左大于则向右等到了空位就挂上新节点。相等的时候根据第二个参数决定是直接返回 false还是把当前节点的 data 替换成新的。bool insertImpl(const T data, bool assignIfExists) { if (!root_) { root_ new Node{data, nullptr, nullptr, nullptr}; return true; } NodePtr cur root_; while (cur) { const auto newKey extractKey(data); const auto curKey extractKey(cur-data); if (comp_(newKey, curKey)) { if (!cur-left) { cur-left new Node{data, nullptr, nullptr, cur}; return true; } cur cur-left; } else if (comp_(curKey, newKey)) { if (!cur-right) { cur-right new Node{data, nullptr, nullptr, cur}; return true; } cur cur-right; } else { if (assignIfExists) { cur-data data; } return false; } } return false; }这里有个容易漏掉的点新节点的 parent 指针必须在创建时就赋值否则后续实现删除时会找不到父节点链路。很多教学代码里 BST 节点只有 left 和 right删节点时用递归返回值来维护父子关系确实能写但非递归删除需要 parent。我的建议是节点里直接带上 parent 指针一开始写的时候就省心后面想改成 AVL 树或者红黑树也是现成的链路。2.3 查找与中序遍历的细节查找的逻辑和插入前半段一模一样从根开始比 key 小往左大往右相等返回节点。这里要注意“按 key 查找”和“按 data 查找”的区别。集合模式下data 本身就是 key映射模式下用户拿到的通常是一个裸 key而不是一个完整的KeyValuePair。所以查找函数应该设计成独立的模板templatetypename K NodePtr find(const K key) const { NodePtr cur root_; while (cur) { const auto curKey extractKey(cur-data); if (comp_(key, curKey)) { cur cur-left; } else if (comp_(curKey, key)) { cur cur-right; } else { return cur; } } return nullptr; }这样写的好处是调用方可以写tree.find(42)而不必为了查找一个映射模式下的 key 去拼一个KeyValuePair。C 的模板在这里充分发挥了威力K 类型和节点里的 key 类型不必一致只要Compare能同时处理两者就行。中序遍历在 BST 里就是有序序列这个功能我用递归实现简洁清晰void inorderTraverse(NodePtr node, std::vectorT result) const { if (!node) return; inorderTraverse(node-left, result); result.push_back(node-data); inorderTraverse(node-right, result); }很多面试题会从这里引申出“BST 转有序链表”、“第 K 小元素”等变体底子都是对中序遍历的理解。实测下来先写出这个模板化版本再针对不同问题做改造效率会高很多因为你不需要反复重写树的构建与维护代码。3. 最头疼的部分删除节点的三种子情形与父指针维护删除节点是二叉搜索树的核心难点没有之一。很多教材只讲了三种情况叶子节点直接删只有一个孩子的节点让孩子顶替有两个孩子的节点找后继替换。但实际动手写起来细节远不止三句话。3.1 先找到再操作删除的完整流程完整删除流程可以拆成四步用 key 找到目标节点。处理目标节点的孩子数量。把目标节点从树中摘除维护 parent 和 left/right 的指向。释放目标节点内存。这里的“摘除”操作需要特别小心。具体而言目标节点可能是根节点也可能不是它的 parent 可能是空、是左子树、是右子树。为了统一处理我写了一个辅助函数transplant它的语义是用节点 v 替换节点 u只处理 u 的父亲与 v 的父子关系不改动 v 的左右孩子。其实这就是红黑树里常见替换操作的雏形。void transplant(NodePtr u, NodePtr v) { if (!u-parent) { root_ v; } else if (u u-parent-left) { u-parent-left v; } else { u-parent-right v; } if (v) { v-parent u-parent; } }有了这个函数删除逻辑会清晰很多。3.2 三种子情形的具体代码第一种情况目标节点没有左孩子。那么直接用它的右孩子替换它右孩子为空也无所谓替换之后右孩子这一侧自然就是空。第二种情况目标节点没有右孩子。那么直接用它的左孩子替换它。第三种情况目标节点左右孩子都在。这时候要找到它的中序后继也就是右子树中最小的节点。后继一定没有左孩子所以可以把后继摘出来顶到目标节点的位置。bool erase(const K key) { NodePtr target find(key); if (!target) return false; if (!target-left) { transplant(target, target-right); delete target; } else if (!target-right) { transplant(target, target-left); delete target; } else { NodePtr successor target-right; while (successor-left) { successor successor-left; } if (successor-parent ! target) { transplant(successor, successor-right); successor-right target-right; successor-right-parent successor; } transplant(target, successor); successor-left target-left; successor-left-parent successor; delete target; } return true; }这段代码最绕的部分在于第三种情况的两个分支。如果后继恰好就是 target 的右孩子那就不需要先把后继摘出来直接让后继顶上来再把 target 的左孩子挂到后继的左孩子位。如果后继在 target 右子树的更深处就要先处理后继的右孩子与后继父亲的连接再调整目标节点的右孩子指针。这个“先摘后继、再接右子树、再顶替目标”的顺序错一步指针就全乱。当初我第一版就把这个顺序写反了结果删除后树结构直接断裂调试了很久。3.3 删除操作里不得不说的两个坑第一个坑是 parent 指针的更新。transplant里只更新了接替节点的 parent但替换完成后如果接替节点还带着原来的子树这些子树里的节点不会受影响因为它们本来就是接替节点的子树。可问题常出在 target 原右子树里当你把 target 的右孩子挂到后继的右孩子位之后必须同步更新新右孩子的 parent。上文代码里写的是successor-right-parent successor这一步很容易被漏掉。第二个坑是删除节点之后的“内存与状态一致性”。我在erase末尾直接用delete target但某些场景下节点可能由内存池统一管理或者节点带有额外的统计信息需要初始化。所以更稳妥的做法是把delete target这一步单独拆成destroyNode函数后续想接内存池或者对象池只改这个函数就行。这种“留缝”的设计一开始看着多写了几行但扩展起来很舒服。4. 支持 key-value 模式时的隐藏复杂度比较器、提取和存取策略到这里树的基础功能已经齐了。但如果仅仅做到这一步你会发现直接把KeyValuePair传给BinarySearchTree会报错因为std::lessKeyValuePair根本不知道该怎么比较一对键值。这就是支持 key-value 模式时最容易踩的坑。4.1 比较器如何横向扩展解决这个问题有两条路。第一条是给KeyValuePair重载运算符让比较操作自动提取 key 再比较。第二条是给树的模板参数传一个自定义比较器比较器内部只关注 key。我推荐第二条。原因是重载运算符会把“如何比较”写死在类型里如果将来同一个KeyValuePair类型在不同场景下需要不同的比较规则你会发现完全绕不开。而传入独立比较器把决策留在调用方灵活性高得多。struct KeyValuePairLess { templatetypename K, typename V bool operator()(const KeyValuePairK, V lhs, const KeyValuePairK, V rhs) const { return lhs.key rhs.key; } }; using KvTree BinarySearchTreeKeyValuePairint, std::string, KeyValuePairLess;这有点像是把比较函数提升成了类型的一部分C 里这种模式其实很常见比如std::map的第三个模板参数就是干这个的。4.2 提取 key 的统一接口设计前文代码里之所以能用一套insert同时处理int和KeyValuePair靠的就是extractKey重载。这个设计有个额外好处当你想查找一个 key 时查找函数接受裸 key 类型内部用同一个Compare去比较裸 key 与节点内提取出的 key编译期会自动匹配合理的重载。不过这里有个小问题需要提一下extractKey返回的是 const 引用所以临时构造的KeyValuePair不会造成拷贝。查找接口也按 const 引用接收外部 key整个链路零拷贝性能上有保障。如果你在实现时随手把参数改成按值传参那么每次查找都会多一次拷贝在大量查找场景下性能影响很明显。4.3 存取策略insertOrAssign 的实际应用场景key-value 模式的树最常见的需求其实是“更新或插入”。比如维护一个配置缓存用户多次写入相同 key后一次的值应该覆盖前一次。这就是insertOrAssign存在的意义。在实现insertOrAssign时有个取值细节值得注意当目标 key 已经在树里并且我们允许覆盖时直接做cur-data data就够了。但如果你希望保留旧的 value 里某些字段那就要改成字段级联拷贝或者调用自定义的 merge 函数。我的经验是这种“部分更新”的需求一定要在一开始就在接口层设计好否则等树写完再塞新逻辑就只能在调用方做“先查找再修改”绕一圈不说还容易破坏树结构的封装性。5. 功能测试与排查技巧让代码真正跑起来代码写完了不代表能用。我这里整理了自测 BST 时非常管用的几组用例以及实际调试中容易迷惑的排查点。5.1 测试用例设计的基本思路BST 最容易出错的是删除环节。所以我的测试策略是构造一棵形状比较刁钻的树然后反复插入、删除、中序输出对比。具体可以这么构造初始树std::vectorint keys {5, 3, 8, 1, 4, 7, 9, 6}; for (int k : keys) { tree.insert(k); }用中序遍历输出结果必须是1 3 4 5 6 7 8 9。然后依次删除根节点 5、删掉叶子 1、删掉只有单孩子的节点 7每删除一次都重新中序遍历并检查序列是否有序且元素正确。如果再激进一点可以加入随机插入、随机删除、随机查找的模糊测试跑几十万次操作最后再中序验证排序性。别觉得麻烦这种测试能在一分钟之内把你代码里的指针迷路问题暴露出来比自己盯着代码看强多了。5.2 常见编译与运行错误排查我在实际编写这个模板的过程中遇到过三类比较典型的问题。第一类是模板实例化报错当你用std::lessT去比较KeyValuePair编译期直接报一堆难以阅读的模板错误。这类问题没别的办法严格按照“比较器必须定义”的思路去设计在一开始就给 pair 类型配好独立的比较器能避免九成以上的编译麻烦。如果编译器报错太混乱一个小技巧是把错误里涉及operator的提示单独拎出来看它往往会指出具体是哪个类型没有可比性。第二类是删除后树结构正确但查找却找不到目标。这种情况九成是 parent 指针没更新对或者是transplant里对根节点的判断写错了。排查方法是在删除操作前后打印节点的 parent 关系链尤其是目标节点及其子树的 parent 指向。第三类是递归深度过大导致栈溢出这通常出现在树退化成链表的场景。我处理的办法是在插入时先做一个“数据分布检查”如果发现插入的 key 几乎单调就在外部打乱顺序再插入或者直接把树升级成平衡树。这个点也引出了下一步的扩展思路。5.3 从 BST 到平衡树的一点扩展想法如果未来要做 AVL 或者红黑树当前这套代码里已经隐含了两处很好的改造基础一是节点里已经存了 parent 指针旋转操作可以直接朝上调整不需要递归返回新根二是extractKey和Compare已经分离树的旋转规则和平衡因子的维护不需要关心 key 具体是裸值还是 pair。真要做到这一步还需要在TreeNode里加一个height或者color字段然后把插入和删除之后的“回溯调整”逻辑补上。这个过程不需要推翻现有设计只是在关键操作后加平衡处理。这其实就是我一开始写这棵树的另一个私心不做一次性玩具而是希望它能作为后续平衡树学习的基础骨架。6. 关于封装与接口设计的一点建议最后简单说说接口层面的体会。我见过很多人写 BST 时把内部节点直接暴露给外部find 返回值直接就是裸指针。临时写测试倒没什么但如果这棵树真的要进入业务代码我建议把指针封装起来对外提供迭代器或者智能句柄内部方法不要直接返回可被随意 delete 的裸指针。这里我用的是“节点指针 私有权限”的方式对外只暴露bool erase(const K)、bool contains(const K)、bool insert(const T)这些语义清晰的接口节点指针全部私有。如果确实需要从树里取出一个节点做修改提供一个安全包装的modifyValue方法在外部传入修改回调内部通过临时指针完成操作后自动回收。好处是调用方想“把 key 改了”这件事从根本上被杜绝了——树的有序性依赖 key 不变一旦允许外部直接改 key整个树就是一堆乱序节点。另外有一个小技巧实现一棵树的赋值和移动语义非常容易踩空。默认拷贝构造会做浅拷贝导致两个树实例共享同一批节点指针析构时双重释放。因此我在这个类里显式删除了拷贝构造与赋值运算符并提供clone做深拷贝。如果项目确实需要频繁复制树建议在clone的基础上再补移动语义这样可以减少不必要的拷贝开销。我个人在实际写这棵树时最大的体会是二叉搜索树的难点从来不在“插入”和“查找”本身而在删除和资源管理。一旦把删除的三种子情形拆清楚、把 parent 指针的维护变成理所应当的步骤整棵树就算立住了。后面再往上加平衡逻辑、迭代器、内存池都会顺很多。如果你也在写类似的自定义容器建议先拿着这套代码跑通功能再考虑性能优化和平衡改造——先把逻辑跑对跑稳永远是最重要的一步。