1.5 小结

本章介绍了各种数据结构的搜索算法，既是为了让读者学习，也是为了帮助读者更加全面地了解搜索领域。

首先，介绍了字符串搜索算法，主要详细讨论了常见的3种方法：暴力搜索算法、KMP算法和BM算法。暴力搜索算法简单易懂，但时间和空间复杂度特别高。 KMP算法引入对模式子串的预先分析，尝试重复使用模式子串中已经匹配成功的初始部分，以有效避免重新匹配。BM算法同样需要对模式子串进行预分析，它与KMP算法的一个关键区别是，它是从右到左进行字母比较，如果失配，则通过类似坏字符规则来跳过字符，避免无效回溯。

字符串搜索在搜索引擎中存在很多典型应用场景。一种是基于Grep的精确匹配，它强大精确的文本搜索能力得益于它使用了BM算法。另一种是基于字符串自动补全的模糊匹配，能够根据字符串前缀来预测用户正在输入的单词的剩余部分，其背后使用的是Trie树和基于编辑距离的字符串相似度算法。

然后，介绍了3种树搜索的结构：二叉搜索树、2-3-4树、红黑树。二叉搜索树是一种特殊类型的树，可以保证元素有序性。红黑树实际上是由2-3-4树进化而来的，如果你希望深入研究红黑树，需要注意2-3-4树的性质，以及2-3-4树与红黑树之间存在怎样的转换关系。使用红黑树的唯一原因是需要一个平衡的二叉搜索树。牢记一点：红黑树与2-3-4树之间存在着等价关系，一个2-3-4树对应多个红黑树，但一个红黑树只对应一个2-3-4树。分析红黑树平衡操作时，转化成2-3-4树模型进行等价分析将事半功倍。

最后，介绍了图搜索算法，主要讨论了如何使用深度优先搜索算法和广度优先搜索算法解决一些典型的图应用问题，比如求解图的连通分量、单源最短路径、二分图的检测、拓扑排序。图搜索算法有一个基本思路，即在使用深度优先搜索算法或者广度优先搜索算法对图进行搜索的过程中，可以记录一些辅助信息来完成对问题的求解。