数据结构之Trie树
概述
Trie 树,名字源于 retrieval,意为检索、找回,又称为前缀树、字典树,是一种有序树形结构,是哈希树的变种,用于保存关联数组,通常是字符串。与二叉查找树不同,键不是保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀。一般情况下不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。
graph TB root((/)) root ---- t((t)) t ---- h((h)) h ---- r2((r)) r2 ---- e3((e)) e3 ---- e4((e)) t ---- r((r)) r ---- e1((e)) e1 ---- e2((e)) r ---- i((i)) i ---- e((e)) r ---- y((y)) root ---- w((w)) w ---- o((o)) o ---- r3((r)) r3 ---- d((d))