字典树，即 Trie 树，称单词查找树或键树，前缀树
- 结点本身不存完整单词
- 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的 字符串；
- 每个结点的所有子结点路径代表的字符都不相同
最大限度地减少 无谓的字符串比较，查询效率 比哈希表高
组团、配对问题
- 去重复
- 搜索过程中移除决策树中分辨能力较弱的部分而减少树大小的方法，降低复杂度
- 双向搜索算法是一种图的遍历算法，用于在有向图中搜索从一个顶点到另一个顶点的最短路径问题
- 算法同时运行两个搜索：一个从初始状态正向搜索，另一个从目标状态反向搜索，当两者在中间汇合时搜索停止
- 启发函数：h(n)，用来评价哪些节点最有希望的是一个我们要找的节点，h(n)会返回一个非负实数，也可以认为是从结点n的目标结点路径的估计成本
- 启发式函数是一种告知搜索方向的方法
-
AVL树是一个平衡二叉搜索树，每个节点左右两子树高度差不超多1
-
Balance Factor（平衡因子）：节点的左子树的高度减去右子树的高度（有时相反），balance factor = {-1, 0, 1}
-
插入和删除操作可能需要一次或多次旋转实现树的重新平衡
-
四种旋转操作：
-
- 右右子树 —> 左旋
-
左左子树 —> 右旋
-
左右子树 —> 左右旋
-
右左子树 —> 右左旋
-
不足：节点需要存储额外信息、且调整次数频繁
-
红黑树是一种近似平衡二叉搜索树，它能确保任何一个节点的左右子树高度差小于二倍
-
满足的条件：
-
- 每个节点要么是红色，要么是黑色
-
根节点是黑色
-
每个叶子节点（NIL节点）是黑色
-
不能有两个相邻的红色节点
-
从任一个节点到其每个叶子节点所有路径都包含相同数目的黑色节点
-
关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长
-
查找、插入、删除的时间复杂度：O(logn)，n是树中元素的数目
- AVL树提供更快的查找比红黑树，因为AVL提供更严格平衡，没增删一次都要维护平衡。
- 红黑树提供了更快的插入和删除操作比AVL树，由于相对宽松的平衡，旋转次数较少
- AVL树每个节点需要存储平衡因子和高度，需要更多存储空间，而红黑树每个节点只需要用一个bit位来存储0和1表示红或者黑
- 大多数语言库都是使用的红黑树（Java1.8 Map），AVL树则用于需要更快检索的数据库
- 读多写少的场景用AVL树，除此之外多用红黑树。