久久精品中文字幕av,av.涩涩涩涩涩涩涩涩,亚洲国产日韩欧美精品成人久久久,成人福利电影免费在线观看,日产国产原创av,日韩av午夜激情,bt天堂中文字幕,超级碰人妻在线视频,欧美老熟妇久久一区二区

[TOC] ## 概述 紅黑樹，Red-Black Tree，是一種自平衡（大致平衡）二叉查找樹。紅黑樹在進行插入和刪除時通過特定操作保持二叉樹的平衡，從而獲得較高的查找性能。 &nbsp; 紅黑樹具有以下五個特性： **1. 節(jié)點是紅色或黑色。 2. 根是黑色。 3. 所有葉子都是黑色（葉子是NIL節(jié)點）。 4. 每個紅色節(jié)點必須有兩個黑色的子節(jié)點。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。） 5. 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。** &nbsp; 下面是一個具體的紅黑樹實例：  &nbsp; 通過以上約束強制了紅黑樹的關(guān)鍵性質(zhì)：**從根到葉子的最長的可能路徑不多余最短的可能路徑的兩倍長**。結(jié)果是這個樹大致上是平衡的，插入、刪除、查找操作的最壞情況都與樹的高度成比例，不會出現(xiàn)二叉查找樹中左右子樹極度不平衡的情況。 &nbsp; 再來解釋一下為什么"從根到葉子的最長的可能路徑不多余最短的可能路徑的兩倍長"？ 根據(jù)性質(zhì)4和性質(zhì)5，紅黑樹中最短的可能路徑都是黑色節(jié)點，最長的可能路徑有交替的紅色和黑色節(jié)點，并且最短路徑和最長路徑有相同數(shù)量的黑色節(jié)點，這就表明了最長的可能路徑不多余最短的可能路徑的兩倍長。 <br/> ## 紅黑樹的操作 ### 紅黑樹的插入 紅黑樹的插入操作可以分成兩步來理解： 1. 先把新節(jié)點掛到紅黑樹相應(yīng)位置上。 2. 調(diào)整紅黑樹，使其滿足紅黑樹的5個性質(zhì)。 第一步比較簡單，從根節(jié)點開始，按二叉查找樹左子小右子大的規(guī)則找到插入位置就可以了。我們重點考慮另外一個問題，新插入節(jié)點是否會破壞紅黑樹的平衡（不滿足紅黑樹的5個性質(zhì)），還有如何恢復(fù)平衡？ &nbsp; 新增節(jié)點或刪除節(jié)點之后，紅黑樹為了恢復(fù)平衡，有兩大操作： * **recolor 重新標記顏色** * **rotation 旋轉(zhuǎn)** 先嘗試 recolor，如果 recolor 不能達到紅黑樹的5點要求，接著嘗試 rotation。弄清楚 recolor 和 rotation 的規(guī)則也是掌握紅黑樹的關(guān)鍵，接下來看看紅黑樹中插入新節(jié)點X的邏輯： 1. **將新插入的節(jié)點X標記為紅色。（因為標記為紅色不會破壞性質(zhì)5）** 2. **如果X是根節(jié)點root，標記為黑色。** 3. **如果X的父節(jié)點是黑色。這種情況不會破壞紅黑樹的特性，不需要處理。** 4. **如果X的父節(jié)點是紅色：** 4.1 **如果X的叔父節(jié)點也是紅色：** 4.1.1. **將父節(jié)點和叔父節(jié)點都標記為黑色。** 4.1.2. **將祖父節(jié)點標記為紅色** 4.1.3. **然后對X的祖父節(jié)點重復(fù)步驟2、3。**  上面幾種情況都是 recolor 操作，也就是父節(jié)點和叔父節(jié)點同為紅色的情況下應(yīng)該執(zhí)行的操作。下面來看一下旋轉(zhuǎn)操作： &nbsp; 4.2. **如果X的叔父節(jié)點是黑色，要分4種情況處理：** 4.2.1. **左左：P是G的左節(jié)點，且X是P的左節(jié)點** 對G節(jié)點執(zhí)行右旋操作，之后交換 P、G 顏色。  &nbsp; 4.2.2. **左右（P是G的左節(jié)點，且X是P的右節(jié)點）** 先對P節(jié)點執(zhí)行左旋，用X節(jié)點替換P節(jié)點，然后再應(yīng)用左左情況。  &nbsp; 4.2.3. **右右（P是G的右節(jié)點，且X是P的右節(jié)點）** 對G節(jié)點執(zhí)行左旋操作，之后交換 P、G 顏色。  &nbsp; 4.2.4. **右左（P是G的右節(jié)點，且X是P的左節(jié)點）** 先對P節(jié)點執(zhí)行右旋操作，用X節(jié)點替換P節(jié)點，然后再應(yīng)用右右情況  <br/> ### 紅黑樹的刪除 為了容易理解，先列一下紅黑樹刪除的大體思路： 1. 刪除節(jié)點： 1.1 如果要刪除的節(jié)點沒有子節(jié)點，直接刪除節(jié)點。 1.2 如果要刪除的節(jié)點有一個子節(jié)點，刪除節(jié)點之后，用子節(jié)點頂替上來。 1.3 如果要刪除的節(jié)點有兩個子節(jié)點，那么問題可以被轉(zhuǎn)化成刪除另一個只有一個子節(jié)點的節(jié)點。就是回到了上面1.2這種情況，具體怎么轉(zhuǎn)化后面會講。 2. 刪除節(jié)點之后，調(diào)整紅黑樹，使其滿足紅黑樹的5個性質(zhì)。 先看這個問題"如果要刪除的節(jié)點有兩個子節(jié)點，那么問題可以被轉(zhuǎn)化成刪除另一個只有一個子節(jié)點的節(jié)點"。 &nbsp; 在刪除帶有兩個子節(jié)點的節(jié)點的時候，我們要么找到它左子樹中的最大元素、要么找到它右子樹中的最小元素，并把它的值復(fù)制到要刪除的節(jié)點中（不復(fù)制顏色），接著去刪除我們從中復(fù)制出值的那個節(jié)點，它必定只有一個子節(jié)點或沒有子節(jié)點（因為它是最大或最小元素，不可能有兩個子節(jié)點）。不好理解就直接看圖：  圖中實例使用的是左子樹的最大元素6來代替8，實際上，找右子樹的最小值也是可以的，兩者選其一即可。 &nbsp; 接著，**怎么刪除有一個子節(jié)點的節(jié)點呢？**假設(shè)要刪除節(jié)點X，子節(jié)點是N。 1. **X是紅色節(jié)點，刪除X之后用N頂替，僅僅是少了一個紅色節(jié)點，不會破壞紅黑樹的性質(zhì)。**  &nbsp; 2. **X是黑色節(jié)點：** 2.1 **子節(jié)點N是紅色。** 刪除X之后用N頂替。由于經(jīng)過N的路徑上少了個黑色節(jié)點，所以要把N改成黑色。  &nbsp; 2.2 **子節(jié)點N也是黑色：** &nbsp;&nbsp;&nbsp;&nbsp;2.2.1 **節(jié)點X是樹根。** &nbsp;&nbsp;&nbsp;&nbsp;N成為新根，在所有路徑上少了個黑色節(jié)點，然后又出現(xiàn)一個黑色的新根，所以保持了紅黑樹的性質(zhì)。 &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.2 **節(jié)點S是紅色。** &nbsp;&nbsp;&nbsp;&nbsp;在節(jié)點P上做左旋，接著互換P節(jié)點和S節(jié)點的顏色，之后按后面的2.2.4、2.2.5、2.2.6來處理。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.3 **節(jié)點P、節(jié)點S、S的子節(jié)點都是黑色。** &nbsp;&nbsp;&nbsp;&nbsp;直接把節(jié)點S改成紅色，之后按2.2.2來處理。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.4 **節(jié)點P是紅色，節(jié)點S和S的子節(jié)點都是黑色。** &nbsp;&nbsp;&nbsp;&nbsp;交換節(jié)點P和節(jié)點S的顏色，經(jīng)過S的路徑上黑色節(jié)點保持不變，經(jīng)過N的路徑上新增了一個黑色節(jié)點，正好填補已刪除的黑色節(jié)點。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.5 **節(jié)點S是黑色，S的左子節(jié)點是紅色，S的右子節(jié)點是黑色，并且N是它父節(jié)點的左子節(jié)點。** &nbsp;&nbsp;&nbsp;&nbsp;在節(jié)點S上右旋，交換節(jié)點L和節(jié)點S的顏色，之后按2.2.6處理。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.6 **節(jié)點S是黑色，S的右子節(jié)點是紅色，并且N是它父節(jié)點的左子節(jié)點。** &nbsp;&nbsp;&nbsp;&nbsp;在P節(jié)點上做左旋，接著交換節(jié)點P和節(jié)點S的顏色，并把節(jié)點R改成黑色，這樣，經(jīng)過節(jié)點N的路徑、經(jīng)過L的路徑、經(jīng)過R的路徑上的黑色數(shù)目與原來保持一致了。  &nbsp; 以上就是紅黑樹的刪除操作，多處都涉及到了遞歸邏輯，所以稍微難懂一點。結(jié)合圖例多看幾遍還是能看懂的。