Radix Tree · 压缩前缀树
一组字符串需要共享前缀地存储，并支持「以某段开头的有哪些」「最长能匹配到哪条」这类查询。本页从逐字符的 trie 讲起，逐步压成 radix tree，再把它的三种核心操作各拆一节：插入（含 edge split 边分裂）、前缀查询 (autocomplete)、最长前缀匹配（IP 路由表的内核）。每节都是一棵能单步插入 / 逐边下行的真树，代码逐行点亮、节点随操作建立与分裂。
1 · 前缀树 trie · 一个字符一个节点
radix tree 的地基是 trie（前缀树，读作 "try"）。它把一组串逐字符码进一棵树：从 root 出发，每个字符走一条边、占一个节点；共同前缀走同一条路径，直到岔开才分支。一个串的最后一个字符所在节点标成词尾 ●——这样既能存一堆词、又天然共享了它们的公共开头。
查找就是「顺着字符往下走」。 要查 car 是否存在：从 root 沿
三条边下行，走得通且终点是词尾 ● 就命中；某一步没有对应的边、或走到头不是词尾（例如只存了 card 没存 car），就不存在。代价只和被查串的长度有关，与词表里有多少词无关——这是 trie / radix 这类前缀结构的核心优势。
但 trie 的节点开销偏高。 看上面 card 这条：
一路下来，中间的 r、d 这些节点各自只有一个孩子，却每个都占一个节点 + 一条边。词越长、独有的尾巴越长，这种「只有一个孩子的链」就越多——没有分叉、纯过路，属于冗余开销。路径压缩那节把这些单孩子链压成一条边,trie
就变成了 radix tree。
2 · 路径压缩 · 单孩子链 → 一条边
radix tree 与 trie 的关系只差一条规则：凡是「只有一个孩子、自己又不是词尾」的中转节点，都并入父边。 一条边的标签于是从单字符变成一整段串——没有分叉的地方不再额外占节点。结构本质不变（查找仍按字符走），节点数显著减少。下面同一组词、trie 与 radix 并排，对比两者的节点数。
压缩比取决于「前缀里有多少分叉」。 试试上面几个预设：纯一条链 () 几乎全是单孩子，radix 把整串压成少数几条边，节省最多；而 te / to 分叉 这种分叉密集的，可压的单孩子链少，节省有限。经验法则：radix tree 的节点数 ≈ key 的个数 × 常数，与 key 长度基本无关——长串的「独有尾巴」都被压成一条边。
查找完全不受影响。 压缩只是把「沿途单字符节点」合并，逐字符下行的逻辑不变——走到一条边时，要么这段串整条匹配（继续下行），要么从某字符起岔开（则不存在）。换来的代价只有一个：插入时可能要把一条边分裂 (edge split)——这正是插入与 edge split那节的主题。
3 · 插入与 edge split · 边分裂
往 radix tree 插一个串，从 root 沿边下行，一路上每条边只有四种遭遇：其一，没有以当前首字符开头的边 → 直接挂一条新叶子边;其二，某条边被整条吃下 → 顺它继续下行；其三，与某条边只共享一段前缀 → 必须在共享点把这条边分成两段 (edge split);其四，要插的串恰好在某点用完 → 把该点标成词尾 ●。其中「只共享一段前缀」是 radix tree 独有、也最关键的一步。
split 改了什么？ 当边 romulus 遇到要插的 romane，二者只共享 rom：新建一个中间节点 rom 顶替原位，把原边降为它的孩子、标签削去公共前缀变成 ulus，再把要插串剩下的 ane 挂成
rom 的另一条边。原来那个词 (romulus) 没有丢失任何字符——它仍能从
拼回，只是中间多了个分叉点。删除则是它的逆操作：删到某节点只剩一个孩子时，把它并回父边。
4 · 前缀查询 · autocomplete 的内核
搜索框打几个字就弹出一串候选，内核就是 radix tree 的前缀查询，分两步：其一，先沿边把 prefix 走完，停在它的落点（可能正好是某节点，也可能落在某条边中间）；其二，落点底下整棵子树的所有词尾，就是「以 prefix 开头」的全部候选。比起把整张词表从头扫一遍，它只走 prefix 那么长一段路就定位到了候选的「窝」。
为什么落点可能在「边中间」？ 边上是压缩过的串。查 rub 时，若树里那条边是 rub 后面直接接
,prefix 正好吃到边的末尾，落点是个真实节点；但若边是 rubi 这样更长的压缩段，查 rub 会停在这条边内部——没关系，只要 prefix 是这条边的前缀，边的整个目标子树仍全部算候选。代价只和 prefix 长度有关，与词典多大无关。
这就是真实搜索框背后的结构之一。 输入法候选、IDE 自动补全、命令行 Tab 补全、地图地名联想，内核都常是 trie / radix tree 的前缀查询（工业实现还会在节点上挂热度 / 权重，子树里再按权重取 Top-K）。
5 · 最长前缀匹配 · IP 路由表的内核
路由器收到一个目的地址，要在路由表里挑一条转发。表里全是网段前缀（CIDR，如 10110000/4 意为「头 4 位是 1011 的都走这」）。多条前缀可能同时命中一个地址——规则是取最具体的那条，即前缀最长的：这就是最长前缀匹配 (LPM)。而路由表本身，正是一棵建在比特上的 radix tree：沿地址的比特逐位下行，每经过一个挂了路由的节点就记一次，走到底取最深的那个。
为什么用 radix tree 而不是「逐条比对路由表」？ 表里可能有几十万条前缀。LPM 走 radix tree 只沿地址的比特下行 O（地址位数） 一趟，与表里有多少条前缀无关；而且「谁更具体」不靠运行时比长度，而是编进了结构——越深的节点前缀天然越长，走到的最深路由就是最长匹配。真实内核还会用 LC-trie / Poptrie 等变体进一步把多层比特压进一个节点、用查表代替逐位走，以支撑每秒上亿次的转发查询。
同一棵树，两处落地。 这里前缀是比特（IP 路由）;「路由设计」系列的 HTTP router 里前缀是 path 段——都是把一张表编译成 radix tree，让「最该命中的那条」由下行顺序 / 深度决定，而不是靠排序或逐条扫。