学习笔记

一、Trie树 定义：树形结构，专门处理字符串匹配的数据结构，用来解决一组字符串集合中快速查找某个字符串的问题。利用字符串之间的公共前缀，将重复的前缀合并在一起。用空间换时间。时间复杂度是O(K)

实现方法： 1、在Trie树中插入字符串 2、在Trie树中查找一个字符串

应用：自动补全功能，比如搜索引擎中的关键词提示功能。不适合精确匹配查找。

二、剪枝 删去一些不重要的节点，来减小计算或搜索的复杂度

常见的剪枝方式

• 可行性剪枝：指在当前情况与题意不符时，以及可以推导出后续情况都与题意不符，那么就进行剪枝，直接把这种情况及后续情况判负，返回。即：不可行，就返回。
• 排除等效冗余：指当几个分支具有完全相同效果时，选择其中一个即可。即：都可以，选一个。
• 最优性剪枝：指在用搜索方法解决最优化问题时的一种常用剪枝。就是搜索到一半时，发现相比已经搜索到的最优解，继续搜索不到更优解，那么停止搜索，进行回溯。即：有比较，选最优。
• 顺序剪枝：普遍来说，搜索是不固定的，对于一个问题，算法可以进入搜索树的任意一个节点。假如需要搜索最小值，但非要从保存最大值的节点开始，那么可能要搜索到最后才有解；但是如果一开始从保存最小值的节点开始，那么可能立即得到解。这是顺序剪枝的一个应用。一般来说，有单调性存在的搜索问题，可以结合贪心算法，进行顺序剪枝。即：有顺序，按题意。
• 记忆化：等同于记忆化搜索，搜索的一种分支。就是记录搜索的每一种状态，当重复搜索到相同状态时，直接返回已知解。即：搜重来，直接跳。

应用：决策树，神经网络，深度优先算法，广度优先算法，A*算法，贪婪算法

三、红黑树 特征：1、是平衡二叉查找树。 2、根节点是黑色的。 3、每个椰子节点都是黑色的空节点 4、任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的 5、每个节点，从该节点达到可达叶子节点的所有路径，都包含相同数目的黑色节点

应用：用动态插入，删除，查找数据的场景，都可以用到它。