Trie 树

Trie（也称为数字树，有时也称为基数树或前缀树）是一种搜索树，用于存储动态集或关联数组，其中键通常是字符串。与二叉搜索树不同，树中的任何节点都不存储与该节点关联的键；相反，它在树中的位置定义了与之关联的键。任何节点的所有后代都具有与该节点关联的字符串的公共前缀，而根节点与空字符串关联。因此，「trie」是一种表示信息「检索」的方式，是一种用于此目的的树结构。典型的使用场景可以是存储预测文本或自动完成字典，例如在您的智能手机或搜索引擎上找到的。