Trie 树

**Trie** 也称为数字树，有时又叫基数树或前缀树，是一种搜索树，用于存储键通常为字符串的动态集合或关联数组。与二叉搜索树不同，树中的节点并不存储与之关联的键，而是由它在树中的位置来定义其所对应的键。任一节点的所有后代都具有与该节点关联字符串的共同前缀，而根节点则对应空字符串。“trie”一词正取自“re**trie**val”（检索），它是为实现信息检索而设计的一类树形结构。典型的应用场景包括存储预测文本或自动补全词典，例如智能手机或搜索引擎中的这类功能。