最近在项目里要写一个缓存模块，里面既要维护一个单纯的 ID 集合，又要维护一份键值映射关系。用现成的容器当然是省事，但考虑到想在这套逻辑上加一些自定义的统计和淘汰策略，同时还想彻底搞清楚树结构内部的细节，于是我决定手写一棵二叉搜索树。而且用了点小技巧，让这棵树既能当 set 用，也能当 map 用。
如果你也遇到过类似的场景，比如想深入理解二叉搜索树、或者正在应付面试里手写红黑树的前置练习，再或者就是想自己封装一套带统计功能的容器，那这篇文章应该能帮上忙。我会把这棵树的模板设计、插入、查找、删除这些核心操作的思路全部讲清楚，重点是解释每个关键步骤背后的“为什么选这条路”，而不是只丢一段能跑的代码给你。
1. 动工前的核心决策：怎么做到一套代码同时支持 key 和 key-value
动手写之前，我先把需求拆了一下。所谓的“既支持 key 又支持 key-value”，用 C++ 的语言翻译过来就是：同一个类模板，实例化之后既能表现成集合（set 语义），又能表现成映射表（map 语义）。这不是要在里面塞两个不同的树结构，而是要用模板参数把“节点里存什么”这件事抽象出来。
1.1 用模板参数控制存储粒度
最朴素的想法是定义一个节点结构，里面两个字段：一个 key，一个 value。value 允许为空。但这样写有几个明显的问题：一是存储浪费，只用 key 的时候 value 字段空着，每个节点白白多占内存；二是语义混乱，什么时候该写 value、什么时候不该写，全靠调用方自觉，根本没法在编译期约束。
我采用的方案是：NodeValue 这个类型由模板参数 T 决定。树本身只关心 T，T 的内部结构由上层传入。
template<typename Key, typename Value> struct KeyValuePair { Key key; Value value; }; template<typename T> struct TreeNode { T data; TreeNode* left; TreeNode* right; TreeNode* parent; };这样设计之后，当你想用集合时，传入TreeNode<int>，节点里就是一个纯粹的 int；当你想用映射时，传入TreeNode<KeyValuePair<int, std::string>>，节点里就是 key-value。同一个 TreeNode 结构，根节点的 data 类型不同，整棵树的语义就不同了，这就是模板的威力所在。
1.2 比较策略如何应对两种模式
树的核心操作——插入、查找、删除——都必须基于“比较”来决策往左走还是往右走。如果节点里只有一个 key，比较逻辑很简单；如果节点里是 key-value，那比较必须只针对 key 进行，value 不能参与排序。
这里我又做了一个关键的抽象：让树模板额外接收一个比较器参数Compare，并且为不同的存储模式提供不同的比较器实现。
template<typename T, typename Compare> class BinarySearchTree { // ... };集合模式下的比较器直接比较元素本身，映射模式下先取出 key 再比较。这样树的核心代码里只需要调用Compare()(a, b)，至于 a 和 b 到底是不是 pair，树完全不关心。
顺着这个思路，我需要为 T 单独写一个萃取方法，让树在 insert 时知道“你传进来的参数是裸 key 还是一个完整的节点数据”。简单地写两个重载也可以，但如果能统一成一种写法更好。我在下文的第四部分会给出具体的模板代码，那里面用了一个函数extractKey来做这件事。
2. 把关键代码落地：节点结构、插入与查找的完整实现
下面这部分我直接给出核心实现，边写边解释每个细节。为了保持代码可读性，先给出树类的整体骨架，再逐个展开函数。
2.1 树的整体框架与类型萃取
template<typename T, typename Compare = std::less<T>> class BinarySearchTree { public: using Node = TreeNode<T>; using NodePtr = Node*; private: NodePtr root_ = nullptr; Compare comp_; // 从完整节点数据中提取用于比较的 key template<typename K> static const K& extractKey(const K& key) { return key; } template<typename K, typename V> static const K& extractKey(const KeyValuePair<K, 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。所以查找函数应该设计成独立的模板：
template<typename 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::vector<T>& 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::less<KeyValuePair>根本不知道该怎么比较一对键值。这就是支持 key-value 模式时最容易踩的坑。
4.1 比较器如何横向扩展
解决这个问题有两条路。第一条是给KeyValuePair重载<运算符，让比较操作自动提取 key 再比较。第二条是给树的模板参数传一个自定义比较器，比较器内部只关注 key。
我推荐第二条。原因是：重载运算符会把“如何比较”写死在类型里，如果将来同一个KeyValuePair类型在不同场景下需要不同的比较规则，你会发现完全绕不开。而传入独立比较器，把决策留在调用方，灵活性高得多。
struct KeyValuePairLess { template<typename K, typename V> bool operator()(const KeyValuePair<K, V>& lhs, const KeyValuePair<K, V>& rhs) const { return lhs.key < rhs.key; } }; using KvTree = BinarySearchTree<KeyValuePair<int, 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::vector<int> 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::less<T>去比较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 指针的维护变成理所应当的步骤，整棵树就算立住了。后面再往上加平衡逻辑、迭代器、内存池，都会顺很多。如果你也在写类似的自定义容器，建议先拿着这套代码跑通功能，再考虑性能优化和平衡改造——先把逻辑跑对跑稳，永远是最重要的一步。
