学习笔记

trie树概念（字典树） 字典树，即 Trie 树，又称单词查找树或键树，是一种树形结构。 典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索擎系统用于文本词频统计。 它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

trie是多叉树，结点不存任何的完整单词

从根结点从某一个结点， 路径上经过的字符连起来， 路径上经过的字符连起来就是对应的字符串 trie树的性质

1. 结点本身不存完整单词；

2. 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串；

3. 每个结点的所有子结点路径代表的字符都不相同

核心思想 Trie 树的核心思想是空间换时间。 利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的

启发式搜索 A*

启发式函数：h (n），它用来评价哪些结点最有希望的是一个我们要找的结点，h (n）会返回一个非负实数也可以认为是从结点 n 的目标结点路径的估计成本。

启发式函数是一种告知搜索方向的方法。它提供了一种明智的方法来猜測哪个邻居结点会导向一个目标。

AVL 问题： 插入和删除操作比较频繁的时候，需要频繁的旋转，调整树的结构， 导致性能下降，但是查询效率高， 因为它更加平衡， 树的深度相对小。

R-B tree： 插入和查询操作都比较频繁的时候，一般是使用红黑树

map和set一般都是使用红黑树实现的

数据库一般是使用的AVL