树与层次结构
字典树
字典树是一种专为存储字符串而生的树：你所走过的路径拼出了键，而不是把键塞进某一个节点。每条边都标着一个字符，于是单词“cat”就是从根出发的路径 c → a → t。共享前缀的单词也共享拼出该前缀的那段路径：“car”和“cat”会一起经过 c → a，再分叉开来。它的名字源自 reTRIEval（检索），读音通常念作“try”，以便和“tree（树）”区分。
查找一个键就是从根出发、一次一个字符地往下走，所以一次查找耗时 O(L)，其中 L 是字符串的长度——而且很妙的是，存的单词越多，它也不会变慢。这相对于平衡搜索树是个实打实的优势，后者的 O(log n) 会随键的数量增长。通常会在某个节点上做标记，表示“这里结束了一个完整单词”，于是“car”和“card”可以同时存在于这同一个结构里。
正因为共享前缀寄存在共享路径上，字典树几乎免费地回答前缀问题：走到“ca”所对应的节点，它底下的一切都是以“ca”开头的单词——这恰好是自动补全、拼写检查器和 IP 路由表所需要的。代价是内存：朴素的节点会为每个可能的下一个字符都留一个槽位（比如小写字母就是 26 个），所以稀疏的字典树会浪费不少空间，这也是为什么会有基数树这样的压缩变体。
// root
// |c
// (c)
// |a
// (a)
// r/ \t
// (r)* (t)* <- car, cat
// |d
// (d)* <- card
struct TrieNode {
std::array<TrieNode*, 26> next{}; // a..z
bool isWord = false;
};每个子节点槽位以下一个字符为键；isWord 标记一个完整的键。
读作“try”（源自 reTRIEval），以与“tree”区分；查找开销 O(L) 取决于键的长度，而非已存键的数量。
又称
另见