算法训练营第07周学习笔记
字典树（Trie）和并查集
字典树（Trie又称单词查找或键树）的基本结构是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。 其优点是:最大限度的减少无谓的字符串比较，查询效率比哈希表高。 首先，节点本身不存在任何单词，它只存它要去到下一个路径（字符），接下来每个节点依次进行。常用的字符中第一个字符就放在根节点上面，根据你输入不同的字符它就开始进行分叉，（Trie不是一颗二叉树，而是一个多叉树）根据开始分在不同的地方而分流。 1.节点本身不存完整单词； 2.从根节点到某一节点，路径上经过的字符连接起来就为该节点对应的字符串； 3.每个节点的所有子节点路径代表的字符都不相同。 在需要统计频次的时候就会在节点存储额外信息中添加一个对应数字代表单词统计的计数。当然也可以存储其他类型的信息，只不过是统计词频时在后面可以按统计结果提供相应的推荐。 节点里面的内部显示结构为每个节点提供存储下一个节点方向的指针，这里存储的指针就不再是用left和right表示左右节点了，而是直接用对应的字符来指向下一个节点。 字典树的核心思想就是用空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
并查集是比较跳跃的数据结构，有固定“套路”需要模板化练习记忆，不像动态的规划或者搜索有那么多可发挥的自有空间。也就这类的题目代码相对比较固定。 并查集要解决的问题场景主要是应用在组团和配对的问题上，也就是在现实问题中需要快速判断两个个体是否在一个集合当中的问题。 并查集是一种数据结构在并查集的场景中主要有三个要实现的函数： 1.makeSet（s）:建立一个新的并查集，其中包含s个单元素集合； 2.unionSet（x,y）：把元素x和元素y所在的集合合并，要求x和y所在的集合不想交，如果相交则不合并； 3.find（x）：找到元素x所在的集合代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以。
初级搜索：就是傻搜索或暴力搜索 1.朴素搜索 2.优化方式——不重复（fibonacci）、剪枝（生成括号问题） 3.搜索方向——深度优先搜索（DepthFirstSearch）和广度优先搜索（BreadthFirstSearh）
优化/高级搜索的两种方法是：双向搜索和启发式搜索 双向搜索可以理解为它从起点和终点分别做一个广度优先，然后在中间相遇；启发式搜索就不再用栈或者队列这种先入后出/先入先出的形式了，而是用一个优先队列放在这里面，而优先队列是按照节点的优先级的做法，这就是启发式搜索，也叫A*算法或者叫做优先级搜索。
（复习）回溯法：本质简化公式是——分治+试错（递归）=回溯法 它采用试错的思想，并尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确解答的时候，它将取消上一步甚至上几步的计算，再通过其它的可能性分步解答再次尝试寻找问题的答案。 回溯法通常用最简单的递归方法来实现，在反复重复上一步的步骤动作后可能会出现两种情况： 1.找到一个可能存在的正确答案； 2.在尝试了规定算法范围内的所有可能分步方法后宣告该问题没有答案； 3.在最坏的情况下，回溯法很可能会导致一次复杂度为指数级时间的计算。
启发式搜索（Heuristic Search /A*）:其中的Heuristic可以认为是智能搜索或者根据某一项条件不断地优化搜索的方向。其思想本质就是根据优先级不断地去找要找的点，先用优先级搞得搜索即可就像一边搜索一边思考一样，是思考型搜索，所以叫启发式搜索。 A*算法或启发式搜索就是基于BFS方式进行搜索。所谓的智能搜索部分就是把队列或者栈换成优先队列方式。其关键点在于这个启发式的函数/估价函数也就是这个优先级怎么定义？ 估价函数——启发式函数：h（n），用来评价哪些节点最有希望的是一个我们要找的节点，h（n）会返回一个非负实数，也可以认为是从节点n的目标节点路径的估计成本。 启发式函数是一种告知搜索方向的方法；它提供了一种明智的方法来猜测哪个邻居节点会导向一个目标。
AVL树： 1.平衡二叉搜索树——发明者G.M.Adelson-Velsky和Evgenii Landis； 2.Balance Factor（平衡因子）——是它的左子树的高度减去右子树的高度（有时相反），每个节点存balance factor = {-1，0，1}； 3.通过旋转操作来进行平衡（四种，a.左旋，b.右旋，c.左右旋，d.右左旋）。 4.不足之处是节点需要存储额外信息且调整次数频繁。
另外一种近似平衡二叉搜索树的方法叫红黑树（Red-black Tree）； 它能够确保任何一个节点的左右子树的高度差小于两倍。具体来说，红黑树是满足如下条件的二叉搜索树： 1.每个节点要么是红色，要么是黑色； 2.根节点是黑色； 3.每个叶子节点（NIL节点，空节点）是黑色的； 4.不能有相邻的两个红色节点； 5.从任何一个节点到其每个叶子的所有路径都包含相同数目的黑色节点。 关键性质是红黑树从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
AVL tree vs Red-black Tree 1.AVL trees provide faster lookups than Red Black Trees because they are more strictly balanced. 2.Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done due to relatively relaxed balancing. 3.AVL trees store balance factors or heights with each node,thus requires storage for an integer per whereas Red Black Tree requires only 1 bit of information per node. 4.Red Black Trees are used in most of the language libraries like map,multimap,multisetin C++ whereas AVL trees are used in databases where faster retrievals are required.