字典树type
status
date
slug
summary
tags
category
icon
password
Property
字典树（Trie）：又称为前缀树、单词查找树，是一种树形结构。顾名思义，就是一个像字典一样的树。它是字典的一种存储方式。字典中的每个单词在字典树中表现为一条从根节点出发的路径，路径相连的边上的字母连起来就形成对应的字符串。
例如下图就是一棵字典树，其中包含有
a、abc、acb、acc、ach、b、chb 这 7 个单词：
这棵字典树用边来表示字母，从根节点到树上某一节点的路径就代表了一个单词。比如 1 → 2 → 6 → 10 表示的就是单词
acc。为了清楚地标记单词，可以在每个单词的结束节点位置增加一个 end 标记（图中红色节点），表示从根节点到这里有一个单词。字典树的结构比较简单，其本质上就是一个用于字符串快速检索的多叉树，树上每个节点都包含多字符指针。将从根节点到某一节点路径上经过的字符连接起来，就是该节点对应的字符串。
字典树设计的核心思想：利用空间换时间，利用字符串的公共前缀来降低查询时间的开销，最大限度的减少无谓的字符串比较，以达到提高效率的目的。
字典树的基本性质：
- 根节点不包含字符，除根节点外，每个节点都只包含一个字符
- 从根节点到某一节点，路径航经过的字符串连接起来，就是该节点对应的字符串
- 每个节点的所有子节点包含的字符串都不相同
假设单词的长度为
n，前缀的长度为 m，字符集合的维度为 d，则：- 插入一个单词：时间复杂度为 ；如果使用数组，则空间复杂度为，如果使用哈希表实现，则空间复杂度为
- 查找一个单词：时间复杂度为 ；空间复杂度为
- 查找一个前缀：时间复杂度为；空间复杂度为
字典树一个典型的应用场景就是：在搜索引擎中输入部分内容之后，搜索引擎就会自动弹出一些关联的相关搜索内容。可以从中直接选择自己想要搜索的内容，而不用将所有内容都输入进去。这个功能从一定程度上节省了我们的搜索时间。
我们输入「字典树」后，底下会出现一些以「字典树」为前缀的相关搜索内容：
这个功能实现的基本原理就是字典树。当然，像 Google、必应、百度这样的搜索引擎，在这个功能能的背后肯定做了大量的改进和优化，但它的底层最基本的原理就是「字典树」这种数据结构。
除此之外，可以把字典树的应用分为以下几种：
- 字符串检索：事先将已知的⼀些字符串（字典）的有关信息存储到字典树⾥， 查找⼀些字符串是否出现过、出现的频率。
- 前缀统计：统计⼀个串所有前缀单词的个数，只需统计从根节点到叶子节点路径上单词出现的个数，也可以判断⼀个单词是否为另⼀个单词的前缀。
- 最长公共前缀问题：利用字典树求解多个字符串的最长公共前缀问题。将⼤量字符串都存储到⼀棵字典树上时， 可以快速得到某些字符串的公共前缀。对所有字符串都建⽴字典树，两个串的最长公共前缀的长度就是它们所在节点最近公共祖先的长度，于是转变为最近公共祖先问题。
- 字符串排序：利⽤字典树进⾏串排序。例如，给定多个互不相同的仅由⼀个单词构成的英⽂名，将它们按字典序从⼩到⼤输出。采⽤数组⽅式创建字典树，字典树中每个节点的所有⼦节点都是按照其字母⼤⼩排序的。然后对字典树进⾏先序遍历，输出的相应字符串就是按字典序排序的结果。
实现 Trie (前缀树)
请你实现 Trie 类：
Trie()初始化前缀树对象。
void insert(String word)向前缀树中插入字符串word
boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回 false
boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为 prefix ，返回 true ；否则，返回 false
示例：
字典序的第K小数字
题目：给定整数
n和k，返回 [1, n]中字典序第k小的数字示例：
将n=12转换为字典树时候，可以发现字典序不过就是这颗字典树的先序遍历
但是很显然将整棵树构建起来是不现实的，当的时候就是上亿个节点了。因为这颗字典树是的十叉数，并且具有明显的先序遍历递增的特点，那么可以通过计算得到某个节点下的子树节点的总数而跳过遍历的时间
- 1下的第一层：最左端为 ，即；最右端为，即，合计。换成：最左端为；最右端为
- 1下的第一层：最左端为100，最右端为112(即n)，而不是200了，合计
112-100+1 = 13
- 合计
10+13 = 26
如果求出以i为根的子树节点有
nodes个- 如果
nodes比k少，那么这个部分都可以全部跳过，第k小的数肯定不在这些节点里，i右移
- 如果
nodes比k多，那么第k小的数一定在这个里面，并是以i开头的数，i下移
- 因此可以移动
i指向的节点，直到跳过的节点数达到k