- 1.字典树的数据结构
- 2.字典树的核心思想
- 3.字典树的基本性质
字典树，即Trie树，又称单词查找树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。 优点：最大限度的减少无谓的字符串的比较，查询效率比哈希表高。
- 1.节点本身不存完整单词
- 2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
- 3.每个节点的所有子节点路径代表的字符都不相同。
- 注：节点可以存储额外信息，字符落下在这个节点的统计信息
- Trie的核心思想是空间换时间
- 利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
- 组团、配对问题
- Group or not?
- makeSet(s): 建立一个新的并查集，其中包含s个单元素集合。
- unionSet(x,y):把元素x和元素y所在的集合合并，要求x和y所在的集合不相交，如果相交则不合并。
- find(x)：找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。
- parent[i] = i 集合领头元素
- 剪枝
- 双向BFS
- 启发式搜索（A*）
- 1.朴素搜索
- 2.优化方式：不重复（fibonacci）、剪枝（生成括号问题）
- 3.搜索方向：
- DFS :depth first search: 深度优先搜索
- BFS: breadth first search : 广度优先搜索
- 双向搜索、启发式搜索
- Two-ended BFS 双向BFS
- 基于BFS代码
- pop时加入智能
- 优先级函数：估价函数
- 启发式函数：h(n)，它用来评价哪些节点最优希望的是一个我们要找的节点，h(n)会返回一个非负实数，也可以认为节点n的目标点路径的估计成本。
- 启发式函数是一种告知搜索方向的方法。它提供了一种明智的方法来猜测哪个邻接点会导向一个目标。
- 15.1.AVL树
- 1.Balance Factor(平衡因子)：是它的左子树的高度减去它的右子树的高度（有时相反），balance factor = {-1,0,1}