標簽：lock 編程語言 android 約束 面經 一起 真題 完整 畫圖
前陣子發了一篇文，說了一下現在大廠對算法的重視，留言區很多人表示算法是一個過不去的坎。
其中的一个朋友就发来了他面试美团Android岗的面經：
他表示，其他的面試題目都答得還不錯，面試官也很滿意，但是這個手寫紅黑樹把他難倒了，支支吾吾了半天也沒有弄清楚，希望我能幫助他。
想著有這個問題的應該不止他一個，就決定寫個文和大家分析一下這個紅黑樹，希望對大家的學習和工作有所幫助。
隔熱覺得，手寫紅黑樹可能有點過分了，我覺得寫不出來也正常，只要理解就行（面試的時候可以問問能不能改爲口述）。
紅黑樹是數據結構中比較複雜的一種，最近與它交集頗多，于是花了一周的空閑時間跟它死磕，終于弄明白並實現了紅黑樹。
寫文總結一下，希望能給試圖理解紅黑樹的同學一些靈感，也讓我能記得更深刻。
在研究紅黑樹時吃了不少苦頭，原因有二：
紅黑樹的插入和刪除非常複雜，很多人並沒有理解或完全實現，或實現了的沒有任何注釋，讓人很難參考；
网络上紅黑樹的理解方式较为单一，一般是 双黑、caseN 法，而插入和删除的情况很多，每种都有对应的处理方式，如果死记硬背的话，再过一段时间再回忆各种情况可能就一头雾水了。
网络上讲紅黑樹的实现多来源于《算法導論》一书，直接讲紅黑樹的实现，需要处理颜色和高度两种属性約束，比较晦涩。本文通过紅黑樹的等同—— 2-3-4樹，避开颜色属性約束，也弱化了高度的影响，以另一种方式去理解紅黑樹，虽然并不能完全降低它的复杂度，但自认为较之普遍实现，更易记一些。
紅黑樹是一种结点带有颜色属性的二叉查找树，但它在二叉查找树之外，还有以下要求：
節點是紅色或黑色。
根是黑色。
所有葉子都是黑色（葉子是NIL節點）。
每個紅色節點必須有兩個黑色的子節點。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。）
從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。
下图就是一个典型的紅黑樹：
但实现上我省略了其中的 Nil 结点，一般如下图，大家理解时也可以忽略它们。
我們知道二叉查找樹在不停地添加或刪除結點後，可能會導致結點情況如下：
這種情況下，二叉查找樹的查找效率最壞會降低爲 O(n)。
而紅黑樹由于在插入和刪除結點时都会进行变色旋轉等操作，在符合紅黑樹条件的情况下，即使一边子树全是黑色结点，另一边子树全是红黑相间，两子树的高度差也不会超过一半。一棵有 n 个结点的紅黑樹高度至多为 2log(n+1)，查找效率最壞爲 O(log(n))。
所以紅黑樹常被用于需求查找效率稳定的场景，如 Linux 中内核使用它管理内存区域对象、Java8 中 HashMap 的实现等，所以了解紅黑樹也很有意义。
下面介绍一下紅黑樹的等同 2-3-4樹。
2-3-4樹是四阶的 B树(Balance Tree)，它的结构有以下限制：
所有葉子節點都擁有相同的深度。
节点只能是 2-节点、3-节点、4-节点之一。
2-节点：包含 1 个元素的节点，有 2 个子节点；
3-节点：包含 2 个元素的节点，有 3 个子节点；
4-节点：包含 3 个元素的节点，有 4 个子节点；
元素始終保持排序順序，整體上保持二叉查找樹的性質，即父結點大于左子結點，小于右子結點；而且結點有多個元素時，每個元素必須大于它左邊的和它的左子樹中元素。
下图是一个典型的 2-3-4樹（来自维基百科）：
2-3-4樹的查询操作像普通的二叉搜索树一样，非常简单，但由于其结点元素数不确定，在一些編程語言中实现起来并不方便，实现一般使用它的等同——紅黑樹。
至于为什么说紅黑樹是 2-3-4樹的一种等同呢，这是因为 2-3-4樹的每一个结点都对应紅黑樹的一种结构，所以每一棵 2-3-4樹也都对应一棵紅黑樹，下图是 2-3-4樹不同结点与紅黑樹子树的对应。
而上文中的 2-3-4樹也可以转换成一棵紅黑樹：
由紅黑樹的性质5，和 2-3-4樹的性质1，为了便于理解紅黑樹和 2-3-4樹的对应关系，我们可以把紅黑樹从根结点到叶子结点的黑色结点个数定义为高度。
紅黑樹和 2-3-4樹的结点添加和删除都有一个基本规则：避免子树高度变化，因为无论是 2-3-4樹还是紅黑樹，一旦子树高度有变动，势必会影响其他子树进行调整，所以我们在插入和刪除結點时尽量通过子树内部调整来达到平衡，2-3-4樹实现平衡是通过结点的旋轉和结点元素数变化，紅黑樹是通过结点旋轉和变色。
下面来对照着 2-3-4樹说一下紅黑樹结点的添加和删除：
2-3-4樹中结点添加需要遵守以下规则：
插入都是向最下面一層插入；
升元：将插入结点由 2-结点升级成 3-结点，或由 3-结点升级成 4-结点；
向 4-結點插入元素后，需要将中间元素提到父结点升元，原结点变成两个 2-结点，再把元素插入 2-结点中，如果父结点也是 4-结点，则遞歸向上层升元，至到根结点后将树高加1；
而将这些规则对应到紅黑樹里，就是：
新插入的結點顔色爲紅色，这样才可能不会对紅黑樹的高度产生影响。
2-结点对应紅黑樹中的单个黑色结点，插入时直接成功（对应 2-结点升元）。
3-结点对应紅黑樹中的黑+紅子樹，插入後將其修複成 红+黑+紅 子树（对应 3-结点升元）；
4-结点对应紅黑樹中的红+黑+紅子樹，插入後將其修複成紅色祖父+黑色父叔+紅色孩子子树，然后再把祖父结点当成新插入的紅色结点遞歸向上层修复，直至修复成功或遇到 root 结点；
如上图所示，虽然向紅黑樹中插入了一个新结点，但由于旋轉和变色，子树的高度保持不变。
紅黑樹的删除要比插入要复杂一些，我们还是类比 2-3-4樹来讲：
查找最近的葉子結點中的元素替代被刪除元素，刪除替代元素後，從替代元素所處葉子結點開始處理；
降元：4-结点变 3-结点，3-结点变 2-结点；
2-結點中只有一個元素，所以借兄弟結點中的元素來補充刪除後的造成的空結點；
当兄弟结点中也没有多个元素可以补充时，尝试将父结点降元，失败时向上遞歸，至到子树降元成功或到 root 结点树高减1；
将这些规则对应到紅黑樹中即：
查找離當前結點最近的葉子結點作爲替代結點（左子树的最右结点或右子树的最左结点都能保证替换后保证二叉查找树的结点的排序性质，叶子结点的替代結點是自身）替换掉被刪除結點，从替代的叶子结点向上遞歸修复；
替代結點颜色为紅色（对应 2-3-4樹中 4-结点或 3-结点）时删除子结点直接成功；
替代結點为黑色（对应 2-3-4樹中 2-结点）时，意味着替代結點所在的子树会降一层，需要依次检验以下三项，以恢复子树高度：
兄弟结点的子结点中有紅色结点（兄弟结点对应 3-结点或 4-结点）能够“借用”，旋轉过来后修正颜色；
父结点是紅色结点（父结点对应 3-结点或 4-结点，可以降元）时，将父结点变黑色，自身和兄弟结点变紅色后删除；
父結點和兄弟結點都是黑色時，將子樹降一層後把父结点当作替代結點遞歸向上處理。
如上圖，刪除的要點是 找到替代結點，如果替代結點是黑色，遞歸向上依次判断侄子结点、父结点是否可以补充被删除的黑色，整体思想就是将删除一个黑色结点造成的影响局限在子树内处理。
當然實現過程中調試也占了很大一部分，我使用了兩項方法幫助調試：
由于插入多个结点时，无法确定是处理哪个结点时出了问题，于是我给紅黑樹类添加了 debug 屬性，用二分法設置此屬性來找到問題結點；
给紅黑樹类添加了 printTree() 方法，實時打印樹結構，確定代碼問題再分析；
由于紅黑樹相对其他树实在较为复杂，只通过思考就完全理解不太现实，还需要自己去试着画，试着实现，我画了 5 张 A4 纸的正反面才算理解了紅黑樹，即便如此，在写这篇文章时还发现了代码中的可优化点。
而且代码实现比畫圖还略复杂，理论中的一个旋轉就包含了 左旋/右旋/先左旋再右旋/先右旋再左旋 幾種情況，雖然有一定規律，還是自己實現一下印象最深刻。
算法現在真的是越來重要了，已經成爲一個考驗程序員技術水平最快的方法，尤其是對應屆生來說。聽說字節跳動的技術崗甚至有算法題一票否決的情況。
但是，數據結構與算法這個知識點的准備需要的時間比較長，要盡早准備，多刷一些leetcode或是其他類似的題。我個人的算法能力一開始也很差，但是經過我自己安排的算法專項訓練，效果還是十分顯著的。下面是我的複習方法，希望對大家的學習和工作有所啓發和幫助。
下面是數據結構和算法的面試核心知識點，大家可以參考學習，逐個擊破。
在刷題之前我建議你看一些書：
《漫畫算法之旅》
如果你之前沒有任何算法基礎，這邊書很適合你，可以補充數據結構和算法的基礎知識，像什麽是時間複雜度空間複雜度、查找、排序等。
如果你有了一定基礎了，建議你直接跳到最後面的算法實戰部分。
《剑指 offer》
非常经典的一本书，学算法的人必刷。但是要注意了，这边书里面的题目是用 C++写的，如果你是 Java 开发人员可能会有点影响。但是要记住学习算法最关键的还是解题思路和方法，用什么语言实现是其次的，如果你时间比较多我是建议你用 Java 语言再实现一遍。
《labuladong的算法小抄》
非常推荐！这是一本很新的书，写书前作者在 Github 开源了一个项目，主要讲解 LeetCode 解题套路，Start 总数排名前40。在书的开头讲解了学习算法的基本思维和套路，建议看这边书的同时再配合 leetcode 刷题，疗效非常棒！
《算法導論》
要是不推荐这本书是不是显得我有点 low 了，这是一本科班出身的同学必看必学的经典大部头。国外大佬写的，国内翻译的经典之作，虽然是经典但是不建议刚入门算法的同学看，因为看了这本书你可能要放弃算法了，比较难看懂。建议有了一定基础再入手这边书。
如果你覺得看書比較枯燥，可以推薦你看一些極客時間的專欄，不過是收費，但是質量非常高。
《數據結構與算法之美》
这个专栏是文字+语音，作者是王争，前 Google 工程师。他采用最适合工程师的学习方式，不拘泥于某一特定編程語言，从实际开发场景出发，由浅入深教你学习数据结构与算法的方法，幫你搞懂基本概念和核心理論，深入理解算法精髓，幫你提升使用數據結構和算法思維解決問題的能力。
《算法面試通關40講》
這個專欄是視頻，作者是覃超，前Facebook工程師。作者會用白板帶你一步一步解題，層層深入一環扣一環，每一題還會用多種解題方法。我基本看完了，收獲頗多。
leetcode、書和極客專欄可以並行，學練結合，不要光看不練。
點擊【此處】進入我的公衆號，添加備注【
算法】，免費獲取這份資料的完整版
Android開發駱駝主頁
大廠Android面試專題（記得給我點贊哦~）
这边还整理了一套大厂常问Android面试真題，有需要的朋友可以找我一起打包获取。
點擊【此處】進入我的公衆號，添加備注【
算法】，免費獲取這份資料的完整版
資源持續更新中，歡迎大家一起學習和探討。
標簽：lock 編程語言 android 約束 面經 一起 真題 完整 畫圖
原文地址：https://www.cnblogs.com/chengsisi/p/14862804.html
