集合Set和树形结构Tree看起来是两个方向放在一起却是数据结构里最经典的一对组合之一。我最早对这对组合产生深刻印象是在处理一个需要“去重、有序、还能按区间取数据”的需求时要维护一批带优先级的任务编号任务不能重复又要随时取出某个范围内的所有编号还要快速拿到最小的那个。当时我本能地先上了哈希结构结果发现哈希只回答“在不在”一个问题拿到数组之后还得排序才能做范围查找性能根本扛不住业务增长。后来我把目光转向树形结构用平衡二叉树重新实现了这个集合问题才算真正解决。这篇文章我会从“集合为什么需要树”讲起拆解哈希集合的边界、二叉搜索树的退化风险、自平衡树的旋转本质再给出一套可运行的有序集合核心实现最后延伸到 B 树、并查集、字典树这些实际工程里的树形集合应用。无论你是准备面试、做存储选型还是单纯想搞懂标准库里的有序集合为什么长那样这篇内容应该都能给你一个比较完整的答案。1. 为什么集合需要树形结构哈希表的边界1.1 哈希集合的强项与短板哈希集合的基础是哈希表核心操作是把元素通过哈希函数映射到一个数组桶里。它的优势非常明显插入、删除、查找的平均时间复杂度都是 O(1)代码写起来也直观大多数场景下直接无脑用哈希集合就完事了。但哈希集合有一个本质上的短板它只维护“存在性”不维护“顺序性”。你可以快速知道一个元素在不在集合里却无法回答以下问题集合里最小的元素是谁比某个给定值大的第一个元素是谁从 5 到 100 之间一共有多少个元素用哈希结构硬做也不是不行你可以把集合全部导出来排序再遍历。但这样一次操作就是 O(N log N) 甚至 O(N)如果你的集合有几十万条数据、业务又要频繁做区间查询这个成本会直接拖垮接口响应。再叠加一个容易被忽视的问题哈希表扩容时会重新分配桶并迁移数据迭代顺序会发生变化。如果你依赖遍历顺序做分页、做对比哈希结构会带来额外的不确定性。1.2 树形集合补齐的三个核心能力二叉搜索树BST和它的自平衡变体解决的就是哈希集合“感知顺序”的问题。树形集合天然具备三个能力这是哈希结构很难弥补的。第一个能力是有序遍历。对一棵二叉搜索树做中序遍历得到的结果天然是升序或降序的。这意味着你在任何时候都能以 O(N) 的代价遍历整个集合而且结果是有序的。第二个能力是区间查询。给定 [lo, hi] 范围树形集合可以在 O(log N K) 的时间内找出所有落在范围内的元素其中 K 是符合条件的元素个数。这个能力在做排行榜、订单筛选、库存盘点时非常实用。第三个能力是前驱与后继查询。也就是“比当前值小的最大值”和“比当前值大的最小值”。这个能力在实现最近邻匹配、LRU 淘汰策略按时间戳找最老数据、IP 地址段匹配时非常关键。用一个生活化的类比来说哈希集合像一张纸条上的名单列表你只能看名字在不在树形集合像一本按拼音排序的通讯录你不仅能查某个人在不在还能随手翻到“张三后面是谁”。1.3 选型对照表实际工程里选型不能只谈理论下面这张对照表是我自己常用的参考对比维度哈希集合无序二叉搜索树自平衡树AVL/红黑树B 树单点查找O(1)最坏 O(N)O(log N)O(log N)插入/删除O(1) 平均最坏 O(N)O(log N)O(log N)有序遍历不支持支持需中序支持支持区间查询不支持最坏 O(N)O(log N K)O(log N K)磁盘友好否否否是实现复杂度低低高非常高从这张表能看出来树形结构解决的是“需要顺序”的场景哈希解决的是“只需要快速存在性判断”的场景。两者不是替代关系而是互补关系。数据库里的索引选 B 树内存里的有序集合选红黑树缓存前置判断还是哈希最快各有各的生态位。2. 从二叉搜索树到自平衡树2.1 二叉搜索树的构建规则与退化风险二叉搜索树的核心规则很简单左子树的节点值都小于根节点右子树的节点值都大于根节点。这个规则保证了任意节点在查找时每走一步就可以淘汰掉一半的搜索空间理想情况下查找复杂度是 O(log N)。但“理想情况”有一个非常苛刻的前提树要长得均匀。如果你按顺序插入一组数据比如依次插入 1、2、3、4、5效果是这样的1 作为根2 成为右子节点3 成为 2 的右子节点……每一步都只往右走整棵树退化成了链表。此时查找 5 需要从根一路遍历到底复杂度变成 O(N)。为什么业务里这种情况特别常见因为业务数据往往天然有序自增 ID、时间戳、水位线、任务编号。这些数据就是按递增顺序产生的如果直接插入普通 BST不退化才怪。这就是“有序输入”给无序 BST 带来的致命伤。2.2 旋转操作的核心思想解决退化问题的方案是让树在插入、删除之后自我调整保持“近似均匀”的形态。这个调整的核心动作叫旋转。旋转有一句非常关键的总结旋转不改变树的中序遍历序列只改变树的整体形状。右旋操作的具体过程选中节点 y它的左子节点是 x。把 x 提升为子树根y 变成 x 的右子节点x 原来的右子树 t2 挂到 y 的左边。 左旋操作完全对称选中节点 x它的右子节点是 y。把 y 提升为子树根x 变成 y 的左子节点y 原来的左子树挂到 x 的右边。这个操作可以用一个生活类比来理解想象三个大小不同的箱子叠在一起左边太重要倒你把中间的箱子抽出来放到最上面重新分配一下承重结构。节点的相对大小顺序没有变但整个结构恢复了稳定。旋转的核心在于理解它是“局部的”一次旋转只影响三个节点和两棵子树不会牵扯到整棵树。这个局部性让平衡操作的时间复杂度维持在 O(1) 级别配合递归回溯整棵树的调整也就是 O(log N)。2.3 AVL 树的平衡因子与调整路径AVL 树把“均匀”定义得非常严格任意节点的左右子树高度差绝对值不超过 1。这个高度差叫平衡因子计算公式是“左子树高度减去右子树高度”。插入节点后从插入点往上回溯沿途更新高度如果发现某个节点平衡因子绝对值超过 1就需要旋转。根据失衡方向处理路径可以分为四种失衡类型特征调整方式LL左子树的左子树过深对失衡节点做一次右旋RR右子树的右子树过深对失衡节点做一次左旋LR左子树的右子树过深先对左子节点左旋再对失衡节点右旋RL右子树的左子树过深先对右子节点右旋再对失衡节点左旋为什么 LR 和 RL 需要两步旋转因为如果直接在失衡节点上做一次旋转会发现无法恢复平衡。这类似于你推一扇卡住的门直接推不行要先往反方向拉一下把门的位置纠正再推开。内侧失衡必须先通过一次旋转转成外侧失衡再做真正的平衡旋转。2.4 为什么工程上更常见红黑树AVL 树是理论上的“处女座方案”高度控制最严格查询效率最稳定。但在工程里我见过更多的地方选择红黑树而不是 AVL 树原因值得说一下。红黑树不要求左右子树高度绝对相等它要求的是一条从根到叶子节点的路径上黑色节点数量相同同时不允许两个红色节点相邻。加上根黑、叶黑、红节点子节点必黑这几条约束它保证了最长路径不超过最短路径的两倍。这个“放宽”很聪明红黑树的最坏查询复杂度还是 O(log N)但插入和删除时需要的旋转次数比 AVL 树少得多比如插入最多两次旋转删除最多三次旋转。对于插入删除频繁的业务场景这个差异是很实际的。AVL 树的查询略快一点但每次插入都可能需要回溯多做旋转红黑树的查询稍慢一点点但整体结构调整代价更可控。再加上红黑树的删除操作实现虽然复杂但工程化成熟度高所以大量语言标准库里的有序集合底层选择红黑树是合理的。3. 实操手写一个极简有序集合3.1 接口设计与数据结构定义理论聊完进入动手环节。我基于 AVL 思路实现一个极简的 OrderedSet只保留核心能力add、contains、中序遍历和范围查询。这里先做一点设计取舍为了保证代码逻辑清晰可读我选择实现 AVL 的插入与平衡删除操作暂不展开工程里可以用懒删除策略绕过后面细说。节点结构需要记录值、左右子节点和子树高度。class Node: __slots__ (val, left, right, height) def __init__(self, val): self.val val self.left None self.right None self.height 1OrderedSet 只需要维护根节点引用。所有递归操作都从根节点出发。3.2 插入流程与中序遍历AVL 插入的核心是递归插入后回溯在回溯路径上依次更新高度并检查平衡因子。一旦发现失衡按四种情况旋转class OrderedSet: def __init__(self): self.root None def _height(self, node): return node.height if node else 0 def _update_height(self, node): node.height 1 max(self._height(node.left), self._height(node.right)) def _balance_factor(self, node): return self._height(node.left) - self._height(node.right) def _rotate_right(self, y): x y.left t2 x.right x.right y y.left t2 self._update_height(y) self._update_height(x) return x def _rotate_left(self, x): y x.right t2 y.left y.left x x.right t2 self._update_height(x) self._update_height(y) return y def _balance(self, node): self._update_height(node) bf self._balance_factor(node) if bf 1: if self._balance_factor(node.left) 0: node.left self._rotate_left(node.left) return self._rotate_right(node) if bf -1: if self._balance_factor(node.right) 0: node.right self._rotate_right(node.right) return self._rotate_left(node) return node def add(self, val): if not self.contains(val): self.root self._insert(self.root, val) return self def _insert(self, node, val): if not node: return Node(val) if val node.val: node.left self._insert(node.left, val) else: node.right self._insert(node.right, val) return self._balance(node) def contains(self, val): node self.root while node: if val node.val: return True node node.left if val node.val else node.right return False这段代码里有几个容易被忽略的细节_balance在更新高度之后才判断失衡顺序不能反否则平衡因子算的是旧高度。旋转函数里必须更新两个被调整节点的高度而且是先更新原来的根旋转后变成子节点再更新新的根。add里先做contains判重这一步虽然多了一次查询但对集合语义来说必不可少否则重复插入会破坏二叉搜索树的“不重复”约束。中序遍历我用迭代方式实现避免递归过深带来的栈风险def inorder(self): res [] stack [] node self.root while stack or node: while node: stack.append(node) node node.left node stack.pop() res.append(node.val) node node.right return res这个迭代遍历的核心是“一直往左压栈弹出来时访问再转向右子树”。理解了这三步中序、前序、后序其实都是同一套模板的变体。3.3 范围查询的递归剪枝实现范围查询是树形集合对比哈希集合最亮眼的操作。给定 [lo, hi]我们希望只访问可能落在区间内的子树而不是遍历整棵树def range_query(self, lo, hi): res [] self._range(self.root, lo, hi, res) return res def _range(self, node, lo, hi, res): if not node: return if lo node.val: self._range(node.left, lo, hi, res) if lo node.val hi: res.append(node.val) if node.val hi: self._range(node.right, lo, hi, res)这段代码的剪枝逻辑很巧妙只有当lo node.val时左子树里才可能存在值大于等于 lo 的节点否则整棵左子树都比 lo 小不用进去。当前节点自身判断一次即可。只有当node.val hi时右子树才可能有值小于等于 hi 的节点否则整棵右子树都比 hi 大同样不用进去。从根开始每层最多递归进入一侧子树深度 O(log N)输出结果又只需要遍历 K 个节点整体复杂度 O(log N K)。这里的 K 是指实际结果数量而不是集合总大小所以即使集合里有百万数据、查询区间只有几个元素速度也很快。3.4 正确性验证与自测清单写完代码不能直接上线至少要跑一轮自测。我的测试思路是这样的s OrderedSet() for v in [10, 5, 15, 3, 7, 12, 18, 1, 6]: s.add(v) assert s.inorder() [1, 3, 5, 6, 7, 10, 12, 15, 18] assert s.contains(7) is True assert s.contains(8) is False assert s.range_query(5, 15) [5, 6, 7, 10, 12, 15] s.add(5) assert s.inorder() [1, 3, 5, 6, 7, 10, 12, 15, 18] print(all tests passed)除了使用逐字比对之外我还强烈建议做随机对照测试生成一组随机数对 OrderedSet 依次 add然后把同一组数放进 Python 自带的 sorted set 思维用 set 去重后排序比对结果。随机测几千组能覆盖绝大多数平衡调整分支。顺带提一下删除操作。AVL 的删除需要处理“有两个子节点的节点被删”的情况需要找前驱或后继替换删除后还要回溯平衡。代码量是插入的两倍以上很容易写错。在业务开发中如果删除频率不高更稳妥的做法是标记删除给节点加一个 deleted 标记查询和遍历时跳过它。等标记节点积累到一定比例再重建整棵树。这是典型的用空间换时间也是多年工程实践沉淀下来的务实方案。4. 落地场景内存索引、磁盘索引与特殊集合4.1 标准库有序集合的工程约定几乎所有主流语言的标准库里都有有序集合或有序映射的现成实现比如有序 Set、有序 Map。这些容器的底层几乎都是平衡树或类似的树形结构它们的接口约定也是一致的元素必须支持“可比较”也就是能比大小。元素一旦放入集合参与排序的关键字段就不能再修改。迭代器遍历结果始终保持自然的升序。实际工程里大部分人不需要自己实现平衡树直接用标准库就够了。手写一遍的价值在于当你遇到自定义对象比较逻辑、批量构建、并发访问、持久化恢复等特殊场景你能准确判断底层结构的行为而不是把它当黑盒踩了坑还不知道怎么排查。4.2 B 树磁盘上的集合索引前面讨论的平衡树都是为内存设计的。内存和磁盘的核心差异是内存里访问任何字节速度都差不多磁盘上读取连续的数据块和随机读取性能差距可能是几个数量级。B 树正是为磁盘场景优化的集合索引结构。B 树的核心设计有两点。第一是高扇出每个节点可以存几百个键树的高度被压得很低。十万亿级别的数据量B 树通常也只需要个位数的层级意味着查询只需要几次磁盘 IO 就能完成。第二是叶子节点用链表串起来范围查询时只要定位到起点后面一路顺序读叶子节点即可非常契合数据库索引的扫描场景。内存平衡树和磁盘 B 树的取舍本质上是“树节点大小”适应存储介质特性的问题。你用平衡树做百万级内存集合一切顺畅一旦数据量超过内存或者要求持久化落盘B 树能让你在磁盘上依然保持类似内存索引的查询体感。这也是数据库索引、文件系统目录索引会大量使用 B 树的原因。4.3 并查集与字典树集合的另类树形实现并不是所有“树形集合”都长得像二叉搜索树。实际工程里还有两种极具代表性的树形集合并查集和字典树。并查集解决的是“动态连通性”问题判断两个元素是否在同一个集合以及把两个集合合并成一个。它的树形结构非常特殊子节点指向父节点根节点代表整个集合。优化手段是路径压缩和按秩合并。路径压缩的精髓在下面这段代码里def find(x): if parent[x] ! x: parent[x] find(parent[x]) return parent[x]第一次查找某个节点时顺路把沿途所有节点直接挂到根节点下面下一次查找就是 O(1)。这个“查一次整条路都会变短”的思路非常优雅在处理连通域、等价关系、冗余连接等场景时是主力结构。字典树也叫前缀树专门用来处理字符串集合。它把公共前缀合并成同一个节点避免了单独存每个字符串时的重复存储。判断一个字符串是否存在时不需要跳跃式比较只需要沿着字符路径走一遍复杂度只跟字符串长度相关和集合里有多少字符串无关。自动补全、敏感词过滤、IP 路由表、通讯录搜索背后都是这种前缀共享的思想。从并查集和字典树可以看到“集合 树形结构”的组合不是只有“有序容器”一种答案。业务需求里的集合可能是“动态分组”意义上的集合也可能是“前缀匹配集合”树形结构总能为不同需求提供对应的形态。5. 常见问题与排查技巧实录5.1 可变对象作为集合元素导致“失去秩序”这个问题非常隐蔽我见过不止一次。你往有序集合里放了一个自定义对象业务后续又改了对象里参与排序的字段值集合内部的结构没有感知依然保留着旧的排序关系。当你再查询或遍历时得到的是一个结构混乱的集合contains 可能返回错误结果range_query 也可能漏数据。这类问题几乎无法通过集合自身修复因为集合内部的树形结构已经和对象的真实值不一致了。最稳妥的规避手段是参与排序的字段设计成不可变如果确实需要修改先把对象从集合移除修改后再重新插入。把这个约定写进设计文档或者直接在自定义对象的排序字段上禁用 setter。5.2 比较器与内部字段不一致导致“隐形丢数据”有序集合判断元素是否重复依赖的是比较器而不是 equals。如果比较器认为两个对象“相等”集合就会认为它们是同一个元素后插入的直接被丢弃。这个行为有时候符合预期有时候会造成数据丢失比如你希望按 ID 去重但比较器错误地比较了 name那两个 ID 不同但 name 相同的对象就会互相覆盖。排查时记住一个规律有序集合的“相等”完全由比较器定义。任何自定义比较器都要保证自反性、对称性、传递性而且要和业务上定义的“唯一键”严格对应。批量插入前先用小数据集实测比事后排查数据丢失成本低得多。5.3 树高失控与递归栈溢出标准平衡树一般不会出现这个问题但如果你写的自定义集合没有正确维护平衡插入大量有序数据后树高会线性增长。此时任何递归操作都可能触达系统栈上限程序直接抛栈溢出错误。排查时先打印树的高度如果高度远大于 log N基本可以确定是平衡代码有 bug。最常见的错误是旋转后没有正确更新子树高度或者插入路径上少了平衡因子检查。建议在插入方法里加一段调试断言遍历全树验证每个节点平衡因子绝对值都不超过 1。测试通过后再移除断言能挡住大部分平衡逻辑问题。5.4 两个有序集合合并的性能陷阱合并两个有序集合最直观的做法是把小的集合逐个插入大的集合。这个方案本身没错但如果两个集合都非常大逐个插入会带来大量平衡旋转性能很差。更高效的方式是“批量建树”把两个有序序列做归并排序得到合并后的有序数组再以中间元素为根递归构建平衡树。这样一次建树的时间复杂度是 O(N)比逐点插入 O(N log N) 快一个量级。如果你的场景经常做集合合并可以先把集合导成有序列表用批量算法重建树整体收益非常明显。最后再分享一个我的个人经验学习树形集合不要只停留在“我会用标准库”这个层面。找一个小项目手动实现一遍 AVL 插入和中序遍历跑几百组随机数据对照测试之后再回去看标准库的接口设计你会突然明白很多之前觉得“就那样”的设计。这套从原理到工程的能力遇到数据库索引、并发容器、分布式一致性问题时还会反复派上用场。