← 首页 / 树 · 遍历、平衡 BST 与前缀 / 度量树 待审核 10 页

树 · 遍历、平衡 BST 与前缀 / 度量树

树 (tree) 是最基础的层级结构:每个节点至多一个父、若干孩子。本话题把仓库里的树系列收拢到一处,分三条线展开——怎么走遍一棵树、怎么让搜索树不退化成链表、怎么用树结构做前缀共享与相似度检索。

第一条线是遍历:前 / 中 / 后序与层序,以及递归 / 显式栈 / Morris 三种实现。第二条线是 binary search tree (BST) 的平衡:红黑树用颜色、AVL 用高度、treap 用随机 priority,各自把树高压在 O(log n);次优查找树换一个目标——静态带权查找下最小化平均查找长度。第三条线走出 BST:radix tree 折叠单孩子链、压缩共享前缀,BK-tree 借编辑距离的三角不等式在词典里整子树剪枝。

遍历:三种次序 × 三种实现

「遍历」= 按某种次序访问每个节点各一次。前 / 中 / 后序 (深度优先) 差别只在 visit(node) 相对递归左右子树的时机;层序 (广度优先) 则把栈换成队列。同一棵 BST,看三种次序如何由 visit 时机决定,又如何用递归 / 显式栈 / Morris 三种技巧走完。

递归 · 遍历的定义本身

递归：visit 写在哪，就是哪种序

最贴近定义的写法。前 / 中 / 后序只差一行——visit(node) 写在 dfs(left) / dfs(right) 之前、之间、之后。单步看调用栈随递归压入弹出，这正是 O(h) 额外空间的来源，也是后两种技巧要替代或省掉的东西。

 显式栈 · 把递归翻成循环

迭代：用一个栈替代调用栈

把递归手动展开成 while 循环 + 一个显式栈。前序最直接（弹栈即访问，右、左依次压栈）；中序「一路向左压栈，弹栈时访问」；后序最难，需 last 指针判断右子是否已处理。单步看栈的内容如何增删。

 Morris · O(1) 额外空间

Morris：借空指针，不用栈也不递归

灵感来自线索二叉树：把节点本该为 null 的 right 临时指向中序后继，走完左子树顺线索自动返回，用完即拆。全程不开栈、不递归，额外空间压到 O(1)，代价是遍历途中树被临时改写。含线索演示、单步装拆、代价分析三节。

 层序 BFS · 用队列逐层

层序：用队列逐层从左到右

另一族——广度优先 (BFS)。不用栈而用队列 (FIFO)：出队即访问，左右子排到队尾等下一层。和前序迭代只差「从容器哪一端取元素」。含「按层 size 快照」分组写法，输出区按层展示。

两条轴,九个格子

把三种次序(前 / 中 / 后)与三种技巧(递归 / 显式栈 / Morris)交叉,就是九种遍历写法。看通它们能收获两个角度的统一: 横看 (固定技巧,换次序):同一种实现里,前 / 中 / 后序只差 visit(node) 这一句挪到哪一行——递归里挪在三个递归调用之间,Morris 里挪在「装线索 / 拆线索」两个时刻之间。 竖看 (固定次序,换技巧):同一种次序,本质都在用一个栈记住「左子树走完后该回到哪个祖先」。递归把这个栈交给语言运行时 (调用栈),显式栈迭代把它搬到堆上一个数组,Morris 则把它藏进左子树最右节点那个闲置的 right 指针里——省掉了与树规模相关的额外内存。

深度优先 vs 广度优先:栈与队列之差

前 / 中 / 后序同属深度优先 (DFS)——靠栈 (后进先出) 记回头路,一头扎到底再回溯。层序遍历则属广度优先 (BFS)——靠队列 (先进先出) 逐层铺开。耐人寻味的是:层序的代码和前序迭代几乎一模一样,唯一区别是「从容器哪一端取元素」——栈从尾部取 (深度优先)、队列从头部取 (广度优先)。一字之差,遍历就从「纵深」变成了「逐层」。两者的峰值额外空间也不同:DFS 是树高 O(h),BFS 是树最宽一层的宽度 O(w)。

遍历 · 延伸阅读

LeetCode 对应题

平衡与查找 BST

朴素 BST 按插入顺序会退化成链表、查找慢到 O(n)。三棵动态平衡树各走一条路把树高压回 O(log n):红黑树用颜色 + 5 条 property、AVL 用 balance factor、treap 用随机 priority。次优查找树则是静态场景的另一个目标——查找概率不均时最小化平均查找长度。

walkthrough · 5 property → 插入 / 查询 / 删除

red-black tree · 拆解与动手

从 5 条 property 与 black height 出发，理解规则其实是 2-3-4 tree 的翻译，再单步演示 rotation、插入 fixup、查询与删除 double black 修复。

 walkthrough · balance factor → 四种旋转 → 插入 / 删除 → vs 红黑树

AVL tree · 拆解与动手

从 balance factor 的定义出发，看它凭什么把树高锁在 ~1.44·log₂n，再单步过四种失衡形态 (LL / RR / LR / RL) 的旋转、插入与删除的回溯再平衡，最后对比 red-black tree 的取舍。

 randomized BST · Cartesian tree

treap 树堆 · 拆解与动手

从随机 priority 为何能平衡出发，单步演示旋转式 insert / delete、无旋转的 split / merge，以及按下标分裂的 implicit treap 区间翻转。每个 demo 都能改输入、单步播放、随时校验两条性质。

 WPL · ΔP 选根 · DP 对照

次优查找树 · 静态带权查找的工程折中

带权查找的 WPL 度量、ΔP 选根的次优构造 O(n log n)、O(n³) 动态规划的最优对照，并量化两者的代价与质量折中。

平衡 BST · 延伸阅读

red-black tree

AVL tree

treap

次优 / 最优 BST

前缀树与度量树

不以「大小比较」组织的两类树。radix tree 把 trie 的单孩子链折叠成一条边,共享前缀地存串,支撑 autocomplete 与 IP 路由表的最长前缀匹配。BK-tree 以编辑距离为度量,靠三角不等式把「找最相近的词」变成整子树剪枝。

trie · 压缩 · 插入 · 前缀查询 · 最长匹配

Radix Tree · 压缩前缀树

从逐字符 trie 出发压成 radix tree，再拆解三种核心操作：插入（含 edge split）、前缀查询(autocomplete)、最长前缀匹配（IP 路由表的内核）。每节都是能单步操作的真树。

 编辑距离 · 三角不等式 · 剪枝

BK-tree · 模糊查询如何剪枝

从编辑距离与它满足的三角不等式讲起，逐词建树观察孩子如何按距离挂载，再单步查询看一条不等式如何剪掉大半棵树。每节都可改输入、单步播放。

前缀树与度量树 · 延伸阅读

radix tree

  • 本站 · 路由设计 / 路由匹配引擎 同款 radix tree 用在 HTTP router 上:把整张路由表编译成前缀树,static → param → wildcard 的优先级「编进结构」。这里讲数据结构本身,那里讲它在 web 路由里的落地。
  • 本站 · String Search KMP / BM / Rabin-Karp 同是字符串结构家族:那条讲「一个 pattern 在长文本里怎么快速找到」,这条讲「一堆串怎么共享前缀地存与查」。
  • Wikipedia · Radix tree en.wikipedia.org 定义与术语 (radix r、PATRICIA、edge label 压缩) 的权威出处,含经典的 romane/romanus/romulus/… 示意图 (本系列「路径压缩」「插入」沿用这组词)。
  • LWN · The XArray data structure lwn.net 对应「真实应用」:Linux 内核的 page cache 长期用 radix tree 索引页号,后来演进成 XArray —— radix tree 在系统底层的代表性落地。
  • Linux · ip route / FIB man7.org 对应「最长前缀匹配」节:内核转发表 (FIB) 用 LC-trie / radix 做 LPM,ip route get 能看到一个地址实际命中哪条前缀。

BK-tree