书名：搜索引擎与程序化广告:原理、设计与实战
ISBN：978-7-115-61700-2
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 杨 敏
责任编辑 胡俊英
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书从源码的角度讲解搜索技术与程序化广告系统，将技术与业务结合、理论与实践并重，帮助读者更好地理解并掌握相关知识。
本书首先从基础的数据结构出发，带领读者深入理解线性结构、树结构和图结构的搜索算法，以及它们的典型应用场景。其次详细分析全文搜索引擎工具包Lucene，包括其索引结构、分析器、搜索与排名机制，以及Lucene的底层数据结构与算法。最后，本书从搜索技术过渡到程序化广告，介绍程序化广告系统中的各个模块和工作机制，包含广告检索、广告库存预测、广告定位、广告标签模板、广告实时竞价、广告实时数据、广告事件流聚合、广告供应链透明度等内容。
本书适合从事搜索技术、搜索引擎、程序化广告相关工作或对相关内容感兴趣的软件开发人员阅读。在阅读本书之前，读者需要具备基本的编程能力。
在过去十多年里，随着广告巨头们的崛起，程序化广告技术发展成为了一套庞大的技术体系。广告的核心技术虽然总是围绕着“如何高效地搜索”展开，但适用的搜索算法和技术路线却随着不同的广告业务场景有了分化。从互联网早期的搜索广告，到后来的贴片广告、动态产品广告、信息流广告等，各种类型的程序化广告尽管思路共通，却都发展出了自己的特点。面对纷繁复杂的技术体系，刚进入在线广告领域的新人难免会不知道该从何处学起。广告技术的另一个难点在于，其中的许多设计都建立在大规模的互联网流量的基础上。由于单机实验环境流量太小，缺少实际工作经验的同学往往难以感知不同流量规模下各种技术路线的效果差异。本书恰好能够帮助读者攻克上述两个难点。
针对搜索技术，本书由浅入深，先讲解基础的搜索算法，再过渡到行业广为应用的产品级搜索引擎Lucene的底层原理，还介绍了众多辅助搜索的技术，如分词、索引、相关性计算、布尔逻辑表达式等。通过阅读本书，读者能够学习构造一个基础搜索系统的完整技术栈，并且可以从理论上对比不同的技术路线、认识不同算法之间的差异，让实践过程事半功倍。
——陈甫鸼
Microsoft Bing团队首席工程师（Principal Engineer）
作为一名写了多年“增删改查”的“业务开发者”，我在阅读本书之前从未发现程序化广告的业务如此有趣。本书不是那种让你阅读之后觉得这个技术很厉害，但是不知道有什么用的书。通过阅读本书，你不仅可以了解高级的技术技巧、实现高性能的搜索引擎内核，还可以知道这对于上层的广告业务意味着什么。
——陶文
滴滴前首席架构师
过去的二十年可以说是“计算机技术+互联网应用”井喷式发展的二十年，我们亲眼目睹了技术创新是如何改变大家的日常生活方式和习惯，以及因此带来的商业模式和价值变现的革新。在互联网世界里，搜索和广告是一个商业闭环中非常重要的组成部分，与之相关的技术也自然而然地成为互联网从业人员需要具备的重要知识。本书从专业技术从业人员的角度深入剖析了搜索和程序化广告相关的技术体系、技术细节以及典型应用场景，相信读者学习和实践完本书的内容后一定会有所收获。
——王强
FreeWheel技术副总裁（Engineering Vice President）
本书深入解析了搜索和广告领域的核心原理和技术，包括大量的数据结构、算法和开源类库。除了理论之外，本书还包含大量示例代码，可以让读者更好地理解和应用这些技术。本书深入浅出，具有很强的实用性和指导性，对于想要深入学习搜索引擎和程序化广告技术的读者来说是一本非常有价值的参考书。相信在本书的帮助下，读者可以大大提升技能水平，并将其更好地应用于工作中。
——徐宁
阿里菜鸟国际物流技术总监（P9）
市面上讲搜索引擎的书不少，讲程序化广告系统的书也不少，但将两者联系在一起且能讲清楚的书就不多了，而这两者对于设计一个良好的程序化广告引擎缺一不可。我与本书作者相识多年，他恰好在这两个领域都有多年的开发经验，更难能可贵的是，他还是一位善于总结和乐于分享的技术布道者。所以我相信，无论你是搜索或广告行业的开发人员、产品设计师，或者仅仅是想了解搜索和程序化广告的相关技术，本书都能让你有所收获。
——张晗
FreeWheel技术副总裁（Engineering Vice President）
如今，互联网已经成为我们生活中不可或缺的一部分。细数互联网时代人们获取信息的主要方式，大体上可以总结为三类：搜索、推荐和广告。搜索是根据用户的主动输入给用户返回相关性最高的结果。推荐通常不需要用户明确表达需要什么，系统会根据用户画像给用户主动推送一些信息，往往能够起到“锦上添花”的效果。广告是一个很特别的存在，形式上有点类似推荐，总是“不请自来”；而在技术上又类似搜索，需要从众多的广告中挑选相关度和收益最高的广告；商业上又要兼顾媒体、广告商和用户三方的诉求，关注用户体验和商业利益最大化。所以有人戏称，搜索、推荐和广告是互联网时代的“三驾马车”。
学界和业界也有很多人在研究这三种技术，尝试用统一的模型去实现这三种技术。由于技术和商业上的原因，统一模型现在还没有实现，但是对这三种技术的认识，却也有了一些共识：这三种技术，都遵循 “召回+排序+定制化”的三阶段。而召回的关键，就是搜索算法。
本书作者是一名“互联网老兵”，一名在程序化广告行业工作多年的资深程序员，一名程序化广告交易平台的架构师，他对搜索算法有着深刻的理解和把握。本书从最基础的字符串匹配算法出发，到程序化交易平台里广告检索、广告库存预测等内容的实战，无疑是学习搜索技术和程序化广告系统的优秀读物。
最后，在互联网企业里工作，每个人每天的工作量都是十分饱和的。在这种情况下，本书作者还能坚持技术上的追求，坚持把自己的所学、所思、所得总结出来，汇成一本书，帮助更多的同学掌握这方面的知识和技能，是非常值得钦佩的一件事情。
党政法
FreeWheel技术副总裁（Engineering Vice President）
作为世界上使用人数最多的搜索引擎之一，也是体量最大的广告商之一，谷歌的成功不在于追求广告投放的数量，而是注重广告投放的效果。程序化广告改变了传统的广告投放模式。程序化广告是指利用技术手段进行广告交易和管理。广告商可以程序化地采购媒体资源，利用算法和技术自动实现对广告目标受众的精准定位，极大地提升了广告投放的效率和效果。
工欲善其事，必先利其器。在开始学习程序化广告之前，需要先学习搜索技术，因为搜索技术是程序化广告中的核心技术之一。程序化广告系统中的很多技术源自搜索技术，比如索引、检索和数据分类与定位。信息时代，人们在数据的海洋中快速准确定位信息的需求量越来越大，对程序化广告而言也是如此。程序化广告需要根据分类的数据对目标受众进行定位，通过灵活、快速的搜索返回匹配的广告。
大多数搜索引擎的底层实现技术是相通的。简单来说，实现一个搜索引擎需要掌握的基本知识不外乎如下几个方面：
● 构建倒排索引；
● 使用TF-IDF模型创建文档权重；
● 搜索文档，比如使用常用的跳表、二叉搜索树或者红黑树进行查询，查询语句中可以包含AND、OR和NOT布尔逻辑运算符；
● 使用向量点积计算待查询内容与文档之间的相似度；
● 按相似度由高到低的顺序为用户返回搜索到的文档。
实现一个程序化广告系统所使用的很多技术和实现一个搜索引擎所使用的技术是相通的，比如：
● 构建广告活动的数据及索引；
● 检索广告活动，查询语句中可以包含AND、OR和NOT布尔逻辑运算符，充分表达广告的流量特征；
● 广告过滤与排序。
本书从基础的数据结构出发，带领读者深入理解线性结构、树结构和图结构的搜索算法，及其各自的典型应用场景。这些数据结构和算法是搜索引擎与程序化广告领域的核心技术，对于构建高效的搜索引擎和程序化广告系统至关重要。
接着，本书介绍Lucene，这是一个提供索引和搜索功能的开源库，可以作为搜索引擎的框架。本书详细分析Lucene的索引结构、分析器、搜索与排名机制，以及Lucene的底层数据结构与算法，帮助读者深入理解Lucene，为讲解程序化广告系统奠定基础。
最后，本书以与搜索技术密切相关的广告检索与定位技术作为切入点，进入程序化广告的主题，介绍程序化广告系统中的各个模块和工作机制，包含广告检索、广告库存预测、广告定位、广告标签模板、广告实时竞价、广告实时数据、广告事件流聚合、广告供应链透明度等内容，帮助读者全面掌握程序化广告技术。
本书在讲解技术内容的过程中，辅以程序源码，其中一部分来自Lucene开源代码，另一部分则是作者自己编写的代码。希望这种理论与实践结合的方式能让读者学有所得、学有所用。
本书适合所有软件开发人员阅读，尤其是从事搜索技术、搜索引擎、程序化广告相关工作或对相关内容感兴趣的开发者，包括搜索引擎工程师、程序化广告系统开发工程师、算法工程师等。本书也适合计算机相关专业的学生阅读。在阅读本书之前，读者需要具备基本的编程能力。
本书主要由三个部分组成：第1章讲解的搜索技术的算法，第2～5章讲解的Lucene搜索引擎框架，以及第7～8章讲解的程序化广告技术。读者可以根据自己的兴趣和需求单独阅读这3个部分，但更加推荐根据本书的组织方式进行阅读。
第1章，搜索技术的算法。本章介绍各种数据结构的搜索算法。首先介绍字符串搜索算法，包含暴力搜索算法、KMP算法和BM算法。然后介绍二叉搜索树，并重点研究2-3-4树与红黑树的等价关系。最后介绍图搜索算法，主要通过DFS和BFS算法讨论如何解决一些典型的实际应用问题。
第2章，Lucence基础。本章讨论Lucene搜索引擎的基础知识。首先介绍Lucene和传统关系数据库的异同，其次深入分析倒排索引和正排索引的机制，接着讨论有效负载机制，最后分析复合索引文件机制。
第3章，Lucene索引段。本章介绍Lucene索引段的相关知识。索引由多个段组成，每个段包含各自独立的文档子集。要想读懂Lucene源码，首先要充分理解文档子集的4类文件格式：tis、tii、frq和prx。 本章首先剖析索引段的合并策略与实现流程，然后讨论索引段的提交点与快照机制，最后分析索引段删除文档机制。
第4章，Lucene分析器。本章介绍Lucene的分析器机制。Lucene通过自定义分词模块来实现对输入数据的分析与存储。本章首先讨论分析器的工作流程，然后借助一个中文分词器来详细解析双数组前缀树与维特比算法的应用。
第5章，Lucene搜索与排名。本章深入分析Lucene的搜索与排名机制。首先介绍TF-IDF模型和余弦相似度，其次讨论过滤器的工作机制，接着讨论全文搜索的工作流程，包含解析查询文本并生成布尔逻辑表达式、定位分词词典索引并返回倒排列表、计算倒排列表中的文档相关度、收集器收集目标文档集合并返回，最后介绍短语搜索和模糊搜索的工作机制。
第6章，Lucene的底层数据结构与算法。本章深入分析Lucene的底层数据结构与算法，包含编码与压缩算法、跳表结构、ByteSliceReader结构和ByteBlockPool结构，以期展现Lucene的设计之美，并帮助读者更好地理解Lucene。
第7章，广告检索与定位。本章主要介绍与广告检索与定位相关的技术。首先介绍全文索引和检索模型，其次介绍位图索引及其应用，接着讲解如何用Be_indexer开源框架实现广告索引，随后对程序化广告系统进行概述，并分析广告检索与广告库存预测的关键技术——DNF算法和倒排索引，最后介绍广告定位中的常见问题——用户唯一性识别问题，即如何进行用户身份图的构建与搜索。
第8章，程序化广告技术。本章介绍程序化广告系统的相关技术，包含广告标签模板、广告实时竞价、广告实时数据，以及广告事件流聚合，并通过一个典型案例进行深入分析。最后分析广告供应链透明度问题及其解决方案，为程序化广告系统提供安全可靠的服务。
写作之难，在于把网状的思考用树状的结构体现在线性展开的语句中。由于个人能力有限，以及编写时间仓促，书中难免会出现一些错误或不准确的地方，恳请读者为我提供建议和指正，我很期待得到你最真挚的反馈。读者可以发送电子邮件到searchrtb@gmail.com与我联系。
感谢人民邮电出版社的编辑龚昕岳老师、陈冀康老师等众多工作人员的辛勤工作，使得本书的出版成为可能。
感谢我亲爱的家人，特别是我深爱的妻子阿丽，尽管她对计算机编程世界完全不了解，但正是她的理解、包容和默默支持，才能让我专心完成这本书。
感谢每一个在我成长道路上帮助过我的人。谨以此书献给众多热爱搜索技术的朋友们！
杨敏
2023年春于北京
杨敏，毕业于浙江大学计算机科学与技术专业，目前就职于一家专门提供互联网视频广告投放、预测和增值等解决方案的公司——Freewheel，担任广告供应方平台（Supply-Side Platform，SSP）的技术负责人、软件架构师。他曾在美国道富银行、Thoughtworks、微软等公司工作，拥有丰富的程序化广告产品开发与设计经验。他曾参与或主持开发过的项目有：
● 美国道富银行的普林斯顿金融系统；
● 普华永道全球派遣服务软件系统；
● 微软SharePoint平台的搜索系统；
● Freewheel的广告供应方平台Stickyads.tv。
他目前专注于Python/Java虚拟机、分布式搜索引擎Elasticsearch、MySQL内核等相关技术领域的研究。
本书提供如下资源：
● 本书源代码；
● 本书彩图文件；
● 本书思维导图；
● 异步社区7天VIP会员。
要获得以上资源，您可以扫描下方二维码，根据指引领取。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区（https://www.epubit.com/），按书名搜索，进入本书页面，单击“发表勘误”，输入勘误信息，然后单击“提交勘误”按钮即可（见右图）。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们。
如果您所在的学校、培训机构或企业想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网络上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”（www.epubit.com）是由人民邮电出版社创办的IT专业图书社区，于2015年8月上线运营，致力于优质内容的出版和分享，为读者提供高品质的学习内容，为作译者提供专业的出版服务，实现作者与读者的在线交流互动，以及传统出版与数字出版的融合发展。
“异步图书”是异步社区策划出版的精品IT图书的品牌，依托于人民邮电出版社在计算机图书领域30余年的发展与积淀。异步图书面向IT行业以及各行业使用IT的用户。
在具体讲解搜索技术之前，我们先看一个生活中与搜索相关的例子。想象一下，你是国家图书馆的管理员，你管理着几百万本书，要想从这堆书中找到一本你要的书并非易事。实际上当一个人来查找图书时，一般首先定位到某个区域，然后从区域中选择相应书架，最后从书架上找到相关的书。本质上，这个过程也对应了搜索的3个流程：索引（对图书进行编码）、排序（对图书进行排序查找）和检索（对图书进行定位）。
由此可见，恰当地应用索引、排序、检索算法可以更高效地解决搜索问题。
索引体现的是数据存储机制，存储着分词和文档的映射关系。
排序是按照特定的顺序排列和存储内容，以方便后续访问。我们在日常生活中经常运用排序思想，有些是有意识的，有些是无意识的。比如电话本和中英文字典都是按照数字或者字母顺序等方式进行排列的。在搜索技术中，排序为索引的构建进行数据预处理、实现数据分类，这有助于更好和更快地搜索。
检索提供了数据读取和分析的功能，通过对索引使用布尔逻辑运算进行查询，并根据匹配文档的相关性将结果集进行排序，将排名靠前的匹配文档集优先返回给用户。
搜索算法用于检索存储在某类数据结构（字符串、树或者图）中的信息，搜索算法可能采用顺序搜索，也可能不采用顺序搜索。如果数据集中的数据是无序的，就需要使用顺序搜索算法，否则可以使用更高效的二分搜索算法。二分搜索算法遵循分而治之的思想。
对于搜索引擎而言，当用户发起搜索时，搜索引擎使用搜索算法在其已有的内容索引中进行文档检索，然后将匹配的文档根据权重进行排序并返回。搜索引擎的意义是提供用户所搜索的内容。搜索引擎的功能越强大、返回结果越准确，用户使用搜索引擎的频率就越高。
本章介绍应用于字符串、树、图等典型数据结构的搜索算法，并通过算法过程和算法分析介绍各个算法的优缺点和具体使用场景。本章讲解的具体搜索算法如下。
● 字符串搜索：暴力搜索算法、KMP（Knuth-Morris-Pratt）算法、BM（Boyer-Moore）算法等。
● 树搜索：二叉搜索树、2-3-4树、红黑树等。
● 图搜索：广度优先搜索、深度优先搜索等。
此外，本章还讲解与搜索技术息息相关的拓扑排序算法，以及运用上述算法实现的一些应用，例如基于Grep的字符串精确搜索、基于字符串自动补全（Auto-complete）的字符串模糊搜索。
字符串搜索也称为字符串匹配问题，在计算机工程中，除了匹配给定的模式子串外，还经常需要在一个巨大的文本主串中搜索子串、前缀、后缀和子序列。字符串搜索常见的算法有暴力搜索算法、KMP算法、BM算法、前缀树算法。
字符串搜索在搜索领域是一个经典问题。这个问题在安全、模式识别与文档匹配等领域有着广泛应用，比如，搜索引擎中的字符串自动补全功能。
搜索引擎是人类最智慧的发明之一。Google创始人佩奇曾经说过：终极的搜索引擎将像人类一样聪明。当用户输入一个字符时，搜索引擎将在1ms内返回数十个候选列表。当用户输入更多的字符时，会惊讶地发现它已经输出了自己想要搜索的主题或问题。这就是字符串搜索中的模糊匹配。
模糊匹配用来处理相似但不相同的查询，是一个非常有用的技术。搜索领域中经常使用模糊匹配功能来处理单词的拼写错误。但在很多时候，精确匹配还是最常用的搜索。
字符串搜索可以简化成：在文本主串M中查找模式子串P。
相比KMP与BM算法，暴力搜索不需要预先分析模式子串。通常来说，暴力搜索是最容易设计、实现和理解的算法。这也是为什么大多数初始情况下会使用暴力搜索尝试解决问题。暴力搜索的时间与空间成本与代价都特别高。在最坏的情况下，文本主串M和模式子串P的长度分别为m和p，对文本主串中每个字符进行p次比较，意味着搜索时间复杂度是O(m×p)。
通过一个实例来分析暴力搜索过程。假设文本主串M为"AFBEAG"，模式子串P为"BEAG"，在文本主串M中搜索模式子串P的过程如下。
● M[0] != P[0]，字符不匹配，文本主串索引i加1，模式子串索引j置0，即i=1，j=0。
AFBEAG
^
BEAG● M[1] != P[0]，字符不匹配，文本主串索引i加1，模式子串索引j置0，即i=2，j=0。
AFBEAG
^
BEAG● M[2] = P[0]，字符匹配，文本主串索引i加1，模式子串索引j移动到下一个位置，即i=1，j=1。
AFBEAG
^
BEAG● M[3] = P[1]，字符匹配，文本主串索引i加1，模式子串索引j移动到下一个位置，即i=1，j=2。
AFBEAG
^
BEAG● M[4] = P[2]，字符匹配，文本主串索引i加1，模式子串索引j移动到下一个位置，即i=1，j=3。
AFBEAG
^
BEAG● M[5] = P[3]，字符匹配，文本主串索引i加1，模式子串索引j移动到下一个位置，即i=1，j=4。
AFBEAG
^
BEAG● j=len(p)，在文本主串M中匹配到模式子串P。
暴力搜索算法的基本思想是：从文本主串第一个字符开始和模式子串的第一个字符进行比较，若相等，则继续比较；否则模式子串回溯到第一个字符，重新和文本主串的第二个字符进行比较。反复如此，直到文本主串结束。
type StringSearch struct {
text string
pattern string
matchedPosition int
}
func NewStringSearch(pattern, text string) *StringSearch {
return &StringSearch{
text: text,
pattern: pattern,
matchedPosition: 0,
}
}
func (ss *StringSearch) bruteForce() bool {
n := len(ss.text)
m := len(ss.pattern)
for i := 0; i < n-m+1; i++ {
j := 0
for ; j < m; j++ {
if ss.text[i+j] != ss.pattern[j] {
break
}
}
if j == m {
ss.matchedPosition = i
return true
}
}
return false
}暴力搜索算法是所有搜索算法设计策略中最简单、直观的方法。它可以解决广泛的实际问题，比如选择排序、冒泡排序、字符串搜索、深度优先搜索和广度优先搜索等。
任何时候都不要拒绝暴力搜索算法，而是要学会构建和改进它。面对新问题，开始时一定要找到一个暴力解决问题的方法。暴力解决方案让你真正理解问题，而不需要过多思考优化的解决方案，你将清楚知道问题的输入是什么，输出是什么，避免“见木不见林”的尴尬。暴力搜索算法给了你一个起点，你可以继续应用不同的技术来优化时间和空间复杂度。
诚实地说，KMP算法是我见过最难学的算法之一，我花了不少时间才完全明白它是如何工作的。尽管它有些难度，但仍然值得你深入学习，当你掌握算法背后的思想后，你会忍不住在心里为它鼓掌。
如前所述，解决搜索问题最基本的方法是将文本主串M和模式子串P中的每个字符依次进行比较，每当出现错误匹配的时候，就将模式子串P整体向右移动一个位置，然后重复之前的比较逻辑。很明显，它的时间复杂度是O(m×p)，其中m和p分别是文本主串和模式子串的长度。有没有更好的优化算法呢？当然有。KMP算法通过预先分析模式子串，并且尝试重用模式子串初始部分中已经匹配的内容，以避免重新匹配。
分析实例之前，需要理解两个概念：前缀与后缀。前缀表示除了最后一个字符以外，一个字符串的全部头部组合；后缀表示除了第一个字符以外，一个字符串的全部尾部组合。以"BABAB"为例，对前缀和后缀的解释如下。
● "B"的前缀和后缀都为空集，共有元素的长度为0。
● "BA"的前缀为[B]，后缀为[A]，共有元素的长度为0。
● "BAB"的前缀为[B, BA]，后缀为[AB, B]，共有元素的长度为1。
● "BABA"的前缀为[B, BA, BAB]，后缀为[ABA, BA, A]，共有元素的长度为2。
● "BABAB"的前缀为[B, BA, BAB,BABA]，后缀为[ABAB, BAB, AB,B]，共有元素的长度为3。
图1-1中展示了一种情况，其中文本主串和模式子串在索引为3的位置出现了不一致。默认情况下，下一步应该将模式子串P向右移动一个位置。由于模式子串P中每个字符都是不同的，可以简单判断出模式子串P[0..2]区间（即以索引0起始，以索引2结尾的连续数组）内的字符都不可能与文本主串M当前的字母E匹配，将模式子串向右移动一个位置是徒劳的，所以需要将模式子串向右移动其自身长度减1个位置，让模式子串P的首个字符与文本主串M当前的字母E进行匹配。
图1-1
图1-2展示了另一种情况，文本主串和模式子串在索引为5的位置出现了不一致。当字母不匹配的时候，究竟要将模式子串P移动多少个位置才是合适且高效的？通过观察，模式子串前缀子串P[0,1]="DE"与模式子串后缀子串P[3,4]= "DE"是完全相同的。实际上，P[0,4]构成的子串中，存在一个前缀"DE"与后缀"DE"是完全相同的，这种情况下应该将模式子串移动到文本主串索引为3的位置继续比较。
图1-2
为了一般化地表达这个问题，假设pSub1=pSub2且pSub2=mSub3，当pSub2的下一个字符和mSub3的下一个字符不匹配时，可以移动模式子串让pSub和mSub3对齐，比较pSub1的下一个字符是否和mSub3的下一个字符匹配。图1-3展示了当文本主串与模式子串失配时，下一步应该从哪个位置开始继续进行字符的比较。这么做的好处是：文本主串的遍历索引i不用回溯，模式子串的遍历索引 j可能需要回溯，但并不一定每次都需要将索引j回溯到索引0。
现在你肯定明白了，如果可以提前找出模式子串的每个前缀，算法就可以跳过一些不必要的匹配，极大提高工作效率。这实际上也就是KMP算法背后的核心思想。
图1-3
下面说明如何寻找前后缀单元格。
如前所述，暴力搜索算法在遇到模式子串P与文本主串M不匹配的情况时，简单地将模式子串P向右移动一个位置并继续比较。KMP算法中引入了一个Next[]数组，Next[]中的值决定下一个要比较的字符的位置。
当M[i] != P[j]时，将模式子串P的失配位置j看成一个字符串的终点，若该字符串的前缀与后缀相等，即P[0..k-1] == P[j-k..j-1]，那么继续将P[k]位置的字符与M[i]位置的字符进行比较。令Next[j]=k，表示当P[j] != M[i]，即模式子串P的j位置发生失配时，模式子串的遍历索引j应该回溯到位置k。
上面的表达比较抽象，怎么直观理解Next[j]=k公式中j与k的对应关系呢？以索引j为终点（不包含索引j本身）的模式子串P[0..j-1]中，后缀与前缀的最长匹配长度是k。如图1-4所示，其中P[0..k-1] = P[j-k..j-1]。
图1-4
Next[j]=k包含如下3层含义，可结合图1-5理解。
● 当P[j] != M[i]时，模式子串的遍历索引j应该回溯到位置k。
● Next[j]的值等于P[0..i]的最长前缀的长度，也等于P[0..i]的最长后缀的长度。
● k的值等于P[0..i]的最长前缀的长度，也等于P[0..i]的最长后缀的长度。
图1-5
如图1-5所示，Next[j]=k是KMP算法的关键，其背后思想是，模式子串P在索引j-1处与文本主串M匹配，但是在索引j处失配。根据Next[j]=k，我们知道模式子串P的最长前缀（同时也是P的最长后缀）的长度为k。因此，我们已经知道：
● P[0..j-1]与M[i-j..i-1]完全匹配，P[j]与M[i]失配，即P[0..j-1]=M[i-j..i-1]；
● Next[j]=k，即P[0..k-1]与P[j-k..j-1]是完全匹配的，即P[0..k-1]=P[j-k..j-1]。
根据等式的传递性可推导出：P[0..Next[j]-1]=M[i-Next[j]..i-1]，即模式子串区间P[0..Next[j]-1]与文本主串区间M[i-Next[j]..i-1]是完全匹配的。
所以，P[j]与M[i]失配后，保持文本主串索引i不变，而模式子串索引j回溯到索引Next[j]，恢复匹配过程。
下面通过一个实例来分析Next[]数组是如何初始化的，如图1-6所示。
图1-6
● 当j=0时，模式子串P[0..j-1]=P[0..-1]是一个无效区间，因此将Next[0]设置为−1。
● 当j=1时，模式子串P[0..j-1]=P[0..0]是一个单个字母"B"，根据前后缀定义，单个字母没有前后缀，因此将Next[1]设置为0。
● 当j=2时，模式子串P[0..j-1]=P[0..1]包含两个字母"BA"，"BA"没有相同的前后缀，因此将Next[2]设置为0。
● 当j=3时，模式子串P[0..j-1]=P[0..2]包含3个字母"BAB"，"BAB"有一个相同的前后缀串，即"B"，因此将Next[3]设置为1。
● 当j=4时，模式子串P[0..j-1]=P[0..3]包含4个字母"BABA"，"BABA"有一个相同的前后缀串，即"BA"，因此将Next[4]设置为2。
● 当j=5时，模式子串P[0..j-1]=P[0..4]包含5个字母"BABAB"，"BABAB"有一个相同的前后缀串，即"BAB"，因此将Next[5]设置为3。
● 当j=6时，模式子串P[0..j-1]=P[0..5]包含6个字母"BABABB"，"BABABB"有一个相同的前后缀串，即"B"，因此将Next[6]设置为1，如图1-7所示。
图1-7
将上述分析过程转成以下代码，主要对模式子串进行预处理从而初始化next[]数组。
func (ss *StringSearch) buildNext() []int {
next := make([]int, len(ss.pattern))
next[0], next[1] = -1, 0
matchCnt := 0
for idx := 2; idx < len(ss.pattern); {
// check prefix and suffix
if ss.pattern[idx-1] == ss.pattern[matchCnt] {
matchCnt++
next[idx] = matchCnt
idx++
} else if ss.pattern[idx-1] != ss.pattern[matchCnt] && matchCnt != 0 {
matchCnt = next[matchCnt]
} else {
next[idx] = 0
idx++
}
}
return next
}我们知道，暴力搜索算法的时间复杂度是O(m×p)，其中m和p分别是文本主串和模式子串的长度。使用KMP算法在文本主串M中搜索模式子串P时，比较两个字符串，当字符比较发生失配时，模式子串中包含足够多的信息来确定下一个匹配的位置，从而减少回溯来提升字符串搜索算法的效率。KMP算法的时间复杂度是O(m+p)。因为文本主串M没有回溯，基于next[]数组信息，模式子串P也几乎没有回溯。
func (ss *StringSearch) kmp() bool {
next := ss.buildNext()
// i - current char in text; j - current char in pattern
i, j := 0, 0
for i < len(ss.text) {
if ss.text[i] != ss.pattern[j] {
if j == 0 {
i++
} else {
j = next[j]
//j = next[j - 1]
}
} else {
i++
j++
if j == len(ss.pattern) {
fmt.Printf("%s found the pattern(%s) at :%d", ss.text, ss.pattern, i-j)
ss.matchedPosition = i - j
return true
}
}
}
return false
}KMP算法虽然广为人知，但它在实践中远不如BM算法。与前面介绍的暴力搜索算法时间复杂度O(m×p)不同，KMP与BM算法只需要线性时间就能在文本主串中找到模式子串。KMP与BM算法都需要对模式子串提前进行预处理，以便在比较字符过程中跳过字符，避免无效回溯。KMP算法的预处理规则是对模式子串的每个位置计算最长前缀和最长后缀的长度。
BM算法与KMP算法的不同之处在于，它从右到左进行字符串的比较，并且使用不同的预处理规则，即坏字符规则，如图1-8所示。
图1-8
如图1-8所示，从模式子串末尾向前匹配时，如果发现某个字符失配，则称这个失配的字符为坏字符。注意，坏字符指的是文本主串中的字符，并不是模式子串中的字符。
图1-9中，当假定文本主串中的坏字符与模式子串中索引为j的字符失配时：
● 如果文本主串中的坏字符在模式子串中存在，则把坏字符在模式子串中的索引记为k；
● 如果文本主串中的坏字符在模式子串中不存在，则把坏字符在模式子串中的索引k记为−1。
那么，当文本主串M与模式子串P不匹配时，模式子串需要向左移动的距离是j−k。
图1-9
通过一个实例来分析BM算法，其中文本主串M为"ADAYZABC"，模式子串P为"ABC"。首先初始化slideTable表格，即坏字符表格，如图1-10所示。
图1-10
● 当i=0，j=2时，M[0+2]与P[2]失配，坏字符'A'在模式子串中的索引k=0。根据公式j−k，将模式子串向左移动两个位置，等价于将文本主串索引i向右移动两个位置，即文本主串下一次比较索引i=2的位置。
ADAYZABC
^
ABC● 当i=2，j=2时，M[2+2]与P[2]失配，坏字符'Z'在模式子串中的索引k=−1。根据公式j−k，将模式子串向左移动3个位置，等价于将文本主串索引i向右移动3个位置，即文本主串下一次比较索引i=5的位置。
ADAYZABC
^
ABC● 当i=5，j=2时，M[5+2] = P[2]，模式主串和模式子串中的字符'C'匹配。
ADAYZABC
^
ABC● 当i=5，j=1时，M[5+1] = P[1]，模式主串和模式子串中的字符'B'匹配。
ADAYZABC
^
ABC● 当i=5，j=0时，M[5+0] = P[0]，模式主串和模式子串中的字符'A'匹配。
ADAYZABC
^
ABC● 当j=−1时，说明在文本主串中找到了模式子串，其从文本主串的索引i=5处开始匹配。
func (ss *StringSearch) buildSlideTable() [256]int {
var st [256]int
for idx := 0; idx < 256; idx++ {
st[idx] = -1
}
for idx := 0; idx < len(ss.pattern); idx++ {
st[ss.pattern[idx]] = idx
}
return st
}回顾暴力搜索算法、KMP算法与BM算法，后两者在搜索匹配模式时，不会遍历整个搜索空间，而是基于预先分析的模式子串的信息，智能地跳过文本中一些无用的搜索空间，从而有效减少每次搜索中必须进行比较的字符数量。
func (ss *StringSearch) BM() bool {
st := ss.buildSlideTable()
textLen := len(ss.text)
patternLen := len(ss.pattern)
// Leon Bug
//for idx := 0; idx < textLen-patternLen; idx++ {
for idx := 0; idx < textLen-patternLen+1; {
j := patternLen - 1
//iterate pattern string from end to beginning
for ; j >= 0; j-- {
if ss.pattern[j] != ss.text[idx+j] {
break
}
}
if j < 0 {
fmt.Printf("found pattern")
ss.matchedPosition = idx
return true
}
//Pattern string slides backward:
idx = idx + (j - st[ss.text[idx+j]])
}
return false
}前面介绍了3种搜索算法，现在介绍搜索算法的具体应用。
Grep是一个文本搜索工具，它支持使用正则表达式搜索文件，并将匹配的行输出。Grep强大的文本搜索能力，得益于它使用的BM算法。BM算法首先查找模式子串的最后一个字符，然后使用一个查找表来告诉Grep，当发现一个失配字符时，它可以在后续匹配比较中跳过一些字符。因此，如果可以确保模式子串中最后一个字符是实际字符，而不是范围或者通配符，就可以显著加快搜索速度。
在Linux中，经常需要在一个或者多个文件中进行搜索。下面通过几个例子来介绍Linux中Find与Grep工具的基本用法。
● 使用Find在多个文件中搜索。
find ./ -type f -name '*.md'● 使用Grep显示/etc/passwd 文件中不包含字符串 "nologin" 的行。
grep -v nologin /etc/passwd● 使用Grep在当前目录中的所有文件中搜索字符串"MySQL"。
grep -rn MySQL ./● 使用Grep搜索 Nginx 日志错误文件中的多个字符串。
grep 'fatal\|error\|critical' /var/log/nginx/error.log那么Find与Grep这两个工具有什么区别呢？
Grep工具基于正则表达式从文件或者数据流中匹配数据，而Find工具根据文件的元数据来选择文件，元数据包含文件名的大小、时间和类型。简单来说，Grep用来搜索文件的内容，而Find用来搜索文件系统。对于每个匹配Find输出的文件，打开每个文件并使用 Grep 搜索模式。下面是通过管道（Pipeline）将Find与Grep工具组合使用的示例：
find /var/log/nginx/ -type f -name '*.log' | grep -E 'fatal|error|critical'当你在搜索引擎中进行搜索的时候，可能你想搜索的内容还没有输入完整，搜索引擎就猜出你想要搜索的内容了，比如，当用户输入“Google”后搜索引擎会返回如图1-11所示的候选内容列表，这就是字符串模糊搜索功能。
图1-11
实现字符串模糊搜索功能需要两项技术，一个是字符串自动补全，用于根据已有关键词查找所有相关的问题；另一个是字符串相似度，用于计算这些相关问题中哪个更可能是用户想要搜索的。
你可能会疑惑，搜索引擎自动补全的这些问题或者建议究竟来自哪里？数据是以怎样的数据结构组织的？自动补全功能是基于前缀树（Trie Tree，又称字典树、单词查找树）数据结构实现的，根据字符串前缀预测用户正在输入的单词的剩余部分。搜索引擎的自动补全功能将用户的输入作为前缀。Trie树的数据结构主要用于以检索为目标的字符串处理和存储。图1-12说明了具体情形。
图1-12
相比于普通的二叉树，Trie树中每个节点至多有26个子节点，这些子节点分别对应26个字母（a～z）。这是一种时间效率很高的数据结构，用于存储和检索字符串。比如，用户的历史查询内容以Trie树的数据结构进行组织和存储，以便搜索。然而，Trie树有一个明显的缺点，即占用大量的内存，因为每个节点都包含一个长度为26的字符数组，用来存储所有子节点，以便对Trie树进行插入、检索和删除操作。
向Trie树中插入内容时，从根节点向下遍历到叶子节点。如图1-13所示，观察"CAT"与"CAP"两个输入单词，它们有共同前缀"CA"，则该前缀只需要在Trie树中存储一次，因此极大地降低了Trie树的空间开销。而对于一些经典的数据结构，比如链表（List），它将每个单词存储在一个单独元素空间，并不会将单独元素空间关联起来。换句话说，这些单词中所有的共同前缀都被重复存储在独立的元素空间中。相比而言，Trie树的存储空间成本更低。
图1-13
对Trie树进行检索的过程是从根节点出发，对于想要检索的内容从左到右枚举每个字母，检查当前节点是否有与该字母对应的子节点。如果没有对应的子节点，则表示检索失败，返回false。如果有对应的子节点，则重复上述步骤，直到分析完想要检索的全部内容。
使用深度优先搜索（Depth First Search，DFS）遍历Trie树结构时，可以收集用户输入的字符前缀的所有字符候选集。当我们讨论在数据结构中进行数据检索的时候，通常会想到哈希表（Hash Table）。哈希表非常高效，但Trie树的数据结构还是有独特优势的。比如，哈希表需要定义哈希函数，无法避免哈希冲突。
对Trie树执行插入操作时，当前节点的后继节点对应哪个子节点指针，就应该使用Children[]数组中的哪一个位置。此处采用idx = int(chr - 'a')逻辑来计算Children[]数组对应的索引位置。
package trie
type Trie struct {
root *TrieNode
}
type TrieNode struct {
Keyword string
Children [26]*TrieNode
}
func NewTrieNode() *TrieNode {
return &TrieNode{
Keyword: "",
Children: [26]*TrieNode{},
}
}
func NewTrie() *Trie {
return &Trie{
root: NewTrieNode(),
}
}
func (t *Trie) Insert(word string) {
cur, idx := t.root, -1
for _, chr := range word {
idx = int(chr - 'a')
if cur.Children[idx] == nil {
cur.Children[idx] = NewTrieNode()
}
cur = cur.Children[idx]
}
cur.Keyword = word
}
func (t *Trie) Inserts(words ...string) {
for _, word := range words {
t.Insert(word)
}
}
func (t *Trie) Removes(words ...string) {
for _, word := range words {
t.Remove(word)
}
}
func (t *Trie) Remove(word string) {
cur, stack := t.root, make([]*TrieNode, 0, len(word))
for _, chr := range word {
stack = append(stack, cur)
cur = cur.Children[int(chr-'a')]
if cur == nil {
return
}
}
// check whether cur node is leaf or not
if !t.IsLeaf(cur) {
return
}
//iteration: from bottom to up
for idx := len(word) - 1; idx >= 0; idx-- {
cur, stack = stack[len(stack)-1], stack[:len(stack)-1]
j := int(word[idx] - 'a')
cur.Children[j] = nil //delete it
//important: trigger delete from bottom to up only when current node is becoming leaf
if !t.IsLeaf(cur) {
return
}
cur.Keyword = ""
}
}
// check whether cur node is leaf or not
func (t *Trie) IsLeaf(node *TrieNode) bool {
for _, child := range node.Children {
if child != nil {
return false
}
}
return true
}
func (t *Trie) FindWord(word string) bool {
cur := t.root
for _, chr := range word {
idx := int(chr - 'a')
cur = cur.Children[idx]
if cur == nil {
return false
}
}
if cur.Keyword != word {
return false
}
return true
}搜索引擎如何判断用户更希望输入哪个单词呢？它需要比较用户输入的单词与单词历史库中的哪个单词的编辑距离（Edit Distance，又称莱文斯坦距离，Levenshtein Distance）最小，并基于上下文来推断用户希望输入的单词。
如果要构建一个简单的拼写检查器或者进行字符串相似度判断，使用编辑距离算法就足够了。两个字符串之间的编辑距离是指将一个字符串更改为另一个字符串所最少需要的编辑单个字符的次数。编辑单个字符的次数越少，两个字符串之间的相似度就越高。所谓编辑单个字符，是指对一个字符串添加一个字母、删除一个现有字母，或用其他字母替换一个现有字母。举例如下。
kitten与sitting的编辑距离为3：
kitten -> sitten (字母s替代k)
sitten -> sittin (字母i替代e)
sittin -> sitting (末尾添加字母g)将求解的问题转换成子问题的过程称为“状态转移”，而状态转移的表达式进一步称为状态转移方程式。为了方便理解，可以将状态转移方程式理解为递归关系。
通过一个实例来分析计算编辑距离的算法过程：有两个字符串"KITTEN" 与"SITTING"，获得两个字符串之间的编辑距离。两个字符串之间的删除、替换和插入等操作次数的值可以在表或者矩阵中进行表示。
矩阵的第一行和第一列分别由两个字符串的每个字符的值填充，两个完整字符串之间的编辑距离由矩阵右下角的值表示。矩阵中第i行j列的值，即vector[i] [j]，表示将第一列中前i个字符组成的字符串转换为第一列中前j个字符组成的字符串所需要执行的操作次数。比如，将一个空字符串变成"K"需要插入一个字母"K"，所以vector[0] [1]=1；将一个空字符串变成"KI"需要插入包含两个字母的序列"KI"，所以vector[0] [2]=2；将一个空字符串变成"KITTEN"需要插入包含6个字母的序列"KITTEN"，所以vector[0] [6]=6。其他依此类推，如图1-14所示，其中dis[i] [j] 表示str1[0..i]和str2[0..j]两个字符串的最小编辑距离。
图1-14
分析dis[1] [1]的值，即"S"字符串与"K"字符串之间的编辑距离是多少？只需要将"S"经过一次替换操作变成"K"，这样两个字符串就相同了，所以dis[1] [1]=1。
分析dis[1] [2]的值，即"S"字符串与"KI"字符串之间的编辑距离是多少？只需要将"S"经过一次替换操作变成"K"并插入一个新字符"I"，这样两个字符串就相同了，所以dis[1] [2]=2。其他依此类推，如图1-15所示。
图1-15
继续分析下一行，分析dis[2] [1]的值，即"SI"字符串与"K"字符串之间的编辑距离是多少？只需要将"SI"经过一次替换操作变成"KI"，并追加一次删除操作，将其变成"K"，这样两个字符串就相同了，所以dis[2] [1]=2。
分析dis[2] [2]的值，即"SI"字符串与"KI"字符串之间的编辑距离是多少？只需要将"SI"经过一次替换操作变成"KI"，这样两个字符串就相同了，所以dis[2] [2]=1。
分析dis[2] [3]的值，即"SI"字符串与"KIT"字符串之间的编辑距离是多少？只需要将"SI"经过一次替换操作变成"KI"，并追加一次插入操作将其变成"KIT"，这样两个字符串就相同了，所以dis[2] [3]=2，如图1-16所示。
图1-16
至此，有两个关键信息需要说明。
● 当计算dis[2] [2]的值时，"SI"与"KI"字符串的末尾两个字符相同，此时dis [2] [2]的值与其左上角dis [1] [1]的值相同。
● 当计算dis[2] [3]的值时，"SI"与"KIT"字符串的末尾两个字符不相同，此时dis [2] [3]的值是周围3个值中的最小值加1，如图1-17所示。
图1-17
因为dis[i] [j] 表示str1[0..i]和str2[0..j] 两个字符串的最小编辑距离，所以dis[i] [j]的状态只与附近的3个状态dis[i] [j-1]（通过插入操作可到达dis[i] [j]）、dis[i-1] [j]（通过删除操作可到达dis[i] [j]）和dis[i-1] [j-1]（通过替换操作可到达dis[i] [j]）有直接关系。代码如下：
dis(i,j) = min(
dis(i, j-1) + 1,
//for insertion operation
dis(i-1, j) + 1,
//for deletion operation
dis(i-1, j-1) + (str1[i] == str2[j] ? 0 : 1)
//for subtitution operation
)下面展示计算编辑距离的完整算法实现。
func Distance(str1, str2 string) int {
dp := make2DArray(len(str1)+1, len(str2)+1)
for idx := 0; idx <= len(str1); idx++ {
dp[idx][0] = idx
}
for idx := 0; idx <= len(str2); idx++ {
dp[0][idx] = idx
}
for row := 1; row <= len(str1); row++ {
for column := 1; column <= len(str2); column++ {
if str1[row-1] == str2[column-1] {
dp[row][column] = dp[row-1][column-1]
} else {
dp[row][column] = min(dp[row-1][column], dp[row][column-1], dp[row-1] column-1]) + 1
}
}
}
return dp[len(str1)][len(str2)]
}
func min(values ...int) int {
if len(values) <= 0 {
return -1
}
var minVal int
minVal, values = values[0], values[1:]
for _, val := range values {
if val < minVal {
minVal = val
}
}
return minVal
}
func make2DArray(rows, columns int) [][]int {
matrix := make([][]int, rows)
for idx := range matrix {
matrix[idx] = make([]int, columns)
}
return matrix
}搜索的前提是需要存储和处理大量的对象，理想的数据结构是使用树来维护一个对象列表，以支持在对象列表中快速地插入和检索对象。
二叉搜索树是一种基础的树结构，有两个基本特点。
● 每个节点最多只有两个子节点。
● 如果左子树非空，则其左子树上所有节点的值小于根节点的值；如果右子树非空，则其右子树上所有节点的值大于根节点的值。
红黑树（Red-Black Tree）是二叉搜索树的一种进化，目的是在不影响基本操作复杂性的前提下保持树的平衡，从而提高搜索效率。它通过给每个节点着色来保持平衡，以确保常见的检索和删除操作的时间复杂度永远不会退化到O(N)。要理解红黑树，必须深入了解二叉搜索树（Binary Search Tree，BST）和2-3-4树，因为红黑树与2-3-4树之间存在着等价关系。分析红黑树平衡操作时，将其转化成2-3-4树进行等价分析将事半功倍。
使用一个简单场景来理解二叉搜索树：当你在字典中查找一个单词时，如果你使用线性搜索，那么你最终将按照顺序搜索每一个单词；如果你使用二分搜索，则是将字典翻到中间部分，然后对比目标单词与字典中间的单词，并选择继续在字典的前半部分或者后半部分搜索。
相比红黑树，二叉搜索树并不是自平衡的。根据你输入的数据顺序，你构建的二叉搜索树将产生完全不同的时间复杂度。
比如，输入数据顺序是{2,3,1}，将获得一个如图1-18所示的平衡的二叉搜索树，它的时间复杂度是O(log N)，其中N是树的节点个数。
图1-18
再比如，输入数据顺序是{1,2,3}，将获得一个如图1-19所示的类似线性链表的结构，它的时间复杂度是O(N)，其中N是链表的节点个数。
图1-19
相反，对于红黑树而言，输入数据的顺序无论是{2,3,1}还是{1,2,3}，都将获得一个如图1-20所示的平衡的红黑树。红黑树的时间复杂度会稳定在O(log N)。
图1-20
简单来说，二叉搜索树在理想情况下的时间复杂度是O(log N)，即树的高度。当在二叉搜索树中频繁执行插入与删除操作后，在极端情况下，二叉搜索树会退化成线性链表结构，时间复杂度会退化成O(N)。红黑树可以用来解决对二叉搜索树频繁执行插入与删除后出现的时间复杂度退化的问题，即红黑树可以提供稳定高效的搜索操作。
顺便提一下，相比红黑树结构，哈希表结构提供O(1)的时间复杂度，但它对内存的要求比较严格，需要事先分配足够的内存来存储它。而红黑树只需要分配存在的节点，占用的内存较小。二者还有一个显著的差别，即红黑树将数据有序存储，支持高效的小范围搜索，而哈希表结构需要遍历整个空间进行大范围搜索。
二叉搜索树是一个递归的数据结构，且对二叉搜索树进行中序遍历，可以获得一个递增的有序序列。
private class Node {
private Key key; // sorted by key
private Value val; // associated data
private Node left, right; // left and right subtrees
private int count; // number of nodes in subtree
public Node(Key key, Value val, int count) {
this.key = key;
this.val = val;
this.count = count;
}
}二叉搜索树是一种非常有用的数据结构，它包含Get、Put、Delete等基本的操作。
从根节点开始递归搜索，并返回匹配的节点。简单来说，就是将搜索节点的值与根节点的值进行比较，如果搜索节点的值小于根节点的值，则向左子树进行递归搜索，如果大于，则向右子树进行递归搜索，如果等于，则表示搜索命中，返回该值。
从根节点开始递归搜索，直到找到一个空链接，然后创建一个新的节点与空链接进行连接。如果添加键已经存在，则可以选择直接更新。
删除节点包含两个步骤：搜索和删除。搜索到目标节点后，删除这个节点。从二叉搜索树中删除一个节点时，根据节点的类型分3种情况。
Case1：待删除节点没有子节点。
如图1-21所示，待删除节点9没有子节点，可以直接删除。
图1-21
Case2：待删除节点只有一个子节点。
如图1-22所示，待删除节点13只有一个子节点，需要使被删除节点的父节点直接连接被删除节点的子节点。
图1-22
Case3：待删除节点有两个子节点。
待删除节点有两个子节点的情况会稍微复杂一些，需进行如下操作。
● 搜索待删除节点。
● 找到待删除节点的前驱节点，即待删除节点左子树的最大节点。此时的前驱节点至多包含一个子节点。
● 将待删除节点的值与其前驱节点的值进行交换。
● 删除前驱节点。如前所述，前驱节点至多包含一个子节点，删除前驱节点就简化成Case1或者Case2中的简单问题了。
上面的流程实施的是替代操作，将前驱节点与待删除节点交换后，转而删除前驱节点。本质是将复杂问题简单化。
图1-23所示为一棵不平衡的树，在最坏的情况下，它会从树退化成一个链表。搜索某个节点的时间复杂度从O(log N)退化成O(N)。相反，一个平衡的二叉搜索树可以避免最坏情况的发生，它的树高，即时间复杂度可以始终保持在对数级别。
图1-23
红黑树实际上是由2-3-4树进化而来的，如果你希望深入研究红黑树，则需要注意2-3-4树的性质，以及2-3-4树与红黑树之间存在的转换关系。
2-3-4树的性质如下。
● 树中每个节点最多包含3个元素、4个子节点。
● 树中每个节点内的值是有序的。
● 所有的叶子节点都在同一水平，确保完全平衡。
2-3-4树节点类型如下。
● 2-Node：包含1个元素、2个子节点。
● 3-Node：包含2个元素、3个子节点。
● 4-Node：包含3个元素、4个子节点。
图1-24展示了2-Node、3-Node和4-Node的结构。比如3-Node中有两个元素（A和B）和3个子节点，第一个子节点中的节点值小于A，第二个子节点中的节点值介于A与B之间，第三个子节点中的节点值大于B。
图1-24
简单来说，元素是按照顺序进行排列的，这符合二叉搜索树的性质，即所有的父节点的值大于左子节点的值，同时小于右子节点的值。
下面通过一个案例来讲解2-3-4树的构建过程。构建一个2-3-4树，其中包含数据项6、9、10、13、14、16、17、18、19、20、1，构建的过程如下。
● 依次插入数据项6、9、10。
● 插入数据项13后5-Node类型的节点需要分裂，如图1-25所示。
图1-25
● 插入数据项14、16后5-Node类型的节点需要分裂，如图1-26所示。
图1-26
● 插入数据项17、18后5-Node类型的节点需要分裂，如图1-27所示。
图1-27
● 插入数据项19、20后5-Node类型的节点需要分裂；分裂出的数据项18与父节点进行合并后需要递归分裂，如图1-28所示。
图1-28
● 插入数据项1，如图1-29所示。
图1-29
2-3-4树按中序遍历得到的序列是一个递增有序序列。想象一束光自顶向下照射2-3-4树，将在水平面上形成一个递增有序序列，如图1-30所示。
图1-30
下面通过一个案例来讲解2-3-4树的删除过程。对于图1-31中的2-3-4树，依次删除数据项1、7、6、9、3、8，过程如下。
图1-31
● Step1：删除数据项1。
在图1-31中，从根节点8开始向下遍历找到包含数据项1的节点。该节点是一个3-Node类型的节点并且是叶子节点，有两个数据项，可以直接删除，不影响平衡性质，结果如图1-32所示。
图1-32
● Step2：删除数据项7。
在图1-32中，从根节点8开始向下遍历并找到包含数据项7的节点。该节点是一个叶子节点，且是只有一个数据项的2-Node类型的节点。检查发现节点7有一个3-Node类型的兄弟节点（包含元素4和5）。
兄弟节点可以借出一个元素，但不能直接将数据项5移到节点7上，否则父节点6的右子节点会变成5，违反搜索树的性质。因此需要进行右旋操作，即首先将数据项5从兄弟节点移到父节点，然后父节点的数据项6下沉到右子节点7，最后删除数据项7。整个过程包含右旋和删除两步操作，结果如图1-33所示。
图1-33
● Step3：删除数据项6。
在图1-33中，从根节点8开始向下遍历找到包含数据项6的节点。该节点是一个叶子节点，也是只有一个数据项的2-Node类型的节点。检查发现节点6有一个2-Node类型的兄弟节点（4）。将这两个2-Node类型节点的父节点（5）下沉，形成一个新的平衡节点（4、5和6），即有3个数据项的4-Node类型节点，如图1-34所示。然后删掉包含数据项6的节点，结果如图1-35所示。
图1-34
图1-35
● Step4：删除数据项9。
在图1-35中，从根节点8开始向下遍历找到包含数据项9的节点。该节点是一个叶子节点，也是有两个数据项的3-Node类型的节点，可以直接删除，不影响平衡性质，结果如图1-36所示。
图1-36
● Step5：删除数据项3。
在图1-36中，从根节点8开始向下遍历找到包含数据项3的节点。该节点是一个内部节点，它的右子节点有两个数据项（4和5）。使用数据项3的继承项4替换3，然后从叶子节点中删除数据项4，结果如图1-37所示。此时节点4是2-Node类型节点，其兄弟节点11也是2-Node类型节点，父节点仍是2-Node类型节点。将这3个2-Node类型节点合并，结果如图1-38所示。
图1-37
图1-38
● Step6：删除数据项8。
在图1-38中，发现根节点包含待删除的数据项8。数据项8有两个子节点（5和10）且都是2-Node类型节点。将这两个子节点合并后删除数据项8，结果如图1-39所示。
图1-39
2-3-4树的优点在于能存放更多的数据项，并且树的高度能尽量低。它的缺点则是由于存在不同的节点类型，操作较为复杂。
二叉搜索树在动态更新过程中，会产生性能退化的问题。红黑树通过保持树的平衡性来避免性能退化，但它的实现逻辑相对复杂。事实上，红黑树与2-3-4树之间存在等价关系，一个2-3-4树对应多个红黑树，但一个红黑树只对应一个2-3-4树。分析红黑树平衡操作时，将其转化成2-3-4树模型进行等价分析将事半功倍。
红黑树是二叉搜索树的一种演化，它通过对每个节点引入两种颜色标记和一组约束规则，以确保树中最深的路径不超过最短路径的两倍，并保持树的平衡性。
红黑树有五大性质：
（1）每个节点要么是红色的，要么是黑色的；
（2）树的根节点必须是黑色的；
（3）不存在两个相邻的红色节点；
（4）从任意一个节点到其后代叶子节点的每条路径都有相同数量的黑色节点；
（5）树的叶子节点必须是黑色的。
相比二叉搜索树，红黑树提供了高效的插入、删除和查找接口，其时间复杂度是 O(log N)，其中N代表红黑树中节点的数量。对于倾斜的二叉树，时间复杂度最高会变成O(N)。红黑树的目的是实现黑色节点数量的平衡。
将2-3-4树转化为红黑树的规则，简单归纳有3个。
（1）2-3-4树的2-Node类型的节点包含一个数据项，转化为红黑树的节点时直接变成一个黑色的节点。
（2）2-3-4树的3-Node类型的节点包含两个数据项，转化为红黑树的节点时需要转换成父、子两个节点，上面的父节点为黑色，下面的子节点为红色。
（3）2-3-4树的4-Node类型的节点包含3个数据项，转化为红黑树的节点时需要转换成父、子3个节点，中间的数据项变成黑色的父节点，两边的数据项变成红色的子节点。
图1-40给出了3种情况的图形化示意（书中的浅色节点表示红黑树中的红色节点，读者可以从配套资源中下载彩图）。
图1-40
现在我们分析2-3-4树中的3种节点。
● 2-Node类型的节点。
如图1-41所示，显然可以直接将2-Node类型的节点映射成一个二叉搜索树的节点。
● 3-Node类型的节点。
对于3-Node类型的节点，存在两种不同的方法来进行映射。这个时候对节点引入颜色的概念：将节点分为黑色与红色。永远记住一点：父节点是黑色的，而子节点是红色的，即当你看到一个红色节点的时候，它一定与它的黑色父节点属于等价2-3-4树中的同一个节点。如图1-42所示。
图1-41
图1-42
● 4-Node类型的节点。
4-Node类型的节点的映射更加复杂，存在5种不同的方法，并同样遵循“上黑下红”的组织原则。图1-43中4-Node类型的节点被映射成完全平衡红黑树，而图1-44中4-Node类型的节点被映射成4种不平衡的红黑树，需要调整。
图1-43
图1-44
上面讨论时的思路是尝试将2-3-4树转换成二叉树，而我们知道红黑树即平衡二叉搜索树。下面通过一个例子进行详细讲解，初始2-3-4树如图1-45所示。
图1-45
● 应用规则1：节点9、10、13、14都是2-Node类型的，直接转换成黑色，如图1-46所示。
图1-46
● 应用规则2：节点1、6、16、18都是3-Node类型的，遵循“上黑下红”的转化原则。
上黑下红有两种形态：红色在左边叫作左倾（如图1-47所示），红色在右边叫作右倾（如图1-48所示）。这两种形态都是合理的，这就是为什么一个2-3-4树可以对应多个红黑树。
图1-47
图1-48
● 应用规则3：节点19、20、21是4-Node类型的，遵循“上黑两边红”的转化原则。
能够保持红黑树平衡的表示方式是唯一的。4-Node类型的节点在转化成红黑树后会形成父子两层节点，父节点是黑色的，而它的两个子节点是红色的。如前所述，红黑树中的黑色节点数量是平衡的。
在左倾基础上应用规则3后，从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点，满足红黑树的定义，如图1-49所示。
图1-49
在右倾基础上应用规则3后，从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点，同样满足红黑树的定义，如图1-50所示。
图1-50
简单推导红黑树性质4：从任意一个节点到其后代叶子节点的每条路径都有相同数量的黑色节点。如前所述，红黑树是从2-3-4树根据规则转换过来的，2-3-4树有两个特征。
● 2-3-4树的节点有3种类型：2-Node、3-Node和4-Node类型。比如，2-Node类型的节点转化成红黑树节点后是黑色的，3-Node类型的节点转化成红黑树节点后是父节点黑、子节点红，而4-Node类型的节点转化成红黑树节点后是中间父节点黑、两边子节点红。2-3-4树中任意节点转化成红黑树节点后都包含一个黑色节点。
● 从2-3-4树的根节点到叶子节点经过的路径是相同的。
所以，2-3-4树转化成红黑树后，从任意一个节点到其后代叶子节点的每条路径中都有相同数量的黑色节点。
在红黑树中不存在相邻的红色节点。将红黑树转化为2-3-4树的基本规则只有下面一条：
每当遇到红色节点时，将该红色节点向上移动与其黑色父节点进行合并，形成3-Node类型的节点或者4-Node类型的节点。
上面的规则比较抽象，因此通过一个红黑树转化为2-3-4树的例子来进行解释。如图1-51所示，从图1-51（a）到图1-51（b）的过程中，红色节点10和5分别与它们的黑色父节点20和6合并；从图1-51（b）到图1-51（c）的过程中，红色节点15、19和26、32分别与它们的黑色父节点18和30合并。
图1-51
下面介绍红黑树的操作，包含结构定义、左旋与右旋、插入节点、删除节点。
红黑树是一种自平衡的二叉树，包含两个体结构：Node（红黑树节点）和Rbtree（红黑树）。
// Node of the rbtree has a pointer of the node of parent, left, right, also has own color and Item which client uses
type Node struct {
Left *Node
Right *Node
Parent *Node
Color uint
// for use by client
Item
}
const (
// RED represents the color of the node is red
RED = 0
// BLACK represents the color of the node is black
BLACK = 1
)
// Item has a method to compare items which is less
type Item interface {
Less(than Item) bool
}
// Rbtree represents a Red-Black tree
type Rbtree struct {
NIL *Node
root *Node
count uint
}
func less(x, y Item) bool {
return x.Less(y)
}红黑树有两种类型的旋转：左旋和右旋。如图1-52所示，将这棵树的节点node左旋之后，它的右子节点right就会成为子树的新的根节点。节点right的左子节点是node，而之前right的左子节点将成为node节点的右子节点。
现在，我们对节点right进行右旋后，它将转换回原始树，如图1-53所示。
图1-52
图1-53
func (t *Rbtree) leftRotate(x *Node) {
if x.Right == t.NIL {
return
}
//
// The illation of left rotation
//
// | |
// X Y
// / \ left rotate / \
// α Y -------------> X γ
// / \ / \
// β γ α β
//
// It should be note that during the rotating we do not change the Nodes' color
//
y := x.Right
x.Right = y.Left
if y.Left != t.NIL {
y.Left.Parent = x
}
y.Parent = x.Parent
if x.Parent == t.NIL {
t.root = y
} else if x == x.Parent.Left {
x.Parent.Left = y
} else {
x.Parent.Right = y
}
y.Left = x
x.Parent = y
}向红黑树中插入节点需要保证红黑树的五大性质。
（1）每个节点要么是红色的，要么是黑色的。
（2）树的根节点必须是黑色的。
（3）不存在两个相邻的红色节点。
（4）从任意一个节点到其后代叶子节点的每条路径都有相同数量的黑色节点。
（5）树的叶子节点也必须是黑色的。
将一个节点插入红黑树中，包含两个步骤。第一步，调用insert接口添加一个节点，就像在普通的二叉搜索树中的操作一样。第二步，在插入节点后调用insertFixup接口来修复插入过程中可能引起的红黑树性质的冲突。
记住一点，新插入的节点要设置成红色节点，以满足红黑树的性质4。插入过程从根节点开始，将插入节点与根节点的值进行比较，若相等，则直接返回；若不等，则当插入节点的值小于根节点的值时，继续在根节点的左子树中查找，否则在根节点的右子树中查找。很显然，这是一个递归过程。
（1）调用insert接口。
向红黑树中插入节点的代码如下：
func (t *Rbtree) insert(z *Node) *Node {
x := t.root
y := t.NIL
for x != t.NIL {
y = x
if less(z.Item, x.Item) {
x = x.Left
} else if less(x.Item, z.Item) {
x = x.Right
} else {
return x
}
}
z.Parent = y
if y == t.NIL {
t.root = z
} else if less(z.Item, y.Item) {
y.Left = z
} else {
y.Right = z
}
t.count++
t.insertFixup(z)
return z
}插入节点的代码中用到了insertFixup函数，下面分析该函数的细节，可以分成3种情况。
Case1：向红黑树中等价于2-3-4树中的4-Node类型节点的节点下添加新节点。
2-3-4树中的4-Node类型的节点转化为红黑树时会变成一个黑色的父节点和两个红色的子节点，当向其中一个红色子节点下方插入新的节点z时，如图1-54（a）所示，违反了性质3（不存在两个相邻的红色节点）。
在这种情况下，由于新添加的节点z的叔叔节点也是红色的，所以将节点z挪到其叔叔节点之下也不能解决这个问题。如果将新添加的节点z的父亲与叔叔节点设置为黑色，则需同时将z节点的祖先节点设置为红色，如图1-54（b）所示。然而，这可能会导致祖先节点违反性质3（不存在两个相邻的红色节点）。很显然，这是一个递归的染色过程。
图1-54
Case2：向红黑树中等价于2-3-4树中的3-Node类型节点的节点下添加新节点。
2-3-4树中的3-Node类型的节点转化为红黑树时会变成一个黑色的父节点和一个红色的子节点，当向其中的红色子节点下方插入新的节点z时，如图1-55所示，违反了性质3（不存在两个相邻的红色节点）。
图1-55
在这种情况下，根据新添加的节点z与其父节点的左右关系，可以分为两种情况。
● Case2.1：z是父节点的左子节点。
● Case2.2：z是父节点的右子节点。
图1-56中，可以通过在新添加的节点z的父节点上执行左旋来将Case2.2转换成Case2.1。这样我们只需要处理Case2.1一种情况。
图1-56
对于Case2.1，首先将节点z的父节点设置为黑色，祖先节点设置为红色，然后对z的祖先节点进行右旋，如图1-57所示。
图1-57
Case3：向红黑树中等价于2-3-4树中的2-Node类型节点的节点下添加新节点。
2-3-4树中的2-Node类型的节点转化为红黑树时会变成一个黑色的节点，当向其下方插入新的节点z时，可以直接添加，不需要额外的调整操作，如图1-58所示。
图1-58
下面通过一个例子来展示如何解决Case1与Case2的递归染色问题。
● Step1：如图1-59所示，新添加的节点33与其父节点38都是红色的，需要根据Case1进行递归方案调整。
图1-59
● Step2：调整后节点40与其父节点30仍然存在相邻节点皆是红色节点的问题，违反红黑树性质3，需要递归调整。因为节点40是其父节点30的右子节点，所以需要根据Case2.2进行调整，即对节点30执行左旋。如图1-60所示。
图1-60
● Step3：节点30变成了其父节点40的左子节点，因此需要根据Case2.1进行调整，即对节点30的祖先节点（60）执行右旋。如图1-61所示。
图1-61
（2）调用insertFixup接口。
调用insertFixup接口来修复插入过程中可能引起的红黑树性质的冲突。
func (t *Rbtree) insertFixup(z *Node) {
for z.Parent.Color == RED {
//
// However, we do not need the assertion of non-nil grandparent
// because the root is black
//
//
//
// Since the color of the parent is RED, so the parent is not root
// and the grandparent must be exist
//
if z.Parent == z.Parent.Parent.Left {
// Take y as the uncle, although it can be NIL, in that case
// its color is BLACK
y := z.Parent.Parent.Right
if y.Color == RED {
//
// Case 1:
// Parent and uncle are both RED, the grandparent must be BLACK
// due to
//
// 4) Both children of every red node are black
//
// Since the current node and its parent are all RED, we still
// in violation of 4), So repaint both the parent and the uncle
// to BLACK and grandparent to RED(to maintain 5)
//
// 5) Every simple path from root to leaves contains the same
// number of black nodes
//
z.Parent.Color = BLACK
y.Color = BLACK
z.Parent.Parent.Color = RED
z = z.Parent.Parent
} else {
if z == z.Parent.Right {
//
// Case 2:
// Parent is RED and uncle is BLACK and the current node
// is right child
//
// A left rotation on the parent of the current node will
// switch the roles of each other. This still leaves us in
// violation of 4)
// The continuation into Case 3 will fix that
//
z = z.Parent
t.leftRotate(z)
}
//
// Case 3:
// Parent is RED and uncle is BLACK and the current node is
// left child
//
// At the very beginning of Case3, current node and parent are
// both RED, thus we violate 4)
// Repaint parent to BLACK will fix it, but 5) does not allow
// this because all paths that go through the parent will get
// 1 more black node. Then repaint grandparent to RED (as we
// discussed before, the grandparent is BLACK) and do a right
// rotation will fix that
//
z.Parent.Color = BLACK
z.Parent.Parent.Color = RED
t.rightRotate(z.Parent.Parent)
}
} else { // same as then clause with "right" and "left" exchanged
y := z.Parent.Parent.Left
if y.Color == RED {
z.Parent.Color = BLACK
y.Color = BLACK
z.Parent.Parent.Color = RED
z = z.Parent.Parent
} else {
if z == z.Parent.Left {
z = z.Parent
t.rightRotate(z)
}
z.Parent.Color = BLACK
z.Parent.Parent.Color = RED
t.leftRotate(z.Parent.Parent)
}
}
}
t.root.Color = BLACK
}因为红黑树是一种特殊的二叉搜索树，因此删除红黑树中的节点和删除二叉搜索树中的节点类似，包含3种情况。
● Case1：待删除节点没有子节点。
● Case2：待删除节点只有一个子节点。
● Case3：待删除节点有两个子节点。
前两种情况的处理方法比较简单。对于Case1，删除没有子节点的节点，只需要简单地从树中删除该节点。对于Case2，删除带有一个子节点的节点，只需要在删除该节点的同时让其子节点代替其。
Case3稍微复杂一些，包含如下步骤。
● 搜索待删除节点。
● 找到待删除节点的后继节点，即待删除节点右子树的最小节点。此时的后继节点至多包含一个子节点。
● 将待删除节点的值与其后继节点的值进行交换。
● 删除后继节点。如前所述，后继节点至多包含一个子节点，删除后继节点后就变成Case1或者Case2的简单问题了。
红黑树的删除节点最终会转换成删除叶子节点（最底下一层），或者删除只有一个子节点的非叶子节点（倒数两层）这两种情况。而红黑树的最底下两层皆对应2-3-4树的叶子节点。
换句话说，删除红黑树中的节点分成3种情况，通过转换可以将Case3转换成Case1和Case2的基本情况，而Case1与Case2的操作等价于删除2-3-4树中的叶子节点。
删除操作涉及删除（delete）、寻找后继（successor）和颜色修正（deleteFixup）。
（1）删除
删除流程遵循先搜索后删除的逻辑，在分布式系统中更是如此。与向红黑树中添加节点相似，删除节点需经历两个步骤：先删除，后调整颜色。删除过程中需要用到t.search函数，这个函数从根节点开始进行递归搜索，类似二分搜索算法。
func (t *Rbtree) delete(key *Node) *Node {
z := t.search(key)
if z == t.NIL {
return t.NIL
}
ret := &Node{t.NIL, t.NIL, t.NIL, z.Color, z.Item}
var y *Node
var x *Node
if z.Left == t.NIL || z.Right == t.NIL {
y = z
} else {
y = t.successor(z)
}
if y.Left != t.NIL {
x = y.Left
} else {
x = y.Right
}
// Even if x is NIL, we do the assign. In that case all the NIL nodes will
// change from {nil, nil, nil, BLACK, nil} to {nil, nil, ADDR, BLACK, nil},
// but do not worry about that because it will not affect the compare
// between Node-X with Node-NIL
x.Parent = y.Parent
if y.Parent == t.NIL {
t.root = x
} else if y == y.Parent.Left {
y.Parent.Left = x
} else {
y.Parent.Right = x
}
if y != z {
z.Item = y.Item
}
if y.Color == BLACK {
t.deleteFixup(x)
}
t.count--
return ret
}删除后，需要调整平衡，但只有当删除的节点是黑色节点时才需要调整平衡，因为红黑树是基于黑色节点的数量平衡的。当完成节点删除后，我们继续研究deleteFixup函数的细节。
红黑树转换成等价的2-3-4树的规则为，任何时候遇到红色节点都将它向上移动与黑色父节点合并成3-Node或者4-Node类型的节点。1.3.4小节中讲解的将一个红黑树转化为2-3-4树的例子如图1-62所示。
图1-62
如前所述，红黑树的删除最终会转换成删除叶子节点（最底下一层），或者删除只有一个孩子的非叶子节点（倒数第二层）这两种情况。本质上删除红黑树可以转化为删除与红黑树等价的2-3-4树的叶子节点。很显然，2-3-4树的叶子节点只有3种情况：2-Node、3-Node和4-Node类型的节点。
Case1：删除红黑树中等价于2-3-4树中4-Node类型节点的数据项（不用向兄弟节点借）。
图1-63中，删除4-Node类型节点中的数据项的操作是安全的，分析如下。
● 如果删除4-Node类型的节点（15、18、19）中的数据项15，删除的是红色节点，没有破坏红黑树的性质，可以安全地删除红色数据节点15。
● 如果删除4-Node类型的节点（15、18、19）中的数据项19，删除的是红色节点，没有破坏红黑树的性质，可以安全地删除红色数据节点19。
● 如果删除4-Node类型的节点（15、18、19）中的数据项18，删除的是黑色节点，也可以安全地删除，只需要从同级的两个红色数据项中随机选择一个从红色修改成黑色并结合旋转操作即可。
图1-63
Case2：删除红黑树中等价于2-3-4树中3-Node类型节点的数据项（不用向兄弟节点借）。
图1-63中，删除3-Node类型节点中的数据项的操作也是安全的，分析如下。
● 如果删除3-Node类型的节点（5、6）中的数据项5，删除的是红色节点，没有破坏红黑树的性质，可以安全地删除红色数据节点5。
● 如果删除3-Node类型的节点（5、6）中的数据项6，删除的是黑色节点，也可以安全地删除，只需要将同级的红色数据项5从红色变成黑色就能继续保持性质。
Case3：删除红黑树中等价于2-3-4树中2-Node类型节点的数据项（需要向兄弟节点借）。
图1-64中，删除2-Node类型的节点（6）会导致黑色节点的数量不平衡而失去安全性。应该怎么处理？
图1-64
是不是可以直接向3-Node类型的兄弟节点（15、18）借一个数据项呢？答案是不能直接从兄弟节点借数据项，这将导致数据无序，如图1-65所示。
图1-65
Case3.1：待删除节点是2-Node类型的，兄弟节点是4-Node类型的，可以借一个节点给待删除节点。
如图1-66所示，调整策略是将father与brother交换颜色，然后对father执行左旋。
图1-66
Case3.2：待删除节点是2-Node类型的，兄弟节点是3-Node类型的，可以借一个节点给待删除节点。
删除2-Node类型的节点（6）后，需要向兄弟节点借一个数据项，但不是直接借而是间接借，需要通过左旋操作由父节点来借一个数据项，从而保持树中各节点的数据项的有序性。比如，图1-67中，删除节点6，并间接向兄弟节点借15，即父节点10下沉，兄弟节点15上移至父节点。
图1-67
● Case3.2.1：待删除节点是2-Node类型的，其兄弟节点brother是3-Node类型的（可以借数据项），并且brother有一个与其方向一致的红色节点son。
与brother方向一致，是指brother为father的左子节点，son节点也是brother的左子节点；或者brother为father的右子节点，son节点也是brother的右子节点。调整策略就是对father实施左旋，保持红黑树的平衡性质，如图1-68所示。
图1-68
● Case3.2.2：待删除节点是2-Node类型的，其兄弟节点brother是3-Node类型的（可以借数据项），并且brother有一个与其方向不一致的红色节点son。
调整策略分两步。第一步如图1-69所示，对brother执行右旋，此时红黑树中father、son、brother 3个节点在一个方向上，问题就简化成了Case3.2.1。第二步是遵循Case3.2.1规则对father执行左旋。
图1-69
Case3.3：待删除节点是2-Node类型的，兄弟节点也是2-Node类型的，不可以借一个节点给待删除节点。
如图1-70所示，删除2-Node类型的节点（10）后，需要向兄弟节点借一个数据项，兄弟节点（18）本身也是2-Node类型的，所以无法借出。
图1-70
● Case3.3.1：待删除节点是2-Node类型的，兄弟节点本身也是2-Node类型的（不能借数据项），并且待删除节点的父节点father是红色的。
调整策略特别简单：只需要将待删除节点与brother节点从黑色修改成红色，同时将父节点father从红色修改成黑色，就可以完成调整工作，如图1-71所示。
图1-71
● Case3.3.2：待删除节点是2-Node类型的，兄弟节点本身也是2-Node类型的（不能借数据项），并且待删除节点的父节点是黑色的。
如图1-72所示，调整策略是将待删除节点与brother节点同时从黑色调整成红色。由于father节点已经是黑色的了，接下来的问题就转移到了对father、father的father以及father的brother3个节点的关系判断，这是一个完全相似的子问题（即father为节点的子树中黑色节点数量减1，如何平衡？），通过不断地向上递归来解决。如果一直是这种情况，最终会转化为root的层面。
图1-72
（2）寻找后继
如果一个节点有右子树，那么它的后继节点就是其右子树下值最小的节点。如果一个节点没有右子树，则需要向上查找当前节点是哪个节点的左子节点。
func (t *Rbtree) successor(x *Node) *Node {
if x == t.NIL {
return t.NIL
}
if x.Right != t.NIL {
return t.min(x.Right)
}
y := x.Parent
for y != t.NIL && x == y.Right {
x = y
y = y.Parent
}
return y
}
func (t *Rbtree) min(x *Node) *Node {
if x == t.NIL {
return t.NIL
}
for x.Left != t.NIL {
x = x.Left
}
return x
}（3）颜色修正
对红黑树进行颜色修正时，需要将红黑树还原成2-3-4树。每当遇到红色节点时，将它向上移动与黑色父节点进行合并，构成3-Node或者4-Node类型的节点。
func (t *Rbtree) deleteFixup(x *Node) {
for x != t.root && x.Color == BLACK {
if x == x.Parent.Left {
w := x.Parent.Right
if w.Color == RED {
w.Color = BLACK
x.Parent.Color = RED
t.leftRotate(x.Parent)
w = x.Parent.Right
}
if w.Left.Color == BLACK && w.Right.Color == BLACK {
w.Color = RED
x = x.Parent
} else {
if w.Right.Color == BLACK {
w.Left.Color = BLACK
w.Color = RED
t.rightRotate(w)
w = x.Parent.Right
}
w.Color = x.Parent.Color
x.Parent.Color = BLACK
w.Right.Color = BLACK
t.leftRotate(x.Parent)
// this is to exit while loop
x = t.root
}
} else { // the code below is has left and right switched from above
w := x.Parent.Left
if w.Color == RED {
w.Color = BLACK
x.Parent.Color = RED
t.rightRotate(x.Parent)
w = x.Parent.Left
}
if w.Left.Color == BLACK && w.Right.Color == BLACK {
w.Color = RED
x = x.Parent
} else {
if w.Left.Color == BLACK {
w.Right.Color = BLACK
w.Color = RED
t.leftRotate(w)
w = x.Parent.Left
}
w.Color = x.Parent.Color
x.Parent.Color = BLACK
w.Left.Color = BLACK
t.rightRotate(x.Parent)
x = t.root
}
}
}
x.Color = BLACK
}在Linux系统中，每个进程有4GB的虚拟内存空间，该空间包含多个虚拟内存区域（Virtual Memory Area，VMA），比如代码段，数据段、Heap段、Stack段。每个VMA都代表一个连续的虚拟地址空间，并且这个空间具有相同的内存属性，比如读写权限。从进程角度分析，虽然一个VMA的虚拟地址是连续的，但它映射的物理内存空间区域可能并不连续。当进程需要申请新的物理空间时，首先需要申请分配虚拟地址空间。
对于Linux内核中频繁的内存操作，需要追求极致的效率。因此Linux的进程内所有VMA通过红黑树进行管理，允许内核高效遍历进程地址空间中的所有VMA。
图数据结构非常强大，是目前应用最广泛的数据结构之一，几乎任何事物都可以用图进行建模表示，比如道路网络、计算机网络、社交网络、用户身份解析图。
事实上，计算机的文件系统和互联网本身都是以图为模型构建的。可以将互联网根据不同的应用场景表示为不同的图，比如，用户通过互联网连接彼此；用户在社交网络（例如微信）互相发送实时消息，互相关注对方并加为好友。
广度优先搜索（Breadth First Search，BFS）和深度优先搜索（Depth First Search，DFS）代表对图进行遍历（即搜索）的算法。程序化广告中用户身份图通过链接不同来源的数据来创建用户标识，广告商利用用户身份图进行目标受众定位并提供个性化广告。如果说用户身份图中的节点代表着某个用户，那么BFS和DFS算法可以用来识别节点之间的关系。
本节涉及许多图论算法，包括DFS在树与图结构搜索算法中的异同、无向图连通分量、最短路径、环检测、二分图检测、染色问题、拓扑排序等。
图存在两种表达方式——邻接矩阵与邻接表，它们用于记录图中任意两个节点之间的连通关系。邻接矩阵使用二维数组进行存储，而邻接表采用链表方式实现，具体来说图中每个节点都有一个独立链表，使用链表来存储当前节点关联的所有邻接节点以及权值。究竟怎么选择？下面分析两个场景。
假设一个图有3000个节点，有2999条边。图中节点的“度”是指与该节点相关联的边的数量。
场景1：存储空间分析。
● 使用邻接表需要3000 + 2999 = 5999 个数据节点来表达这个图。
● 使用邻接矩阵需要3000 × 3000 = 900万个数据节点来表达这个图。
结论：使用邻接矩阵占用的资源约为使用邻接表所占用的资源的1500倍。具体来说，如果原本邻接表只需要1KB的信息来存储图信息，那么对应的邻接矩阵则需要约1.5MB；如果本来邻接表需要使用1MB存储信息，那么对应的邻接矩阵则需要约1.5GB。
两种数据结构的存储空间差距是如此之大！1500倍的差距意味着，原本单机可以处理的场景，现在需要分布式处理。
场景2：求一个节点的相邻节点。
● 使用邻接表，此节点的“度”就说明需要遍历的时间复杂度。
● 使用邻接矩阵，不管当前节点的“度”是多少，我们都需要通过矩阵的对应行来遍历判断图中所有节点是否与当前节点相邻。其时间复杂度是O(V)。
接下来讨论稀疏图和稠密图的概念，边的多少是二者本质上的差异。如图1-73所示，稠密图是指边数接近于最大边数的图。如图1-74所示，稀疏图是一种边数接近于最小边数的图。
图1-73
图1-74
图1-75中，左图是稀疏图，尽管它的节点特别多，但是每个节点的度为5或6；右图是稠密图，尽管它的节点数看起来特别少，但是每个节点都与其他所有节点相连并形成了边，最终使得整个图的边数非常多。
图1-75
假设一个图有3000个节点，使用邻接表来存储。下面分析两个场景。
场景1：稀疏图
对于这3000个节点，如果每个节点的度都是3，则意味着有(3000×3)/2=4500条边。
场景2：稠密图
对于这3000个节点，如果每个节点的度都是2999，则意味着有(3000×2999)/2≈450万条边。
结论很明显：对于同样拥有3000个节点的稀疏图和稠密图，如果节点的度分别是3和2999，则二者存储的边的比例相差约1000倍。如果应用场景是一个稀疏图，采用邻接矩阵存储的成本以及时间复杂度都比邻接表要高。
图1-76所示为北京城市轨道交通线网图，看似特别复杂，但是图中每个节点（地铁站）都只与其附近的2～3个节点相连接，也就是说城市轨道交通线网图中节点的“度”并不大，其本质还是一个稀疏图，用邻接表来建模足够了。
图1-76
对生活中的问题进行建模得到的大多是稀疏图，因此建议使用邻接表数据结构来存储数据。
为了方便理解本小节内容，先想象一棵向下生长的树，树根在上，叶子在下。
树的深度优先搜索（又称Tree-DFS）意味着遍历从树根开始，在某个方向上尽可能地深入搜索，直到遇到叶子节点，然后回溯到上一层次，进入另一个方向深入搜索。Tree-DFS遍历的主要方向是垂直的。
与之相对，树的广度优先搜索（又称Tree-BFS）意味着遍历从树根开始，然后访问根节点的所有子节点，接着访问孙子节点，以此类推。对于每个深度，搜索所有的兄弟节点。
图结构中可能存在环，因此图的深度优先搜索（又称Graph-DFS）中遍历到一个节点时，需要查看这个节点是否已经被遍历过。为了确定每一个节点是否被遍历过，需要为每个节点创建一个visited[]标记。当遍历一个节点后，需要标记当前节点为已访问状态。
Tree-DFS使用递归遍历中的前序遍历。算法流程分为两步：第一步是遍历当前节点；第二步是递归遍历并访问所有的子树。
type TreeNode struct {
value string
left *TreeNode
right *TreeNode
}
func insert(n *TreeNode, v string) *TreeNode {
if n == nil {
return &TreeNode{v, nil, nil}
} else if v <= n.value {
n.left = insert(n.left, v)
} else {
n.right = insert(n.right, v)
}
return n
}
func preorder(n *TreeNode) {
if n != nil {
fmt.Printf(n.value + " ") //遍历
preorder(n.left) //访问子树
preorder(n.right) //访问子树
}
}Graph-DFS与Tree-DFS在逻辑结构上是完全一致的。对于图数据结构来说，没有3-Node这样的节点类型，而是通常使用一个数字序号来表达一个节点，其中每一个节点与其他节点的相邻关系可以用邻接表或者邻接矩阵来存储。
type Graph struct {
adj map[string][]string
}
func (g *Graph) DFS(start string) {
visited := g.createVisited()
g.dfs(start, visited)
}
func (g *Graph) dfs(start string, visited map[string]bool) {
visited[start] = true
fmt.Println("DFS", start) //遍历
for _, node := range g.adj[start] {
if !visited[node] {
g.dfs(node, visited) //访问子树
}
}
}对于树结构和图结构的深度优先搜索，通过抽象它们的底层逻辑，发现二者的本质是相同的。对比树的深度优先搜索和图的深度优先搜索逻辑如下。
● 第一步：对于树来说是遍历当前节点；对于图来说是从某个节点V开始进行遍历。
● 第二步：对于树来说是遍历所有子树，先遍历左子树，然后遍历右子树，由于树中每个节点至多只有左子节点和右子节点，所以只需要递归遍历左右子树就完成了递归遍历所有子树；对于图来说也是遍历所有子节点，但与当前节点V相邻的节点可能不止两个，而是多个。因此，需要通过for循环和邻接表来找出与当前节点V相邻的所有图节点。需要注意的是，递归遍历相邻节点前需要判断相邻节点是否已被访问过，即visited[V]。
❏ 在树中进行深度优先搜索，不需要判断当前节点是否被访问过。树中没有环，一个节点只可能被遍历访问一次，没有第二次被访问的机会。
❏ 图数据结构中可能存在环，一个节点可能会从多个遍历路径被访问，需要引入visited[]数组来保证图递归遍历过程中每个节点有且只有一次机会被访问。所以，在递归函数访问某个节点时，需要将当前正在访问的图节点V对应的visited[V]进行置位操作，即visited[V]=true。这样在后续的递归调用中，如果再次遇到节点V，就不会遍历节点V。
树中通过if node != nil来判断递归遍历终止条件；图的深度优先搜索从表面上看没有终止条件，实际上隐含在代码中。那么，图的递归遍历终止条件是什么呢？有两种情况。
● 当前节点V没有相邻的节点。
● 当前节点V的相邻节点都已经被访问过了。
这两种情况下都不需要继续递归下去，当前层递归可以返回到上一层递归。换句话说，上面两层逻辑都已经定义在for循环与if(visited[V])的判断逻辑当中。比如，若当前节点V没有相邻节点，此时for循环根本不会执行；若当前节点V的所有相邻节点已经被访问过，此时进入for循环后无法通过if(visited[V])的逻辑判断。因此，在这两种情况下都不会触发DFS递归遍历。
实际上，树的深度优先搜索与图的深度优先搜索的底层逻辑框架是相通的。图1-77给出了对此情况的概述。
图1-77
在图的深度优先搜索过程中，每个节点以及每条边都会被访问一次，所以时间复杂度是O(v + e)，其中v表示节点数，e表示边数。如果考察的图是连通图，时间复杂度可以写成O(e)。如果图中所有节点之间不相连，时间复杂度可以写成O(v)。
深度优先搜索在图搜索中的典型应用场景举例如下：
● 检测一张图是否整体连通，即求解图的连通分量；
● 二分图的检测；
● 寻找图中的桥与割点；
● 哈密顿路径；
● 拓扑排序。
很多场景下我们会对无向图的连通分量感兴趣，比如在一个城市公路图模型中，每个节点代表一个城市，每条边代表城市之间的道路。求解公路系统图的连通分量，相当于求解公路系统中有多少独立的区域。我们可以据此计算最多可以关闭多少道路或者十字路口，但仍保持其他的街道网络是紧密连通的。
类似地，图1-78表示一个社交网络，其中每个节点代表每个人，节点之间相通的边代表这两个人是相识的，那么求解社交网络图的连通分量，相当于求解社交网络中有多少个独立的团体。
假如从节点A开始遍历，只会对与节点A直接或间接相邻的所有节点进行遍历，与此同时会把这些节点在对应的visited[]数组中标记为true。
图1-78
一旦节点A退出了当前的深度优先搜索递归调用，可以通过for循环继续寻找下一个没有被访问的节点，此节点肯定是另一个连通分量的一部分，对应图1-78中就是节点H。代码中for循环会找到节点H并继续进行深度优先搜索调用，此时找到了一个新的连通分量，将connectedComCnt变量进行自增操作。
type Graph struct {
adj map[string][]string
results []string
connectedComCnt int
}
func NewGraph() Graph {
return Graph{
adj: make(map[string][]string),
results: make([]string, 0),
connectedComCnt: 0,
}
}
func (g *Graph) DFS() {
visited := g.newVisited()
for key := range g.adj {
if visited[key] == false {
g.dfs(key, visited)
g.connectedComCnt++
}
}
fmt.Println("connected component count:", g.connectedComCnt)
}
func (g *Graph) dfs(start string, visited map[string]bool) {
visited[start] = true
fmt.Println("DFS", start)
g.results = append(g.results, start)
for _, node := range g.adj[start] {
if !visited[node] {
g.dfs(node, visited)
}
}
}如果想进一步求解每个连通分量具体包含哪些节点，应该怎么做？有两个思路：思路一是向深度优先搜索递归函数中引入List[i]容器，将一组连通分量中的所有节点全部放入这个List[i]容器中；思路二是将boolean[] visited 重构成 int[] visited。
● 连通分量中的节点被遍历后，visited[]数组会从全为0变成全为1。
● visited[]数组的元素类型是布尔类型，所以它只能传递一个信息，即visited[i]代表节点i是否已经被访问过。如果我们换一个思路，将boolean visited[]数组扩展成 int visited[]，则可以让 visited[]数组承载更多的信息。
func (g *Graph) newVisited() map[string]bool {
visited := make(map[string]bool, len(g.adj))
for key := range g.adj {
visited[key] = false
}
return visited
}我们将visited[]定义成整型，将数组中每个元素的值初始化为−1。在遍历 过程中会将visited[]设置成非负值。非负值有很多可以选择，不同的非负值代表不同的连通分量。
● for V := 0; V < len(v); V++ { dfs(v) }
● 第一次遍历dfs(0)的时候，将所有与节点0相连通的节点对应的visited[]统一赋值为0，表示所有值为0的visited[]节点属于同一个连通分量，可以将0看成连通分量的ID。
● 之后，for循环继续，它会找到未访问的节点H，从节点H出发再次按照深度优先搜索算法来递归遍历图，将所有与节点H相连通的节点对应的visited[]值设置为1。
● 利用visited[]数组，既完成了图的深度优先搜索过程中节点是否被访问过的逻辑判断，也实现了对图中属于不同连通分量的节点集的划分。visited[]中不同的值用来说明不同节点分别所属的连通图ID，如下所示。
connected component count: 2
connected components: map [A:0 B:0 C:0 D:0 E:0 F:0 G:0 H:1 I:1 J:1]func (g *Graph) DFS() {
visited := g.newVisited()
for key := range g.adj {
if visited[key] == -1 {
g.dfs(key, g.connectedComCnt, visited)
g.connectedComCnt++
}
}
fmt.Println("connected component count:", g.connectedComCnt)
fmt.Println("connected components:", visited)
}
func (g *Graph) dfs(start string, ccID int, visited map[string]int) {
visited[start] = ccID
fmt.Println("DFS", start)
g.results = append(g.results, start)
for _, node := range g.adj[start] {
if visited[node] == -1 {
g.dfs(node, ccID, visited)
}
}
}
func (g *Graph) newVisited() map[string]int {
visited := make(map[string]int, len(g.adj))
for key := range g.adj {
visited[key] = -1
}
return visited
}单源路径问题求解的是从一个节点到另一个节点之间是否存在路径。图论问题中解决问题的一个基本思路是，在图的深度优先搜索过程中，可以辅助地记录一些信息来帮助我们完成对问题的求解。以图1-79为例。
图1-79
模拟单源路径算法的过程如下。
● 从节点A开始深度优先遍历它的相邻节点。先找到邻接点B。
● 遍历到节点B的时候，因为节点B是从节点A走来的，所以记录下B<-A这个信息。
● 继续从节点B开始进行深度优先遍历，找到它有A、D、E这3个相邻节点，因为节点A已经遍历过了，所以选择节点D。
● 遍历到节点D的时候，因为节点D是从节点B走来的，所以记录下D<-B这个信息。
● 继续从节点D开始进行深度优先遍历，找到它有B、C这两个相邻节点。因为节点B已经遍历过了，所以选择节点C。
● 遍历到节点C的时候，因为节点C是从节点D走来的，所以记录下C<-D这个信息。
● 继续从节点C开始进行深度优先遍历，找到它有A、G这两个相邻节点。因为节点A已经遍历过了，所以选择节点G。
● 遍历到节点G的时候，因为节点G是从节点C走来的，所以记录下G<-C这个信息。
● 继续从节点D开始进行深度优先遍历，找到它有C、F这两个相邻节点。因为节点C已经遍历过了，所以选择节点F。
● 遍历到节点F的时候，因为节点F是从节点G走来的，所以记录下F<-G这个信息。
● 继续从节点F开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点G。
● 继续从节点G开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点C。
● 继续从节点C开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点D。
● 继续从节点D开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点B。
● 继续从节点B开始进行深度优先遍历，找到它有A、D、E这3个相邻节点。因为节点A和D已经遍历过了，所以选择节点E。
● 遍历到节点E的时候，因为节点E是从节点B走来的，所以记录下E<-B这个信息。
● 继续从节点E开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点B。
● 继续从节点B开始进行深度优先遍历，所有相邻节点已经标记为访问，所以返回到上一层节点A。
● 继续从节点A开始进行深度优先遍历，所有相邻节点已经标记为访问，所以当前的连通分量遍历完毕，得到如下信息。
B <- A
D <- B
C <- D
G <- C
F <- G
E <- B● 当前连通分量的每个节点我们都记录下来了。使用previous[]数组记录当前节点是从哪一个节点走来的。接下来，如果想找到节点A到节点G的路径，可以从目标节点通过previous[]数组进行反向推导，一直找到源节点。具体步骤如下。
❏ 查询previous[]数组，询问节点G是从哪儿来的？得到previous[G] =C。
❏ 查询previous[]数组，询问节点C是从哪儿来的？得到previous[C] =D。
❏ 查询previous[]数组，询问节点D是从哪儿来的？得到previous[D] =B。
❏ 查询previous[]数组，询问节点B是从哪儿来的？得到previous[B] =A，其中，A即我们查询的源节点。
● 因此，找到一条从节点A到节点G的路径，即A -> B -> D -> C -> G。
结论：求解路径问题还是使用图的深度优先搜索算法作为框架，只是在做深度优先搜索的同时引入了previous[]数组来记录一些信息，以帮助我们完成对路径问题的求解。
新的问题：如何求解节点E到节点B的路径？
● 上面的方法是无法求解节点E到节点B的路径的，因为目前previous[]记录的所有信息都是从节点A出发进行深度优先搜索过程中记录并存储的信息。
● 比如，我们使用目前记录的信息查找从节点E到节点B经历的路径。
❏ 查询previous []数组，询问节点E是从哪来儿的？得到previous [E] = B。
❏ 查询previous []数组，询问节点B是从哪来儿的？得到previous [B] = A。
❏ 查询previous []数组，询问节点A是从哪儿来的？得到previous [A]的值是什么？然而previous [A]是没有值的，原因在于深度优先搜索算法的初始节点是A。
● 结论：我们无法基于现有的previous []数组信息找到从节点E到节点B是否存在路径。
● 如果希望求解出从节点E到节点B是否存在路径，那么整个深度优先搜索算法需要从节点E开始重新执行，并在执行过程中记录新的previous []数组信息。
当前算法可以求解从某个节点出发到图中剩余任意节点的路径问题，但是起始节点是固定的，因此该算法被命名为“单源路径算法”。
func (g *Graph) SingleSourcePathDFS(src, dst string) {
visited := g.newVisited()
g.previous = make(map[string]string)
isConnected := g.dfs(src, dst, src, visited)
results := make([]string, 0)
if isConnected {
results = append(results, dst)
parent := g.previous[dst]
for parent != src {
results = append(results, parent)
parent = g.previous[parent]
}
results = append(results, src)
fmt.Println("Paths from %s to %s node:", src, dst, reverse(results))
}
}
func (g *Graph) dfs(start, dst, parent string, visited map[string]bool) bool {
visited[start] = true
g.previous[start] = parent
if start == dst {
return true
}
for _, ver := range g.adj[start] {
if !visited[ver] {
if g.dfs(ver, dst, start, visited) {
return true
}
}
}
return false
}
func (g *Graph) newVisited() map[string]bool {
visited := make(map[string]bool, len(g.adj))
for key := range g.adj {
visited[key] = false
}
return visited
}
func reverse(slice []string) []string {
reverseResults := make([]string, 0)
for i := len(slice) - 1; i >= 0; i-- {
reverseResults = append(reverseResults, slice[i])
}
return reverseResults
}自然地，所有点的路径问题都可以在单源路径问题的基础上解决，也就是对图中每个节点都执行一次单源路径算法。
同样是解决单源路径问题，广度优先搜索算法使用队列，只要队列不为空，while循环就不停。取出队列中的第一个元素，即节点V，然后找到所有与节点V相邻的节点，并将其压入队列。使用一个for循环来遍历所有与节点V相邻的节点。
确认相邻节点W是否已经访问过，即判断visited[W]= =false？如果没有，可以将其压入队列。visited[]数组确保一个节点只会被访问一次，即入队一次、出队一次。这样可避免重复入队、重复访问同一个节点。
func (g *Graph) SingleSourcePathBFS(src, dst string) {
isConnected := g.BFS(src, dst)
if isConnected {
g.outputSingleSourcePath(src, dst)
}
}
func (g *Graph) BFS(src, dst string) bool {
visited := g.newVisited()
g.previous = make(map[string]string)
visited[src] = true
g.previous[src] = src
var q []string
q = append(q, src)
for len(q) > 0 {
var current string
current, q = q[0], q[1:]
g.results = append(g.results, current)
for _, adj := range g.adj[current] {
if !visited[adj] {
q = append(q, adj)
visited[adj] = true
g.previous[adj] = current
if adj == dst {
return true
}
}
}
}
return false
}对于广度优先搜索的单源（最短）路径算法的总结如下。
● 在广度优先搜索的代码框架上做一点修改，就可以解决广度优先搜索的单源路径问题。
● 首先，对于每个连通分量的起始点，它的previous[]值对应它自己，即previous[src]=src。
● 其次，对节点V的所有相邻节点进行广度优先搜索，如果相邻节点W没有被访问过，即visited[W]=false，则将节点W压入队列。与此同时，说明V-W构成了一条边，节点W的上一个节点是V，即previous [W]=V。
下面介绍广度优先搜索与深度优先搜索的区别与联系。
如图1-80所示，对于同一个图，想要找到从节点A到节点G的路径，深度优先搜索算法的过程是A -> B -> D -> C -> G，广度优先搜索算法的过程是A -> C -> G ，故广度优先搜索算法实现的是最短路径，这是广度优先搜索的性质。
图1-80
为了理解这个性质，可以简单回顾一下树的广度优先搜索算法，如图1-81所示。
● 从根节点A开始使用广度优先搜索算法进行遍历。
● 找到节点B和节点C，它们与根节点的距离是1。
● 继续遍历节点B和节点C，找到D、E、F、G这4个节点，它们与根节点的距离是2。
图1-81
树的广度优先搜索算法被称为层序遍历，本质是按照与根节点距离的远近来遍历的，先遍历与根节点距离小的节点，后遍历与根节点距离大的节点，依此类推。换句话说，在树的广度优先搜索算法中，后遍历的节点到根节点的距离一定大于或者等于先遍历的节点到根节点的距离。
同理，图的广度优先搜索算法也是按照与起始点A距离的远近来遍历的，即后遍历的节点肯定比先遍历的节点与根节点之间的距离大或者二者相等。最后，广度优先搜索能保证找到从开始到目标节点的最短路径，而深度优先搜索却不能。
检测无向图中是否有环，整体思路与单源路径问题非常相似，二者的区别在于：单源路径问题是检索从一个节点到另一个节点是否有路径；而检测无向图中是否有环是检索从一个节点到该节点本身是否有路径。单源路径问题中的起始节点与终止节点是不同的，而无向图中是否有环问题中的起始节点与终止节点是相同的。
在图1-82中寻找从节点A起始的图中是否有环的思想如下。
图1-82
● 从节点A开始深度优先遍历它的相邻节点。先找到相邻节点B。
● 遍历到节点B的时候，找到它有A、D、E这3个相邻节点。由于节点A是节点B的上一个节点，尽管节点B可以回到节点A，但并不是一个环。
● 遍历到节点D的时候，找到它有B、C这两个相邻节点。由于节点B已经访问过，因此节点B不是要寻找的终止节点。
● 遍历到节点C的时候，找到它有A、G这两个相邻节点。由于节点A已经访问过，同时也是我们寻找的终止点，说明从节点C可以回到节点A，并且当前来到节点C的上一个节点为D而非A。因此，深度优先搜索找到了一个环。
上面例子中，整个过程是从节点A开始的，最后遍历的终止节点也是A。但也有可能从一个节点开始到最后发现一个环，环的终止节点与搜索的起始节点并不相同。例如在图1-83中，发现环的过程为A -> B -> D -> E -> B，其中起始节点是A，终止节点是B。
检测无向图中的环的算法思想是，遍历所有节点，若在遍历过程中找到了一个已经被访问的节点，并且这个节点并不是当前节点的上一个节点，说明此时找到了一个环。
图1-83
func (g *Graph) cycleDetection() bool {
visited := g.newVisited()
for key := range g.adj {
if !visited[key] {
if g.dfsCycleDetection(key, key, visited) {
fmt.Println("Detected Cycle")
return true
}
}
}
fmt.Println("No Cycle")
return false
}
func (g *Graph) dfsCycleDetection(src, parent string, visited map[string]bool) bool {
visited[src] = true
for _, ver := range g.adj[src] {
if !visited[ver] {
if g.dfsCycleDetection(ver, src, visited) {
return true
}
// Leon Bug
//else if ver != parent {
// return true
//}
} else if ver != parent {
return true
}
}
return false
}DFS(V, parent)接收两个参数，一个是当前正在遍历的节点V；另一个是节点parent，它表示当前遍历节点的上一个节点。
对节点V的所有相邻节点进行深度优先遍历，即for(int W : g.adj(V))，有如下逻辑判断：
● 如果相邻节点W没有被访问过，即visited[W]=false，则会进一步触发深度优先搜索算法；
● 如果满足W!= parent，则表示当前相邻节点W已经被访问过，并且它不是当前节点V的上一个节点parent，此时说明找到了一个环。
如果一个图中所有边的两个端点都属于不同的部分，则将这个图称为二分图。二分图的节点可以分成不相交的两个部分，如图1-84所示。图1-84中左、右图是完全等价的，左图比较容易判断出是二分图，但右图就比较难判断它的二分图性质。二分图有巨大的应用，比如选课系统，左边节点代表学生，右边节点代表课程。染色算法是典型的二分图建模算法。
图1-84
二分图检测是基于深度优先搜索的算法，但是在深度优先搜索的过程中需要进行染色的操作，即在遍历图的过程中，为每个节点指定一个颜色。比如将黑色与红色两种颜色分别赋给图中每个节点。最后看能不能实现每条边的两端节点颜色是不同的，即如果边的一个端点是红色的，那么边的另一个端点就必须是黑色的。
图1-85
以图1-85为例，深度优先搜索中的染色过程如下。
● 访问起始节点A并将其染成红色，找到相邻节点B、C。访问节点B。
● 访问节点B并将其染成黑色（与上一个节点A颜色不同）。找到相邻节点A、D、E。节点A已经标记为访问，故访问节点D。
● 访问节点D并将其染成红色（与上一个节点B颜色不同）。找到相邻节点B、C。节点B已经标记为访问，故访问节点C。
● 访问节点C并将其染成黑色（与上一个节点D颜色不同）。找到相邻节点A、D、G。节点A和D已经标记为访问，并且节点A和D与节点C的颜色不相同，故访问节点G。
● 访问节点G并将其染成红色（与上一个节点C颜色不同）。找到相邻节点C、F。节点C已经标记为访问，故访问节点F。
● 访问节点F并将其染成黑色（与上一个节点G颜色不同）。节点F已经标记为访问，且没有其他相邻节点可以遍历，故返回上一层节点G。
● 继续从节点G开始按照深度优先搜索算法来递归遍历，所有相邻节点已经被标记为访问，所以返回上一层节点C。
● 继续从节点C开始按照深度优先搜索算法来递归遍历，所有相邻节点已经被标记为访问，所以返回上一层节点D。
● 继续从节点D开始按照深度优先搜索算法来递归遍历，所有相邻节点已经被标记为访问，所以返回上一层节点B。
● 继续从节点B开始按照深度优先搜索算法来递归遍历，找到相邻节点A、D、E。节点A和D已经被标记为访问，故访问节点E。
● 访问节点E并将其染成红色（与上一个节点B颜色不同）。所有相邻节点已经被标记为访问，所以返回上一层节点B。
● 继续从节点B开始按照深度优先搜索算法来递归遍历，所有相邻节点已经被标记为访问，所以返回上一层节点A。
● 继续从节点A开始按照深度优先搜索算法来递归遍历，所有相邻节点已经被标记为访问，并已经到达递归的第一层，DFS函数完成染色过程。
整个染色过程中，需要依次将图中每个节点染成红色或者黑色。声明一个整型数组colors[]，数组大小等于图中的节点数目，数组中存储每个节点的颜色。
DFS函数接受两个参数，一个是当前节点V，另一个是节点V对应的colors[]值。DFS函数的逻辑如下。
● 首先对当前节点V的访问标志与colors[]标志进行赋值。
● 然后对当前节点V的所有邻接点进行遍历。
❏ 如果相邻点W没有被访问过，即visited[W]=false，此时需要触发深度优先搜索递归调用，并且需要对节点W进行染色。节点W的colors[]值当然应该与节点V的colors[]值不同，所以记为1-color，即DFS(W, 1-color)。
❏ 如果相邻节点W已经被访问过，就说明节点W已经被染色了，需要判断节点W的颜色与上一个节点V的颜色是否相同，即colors[W]是否等于colors[V]。如果相同，说明V-W这条边的两个节点的颜色是相同的，违反了二分图的定义，进而说明当前遍历的图不是二分图。
func (g *Graph) binaryParDetection() {
colors := g.newColor()
visited := g.newVisited()
for key := range g.adj {
if !visited[key] {
if !g.dfsBinaryParDetection(key, 0, visited, colors) {
fmt.Println("No Binary Partition Detection:")
}
}
}
fmt.Println("Binary Partition Detection:", colors)
}
func (g *Graph) dfsBinaryParDetection(src string, color int, visited map[string]bool, colors map[string]int) bool {
visited[src] = true
colors[src] = color
for _, ver := range g.adj[src] {
if !visited[ver] {
if !g.dfsBinaryParDetection(ver, 1-color, visited, colors) {
return false
}
} else if colors[ver] == colors[src] {
return false
}
}
return true
}拓扑排序是一个有向无环图的所有节点的线性序列，并且满足两个条件：
● 每个节点仅出现一次；
● 如果存在一条从节点A到节点B的路径，那么在拓扑序列中节点A出现在节点B的前面。
图1-86中，节点A指向节点B和C，因此拓扑排序中节点A出现在它们之前。同时，节点B和C都指向节点D，因此拓扑排序中节点B、C出现在节点D之前。以此类推，拓扑排序的最终结果为[A, B, C, D, E]。
图1-86
对于有环图而言，如图1-87所示，节点B指向节点D，同时节点D也间接指向节点B，这要求拓扑排序结果中节点B必须出现在节点D之前，同时节点B又出现在节点D之后，这是矛盾的。因此有环图没有拓扑排序。
图1-87
以图1-88为例来说明拓扑排序算法的流程。首先，需要找到一个入度为0的节点，此时发现节点A的入度为0，因此将节点A添加到拓扑排序的结果中。一旦将节点A加入了拓扑排序中，则将节点A及其出边进行虚拟删除，然后重新计算图中与节点A相邻的节点的入度。接下来，重复前面的步骤，查找任何入度为0的节点，并将其添加到拓扑排序结果中。
图1-88
算法步骤归纳如下。
● 查找入度为0的节点。
● 将该节点添加到拓扑排序结果中。
● 从图中删除以该节点起始的边，并重新计算与该节点相邻的节点的入度。
● 重复上述步骤。
拓扑排序本质上是一个有向无环图，或者是一个依赖树。如果任何事件B要求在启动之前完成事件A，那么在排序中A将出现在B之前。拓扑排序在计算机中的应用非常广泛，比如用来构建相互依赖的系统、编译器系统、学校选课系统、Hadoop中的任务调度子系统等。当然，拓扑排序在生活中也有很多应用场景，比如安排家务事（洗完衣服之前不能出门）；为儿童制定疫苗接种时间表，使得某些疫苗接种必须在其他疫苗接种之前完成。
拓扑排序算法使用队列来记录当前入度为0的节点。遍历队列中入度为0的节点并将结果输出到拓扑排序结果中，同时更新该节点相邻的节点的入度（减一操作），如果更新后相邻节点的入度为0则需要将其放入队列。后续重复这个过程，不断从队列中取出入度为0的节点。
特别说明两点：第一点是拓扑排序的结果并不是唯一的；第二点是对于有向有环图，拓扑排序是无解的（换句话说，拓扑排序算法有一个附加的效果，用来检测有向图中是否有环）。
package toposort
type Graph struct {
vertexes []string
indegree map[string]int
edges map[string][]string
}
func NewGraph(cap int) *Graph {
return &Graph{
vertexes: make([]string, 0, cap),
indegree: make(map[string]int),
edges: make(map[string][]string),
}
}
func (g *Graph) AddNode(nodeName string) bool {
g.vertexes = append(g.vertexes, nodeName)
if _, ok := g.edges[nodeName]; ok {
return false
}
g.edges[nodeName] = make([]string, 0)
g.indegree[nodeName] = 0
return true
}
func (g *Graph) AddNodes(nodeNames ...string) bool {
for _, name := range nodeNames {
if ok := g.AddNode(name); !ok {
return false
}
}
return true
}
func (g *Graph) AddEdge(src, dst string) bool {
_, ok := g.edges[src]
if !ok {
return false
}
// Leon Bug
//adjEdges = append(adjEdges, dst)
g.edges[src] = append(g.edges[src], dst)
g.indegree[dst]++
return true
}
func (g *Graph) RemoveEdge(src, dst string) bool {
if _, ok := g.edges[src]; !ok {
return false
}
g.edges[src] = remove(g.edges[src], dst)
g.indegree[dst]--
return true
}
func remove(s []string, r string) []string {
for i, v := range s {
if v == r {
return append((s)[:i], (s)[i+1:]...)
}
}
return nil
}
func (g *Graph) Toposort() ([]string, bool) {
queue := make([]string, 0, len(g.vertexes))
rets := make([]string, 0, len(g.vertexes))
for _, vertex := range g.vertexes {
if g.indegree[vertex] == 0 {
queue = append(queue, vertex)
}
}
for len(queue) > 0 {
var curVertex string
curVertex, queue = queue[0], queue[1:]
rets = append(rets, curVertex)
backup := make([]string, len(g.edges[curVertex]))
copy(backup, g.edges[curVertex])
for _, adjVertex := range backup {
//Leon Bug: you cann't modify g.edges[curVertex] inside RemoveEdge when iterating g.edges[curVertex]
g.RemoveEdge(curVertex, adjVertex)
if g.indegree[adjVertex] == 0 {
queue = append(queue, adjVertex)
}
}
}
totalDegree := 0
for _, degree := range g.indegree {
totalDegree += degree
}
if totalDegree > 0 {
return rets, false
}
return rets, true
}链表、树与图的算法大量涉及递归操作。如何递归地思考？基本思想是忘记技术细节，只考虑定义，特别是函数递归定义。举例来说，检查一个字符串是否是回文串。根据定义，如果一个字符串和它的逆串相同，那么称这个字符串为回文串，如abcba。
有两种方法来检查一个字符串是否为回文串：for循环迭代和递归。
在迭代算法中，只需维护两个指针——开始（begin）和结束（end）。如果开始和结束指针指向的两个字符相同，就可以继续将开始指针向后移动，而将结束指针向前移动，再次检查两个字符，直到开始指针与结束指针交叉。
在递归算法中，第一步判断原始字符串是否构成一个回文串，判断内容如下。
● 开始字符与结束字符相同。
● 字符串的其余部分是回文串？
第二步判断字符串其余部分是否构成一个回文串，判断内容如下。
● 开始字符与结束字符相同。
● 字符串的其余部分是回文串？
第三步判断字符串其余部分是否构成一个回文串，判断内容如下。
● 开始字符与结束字符相同。
● 字符串的其余部分是回文串？
继续递归调用，直到“字符串的其余部分”为空，递归函数回溯返回，确定当前字符串是一个回文串。
本质上，递归就是用同一个子问题来表达原始问题。一般来说，原始问题可以分成子问题，子问题进一步被分解成更小的子问题，最终，这个子问题变成了基本的简单问题，可以直接给出答案。通过递归函数可以一步步回溯到调用起点，比如，求解二叉树的节点数：
if tree is not empty
size(tree) = size(tree.left) + size(tree.right) + 1记住，递归就是一个遍历，一种for循环迭代而已。它可以用来解决子问题，比如，遍历数组、链表、树和图结构。对于动态规划（Dynamic Programming，DP）来说，它有两种类型：自顶向下和自底向上。其中自顶向下的本质就是递归，但是增加了记忆查找表的功能。我们知道，DP问题中相同的子问题会重复出现，为了避免将来重复计算相同的子问题，只需要通过搜索记忆查找表直接返回值，即可提高算法效率。
本章介绍了各种数据结构的搜索算法，既是为了让读者学习，也是为了帮助读者更加全面地了解搜索领域。
首先，介绍了字符串搜索算法，主要详细讨论了常见的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树模型进行等价分析将事半功倍。
最后，介绍了图搜索算法，主要讨论了如何使用深度优先搜索算法和广度优先搜索算法解决一些典型的图应用问题，比如求解图的连通分量、单源最短路径、二分图的检测、拓扑排序。图搜索算法有一个基本思路，即在使用深度优先搜索算法或者广度优先搜索算法对图进行搜索的过程中，可以记录一些辅助信息来完成对问题的求解。
