從2-3-4樹模型到紅黑樹實作
目錄
- 從2-3-4樹模型到紅黑樹實作
- 前言
- 2-3-4樹
- 查找
- 插入
- 樹的生長
- 洗掉
- 洗掉最大key
- 洗掉最小key
- 洗掉任意key
- 左傾紅黑樹
- 查找
- 插入
- 洗掉
- 洗掉最大Key
- 洗掉最小Key
- 洗掉任意Key
- 總結
- 參考文獻
前言
紅黑樹，是一個高效的二叉查找樹，其定義特性保證了樹的路徑長度在黑色節點上完美平衡，使得其查找效率接近于完美平衡的二叉樹，
但是紅黑樹的實作邏輯很復雜，各種旋轉，顏色變化，直接針對其分析，大多數都是死記硬背各種例子，不太容易有個直觀的理解，實際上，紅黑樹是實作手段，是其他概念模型為了方便在二叉樹上實作進而定義的節點顏色這個資訊，如果從概念模型入手，再一一對應，就容易理解的多了，而紅黑樹能夠對應的模型有2-3樹，2-3-4樹等，下面我們會以2-3-4樹作為概念模型，對紅黑樹進行分析，
2-3-4樹
2-3-4樹是對完美平衡二叉樹的擴展，其定義為：
- 在一個節點中，可以存在1-3個
key， - 2-節點，擁有1個
key和2個子節點， - 3-節點，擁有2個
key和3個子節點， - 4-節點，擁有3個
key和4個子節點， - 子節點為空的節點稱為葉子節點，
- 任意從根節點到葉子節點的路徑擁有相同的長度，即路徑上的鏈接數相同，
下圖就是一個2-3-4樹：
查找
2-3-4樹的查找很簡單，類似于二叉樹，步驟如下：
- 將查找
key和節點內的key逐一對比， - 如果命中，則回傳節點內
key的對應值， - 如果節點內的
key都不命中，則沿著合適的鏈接到下一節點重復該程序直到找到或者無后續節點，
舉個例子，如果我們要在上面的2-3-4樹中查詢11，其步驟如下：
插入
2-3-4樹的插入，不會發生在中間節點，只會在葉子節點上進行插入，
、
在葉子節點上新增key，會使得2-節點變為3-節點，3-節點變為4-節點，而原本的4-節點就沒有空間可以插入key了，為了解決這個問題，可以將4-節點中間的key推送給其父節點，剩下的2個key形成2個2-節點，效果如下
通過將4-的葉子節點拆分，產生了新的葉子節點可供key插入，同時將中間key送入父節點，該操作不會破壞樹的平衡性和高度，但如果葉子節點的父節點也是4-節點，這個操作就無法進行了，為了解決這個問題，有兩種思路：
- 自底向上，從4-葉子節點開始分裂，如果分類后其父節點也是4-節點，繼續向上分裂，直到到達根節點，如果根節點也是4-節點，分裂后樹的高度+1，
- 自頂向下，從根節點到插入所在的葉子節點路徑上，遇到4-節點就將其分裂，
兩種方法都能解決問題，不過自頂向下不需要遞回，實作起來更簡單，通過這種處理方式，確保了1）最后到達的葉子節點必然是2-或者3-節點，搜索路徑上不存在4-節點，
樹的生長
2-3-4樹是向上生長的，這句話可以從根節點的分裂理解：如果根節點是一個4-節點，當新增key時，根節點會分裂，將中間的key推入父節點，根節點沒有父節點，因此中間的key就會成為新的根節點，如下所示：
整顆樹的生長可以看成是葉子節點不斷的新增key，并且在成為4-節點后被下一次的新增動作分解為2個2-節點，同時將一個key送入父節點，隨著這個程序的不斷進行，不斷有key從葉子節點向根節點匯聚，直到根節點成為4-節點并在下一次新增時被分類，進而讓樹升高1，
洗掉
洗掉是整個操作中最為復雜的部分，因為洗掉可能發生在任意節點上，并且洗掉后可能破壞2-3-4樹的完美平衡，在這里，我們先來處理一些簡單的情況，最后再思考可以推而廣之的策略，
洗掉最大key
在2-3-4樹中，洗掉最大key必然是最右邊的葉子節點上，如果葉子節點是3-節點或者4-節點，只需要將其中最大的key洗掉即可，不會對樹的平衡性造成影響，但如果洗掉的key在2-節點上，情況就變得麻煩，因為洗掉2-節點，導致樹的平衡被破壞，為了避免這個情況的發生，不能讓洗掉發生在2-節點上，
為了讓洗掉不落在2-節點上，可以將2-型別的葉子節點（最終要洗掉的那個），從其兄弟節點“借”一個key進行融合變成3-節點；也可以將父節點的key和兄弟節點的key融合，變成一個4-節點，主要保證變化程序中樹的平衡性不被破壞即可，變換完成之后的節點型別是3-或4-，自然就可以成功洗掉了，變化的可能情況有：
變化的策略是：
- 將父節點的
key，自身的key，兄弟節點的key的合并后形成一個邏輯節點， - 變化一：新節點為4-節點的情況下，父節點還有key，則新節點替換目標節點；
- 變化二：新節點為5-節點的情況下，最小
key還給兄弟節點，次小key還給父節點，剩余2個key設定到目標節點， - 變化三：新節點為6-節點的情況下，最小
key還給兄弟節點，次小key還給父節點，剩余3個key設定到目標節點，
向下的搜索，最終達到需要洗掉key的葉子節點，葉子節點的兄弟節點無法控制，而如果能保證目標key所在的葉子節點的父節點不是2-節點，就可以安全洗掉key而不會破壞樹的結構，因此，在自頂向下的程序中，非根節點如果為2-節點，則通過變化成為非2-節點，這個轉化，僅僅針對搜索路徑的下一個節點而言，因此可能出現節點1被轉化為非2-節點后，其子節點是2-節點，子節點轉化為非2-節點時將父節點（節點1）恢復成2-節點，轉化的最終目的是為了保證葉子節點的父節點是非2-節點即可，只不過為了達成這個保證，整個轉化行為需要從根節點一直進行下去，因此如果在葉子節點的時候執行轉化可能會導致子樹高度減1，這種變化會影響到全域樹的平衡，就需要回圈向上迭代到根節點，比較復雜，而從根節點開始一路轉化下去，則容易理解和實作，也不會影響樹的平衡，
通過執行這種變化，在葉子節點中，就可以安全洗掉key，
洗掉最小key
最小key的洗掉思路和操作方式和洗掉最大key相似，只不過搜索路徑的方向是最左而已，其節點變化策略也是相似的，具體的變化有以下幾種：
變化的策略是：
- 將父節點的
key，自身的key，兄弟節點的key的合并后形成一個邏輯節點， - 變化一：新節點為4-節點的情況下，父節點還有key，則新節點替換目標節點；
- 變化二：新節點為5-節點的情況下，最大
key還給兄弟節點，次大key還給父節點，剩余2個key設定到目標節點， - 變化三：新節點為6-節點的情況下，最大
key還給兄弟節點，次大key還給父節點，剩余3個key設定到目標節點，
洗掉任意key
洗掉任一key就變得比較麻煩，key可能出現在中間節點上，洗掉的話，樹的結構就被破壞了，這里，我們可以采用一個取巧的思路：如果洗掉的key是樹的中間節點，將該key替換為其中序遍歷的后繼key；該后繼key是洗掉key的節點的右子樹的最小key，
key的替換對樹無影響；而將替換key洗掉，則轉換為洗掉對應子樹最小Key的問，洗掉最小Key，需要從根節點自頂向下變化2-節點才能保證葉子節點中key的成功洗掉，因此，洗掉任一Key的具體處理思路可以總結為：
- 從根節點開始自頂向下搜索，非根節點如果為2-節點，則通過變化成為非2-節點，
- 搜索發現目標key，將其替換為中序搜索后繼key，
- 洗掉步驟2節點的右子樹最小key，
左傾紅黑樹
2-3-4樹是一種概念模型，直接按照這個概念模型用代碼實作則比較復雜，主要的復雜有：
- 維持3種節點型別，
- 多種節點型別之間需要互相轉換，
- 在樹中移動需要進行多次比較，如果節點不是2-節點的話，
因此在表現形式上，我們將2-3-4樹換另外一種形式來展現，進行以下變換：
- 將2-3-4樹用二叉樹的形式表現，
- 節點之間的鏈接區分為紅色和黑色，紅色鏈接用于將節點鏈接起來視作3-節點和4-節點，
這種轉換的關鍵點在于：
- 轉換后的二叉樹可以使用二叉樹的搜索方式，
- 轉換后的二叉樹和2-3-4樹處于一致關系，改變的只是表現形式，
不過由于3-節點兩種表現形式，增大了復雜性，因此對變換要求增加一條：紅色鏈接只能為左連接，通過三個約束后，轉換得到二叉樹我們稱之為左傾斜紅黑樹，其關鍵特性有：
- 可以使用二叉樹搜索方式，
- 與2-3-4樹保持一一對應，
- 紅黑樹是黑色鏈接完美平衡的，也就是從根節點到葉子節點的任意路徑上，黑色鏈接的數量一致，
其對應方式如下：
可以看到，如果將紅色鏈接放平，就和2-3-4樹在展現上一致了，2-3-4樹是完美平衡的，其對應的左傾斜紅黑樹是黑色鏈接完美平衡，因為紅色鏈接是用于3-節點和4-節點的；而黑色鏈接就對應2-3-4樹中的鏈接，
左傾斜紅黑樹的轉換中不允許2種形式：
- 右傾斜的紅色鏈接，
- 兩個連續的紅鏈接在一個搜索路徑中（從根到葉子節點的路徑）
形象的說以下幾種不允許：
禁止的情況，減少了需要考慮的情形，為后續的編碼實作降低了難度，對于上述定義的左傾斜紅黑樹，使用資料結構來表達的話，在原本的二叉樹的節點中，增加一個屬性color，用于表示指向該節點的鏈接的顏色，
public class RedBlackTree
{
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root; // root of the BST
private int heightBLACK; // black height of tree
private class Node
{
`key` `key`; // `key`
Value value; // associated data
Node left, right; // left and right subtrees
boolean color; // color of parent link
private int N; // number of nodes in tree rooted here
private int height; // height of tree rooted here
Node(`key` `key`, Value value)
{
this.`key` = `key`;
this.value = https://www.cnblogs.com/jfire/p/value;
this.color = RED;
this.N = 1;
this.height = 1;
}
}
}
查找
紅黑樹的查找和二叉樹的一致，但是會更加快速，因為紅黑樹是黑色平衡的，搜索長度得到了控制，
插入
在介紹插入實作之前，首先要介紹紅黑樹中的兩種旋轉操作：
- 右旋：將一個左傾斜的紅鏈接轉化為右鏈接，
- 左旋：將一個右傾斜的紅鏈接轉化為左連接，
這兩個操作的重要性在于其變化是區域的，不影響黑色連接的平衡性，其變化如下：
紅黑樹的插入和二叉樹插入是相同的，只不過新增的鏈接是紅色的，因為紅黑樹的概念模型是2-3-4樹，2-3-4樹新增節點是在葉子節點上，并且新增后必然成為3-節點或者4-節點，所以新增鏈接均為紅色，
在新增完畢后，根據紅鏈接具體情況，進行旋轉處理，以保持左傾斜紅黑樹的要求，可能出現的情況有：
- 在2-節點上新增
key，表現在紅黑樹上，就是一個黑色的節點新增左連接或者右連接 - 在3-節點上新增
key，表現在紅黑樹上，就是被紅鏈接相連的兩個節點上3個可新增連接的地方新增紅鏈接，
2-節點的情況如下所示：
3-節點的情況如下所示：
左旋和右旋的方法如下：
private Node rotateLeft(Node h)//將節點的右紅鏈接轉化為左鏈接，并且回傳原本節點的子樹轉化后新的子樹的根節點
{
Node x = h.right;
h.right = x.left;
x.left = setN(h);
x.color = x.left.color;
x.left.color = RED;
return setN(x);//該方法用于計算節點x的子樹內的節點數量以及高度
}
private Node rotateRight(Node h)//將節點的左紅鏈接轉化為右鏈接，并且回傳原本節點的子樹轉化后新的子樹的根節點
{
Node x = h.left;
h.left = x.right;
x.right = setN(h);
x.color = x.right.color;
x.right.color = RED;
return setN(x);
}
在2-3-4樹的節點插入中，為了避免葉子節點是4-節點導致沒有空間插入，所以從根節點到葉子節點的搜索路徑中，采用自頂向下的4-節點分解策略，而在紅黑樹中，對4-節點的分解動作是通過對節點的顏色變化完成的，如下圖所示：
翻轉的程序很簡單，就是將節點，節點的左右孩子節點的顏色都進行調整即可，顏色翻轉的代碼如下
private void colorFlip(Node h)
{
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}
4-節點的分解帶來的效果是將紅色鏈接向上層移動，這個移動可能產生一個紅色的右鏈接，此時需要通過左旋來修正；或者產生2個連續的紅鏈接，此時需要將其右旋，形成一個符合定義的4-節點，
總結來說，插入的程序首先是自頂向下，遇到4-節點就進行分解，直到到達葉子節點插入新的key；由于向下程序的4-節點可能產生右傾斜的紅鏈接，或者連續的2個紅鏈接，因此需要從葉子節點處向上到達根節點，修復產生的這些問題，處理方式主要是：
- 右傾斜的紅鏈接左旋，
- 連續的紅鏈接，通過右旋來達到符合定義的4-節點，
按照上述的總結，我們可以將新增節點的方法實作為
private Node insert(Node h, `key` `key`, Value value)//將KV對插入以h節點為根節點的樹，并且回傳插入后該樹的根節點
{
if (h == null)//尋找到空白鏈接，回傳新的節點，該節點為紅色鏈接指向的節點，
{
return new Node(`key`, value);
}
if (isRed(h.left) && isRed(h.right))//自頂向下的程序中，分裂4-節點，
{
colorFlip(h);
}
if (eq(`key`, h.`key`))
{
h.value = https://www.cnblogs.com/jfire/p/value;
}
else if (less(`key`, h.`key`))
{
h.left = insert(h.left, `key`, value);
}
else
{
h.right = insert(h.right, `key`, value);
}
if (isRed(h.right))//右傾斜的紅色鏈接，進行左旋，
{
h = rotateLeft(h);
}
if (isRed(h.left) && isRed(h.left.left))//連續的紅色鏈接，右旋變化為符合定義的4-節點
{
h = rotateRight(h);
}
return setN(h);
}
洗掉
和概念模型相同的方法，我們首先嘗試實作洗掉最大key和洗掉最小key，之后通過替換key位置來實作洗掉任意Key功能，
洗掉最大Key
和概念模型相同，洗掉要發生在非2-節點上才能保證樹的平衡不被破壞，這就意味著洗掉一定要發生在一個被紅色鏈接相連的節點上，概念模型當中，在自頂向下搜索程序需要保證中間節點不是2-節點來使得葉子節點必然可以轉化為非2-節點進行安全洗掉；反應在紅黑樹中，搜索路徑的下一個節點，必須要被紅色鏈接相連，如果不是的話，則要進行變化，具體的手段包括：
- 當前節點有左傾斜紅色鏈接時，將其進行右旋，右旋可以從概念模型上理解，可以認為搜索路徑是進行到3-節點或4-節點，并且從小
key搜索到大key， - 搜索路徑的下一節點為2-節點，轉化為非-2節點，這個轉化程序，參考概念模型中的做法，將當前節點的
key，右子節點的key，左子節點的key先合并，產生紅鏈接相連的邏輯節點，之后按照概念模型的拆分方式進行拆分，
針對步驟二，我們做下具體的分析，
當前節點不是2-節點，且3-節點的紅色左連接被轉化為右鏈接，因此在下一個節點為2-節點的情況下，當前節點必然是被右傾斜紅鏈接指向，所示初始狀態可能如下：
對于情況一，我們只需要對節點20進行顏色翻轉，就可以讓其后繼節點變為紅色，也就是鏈接變紅，即可，這種轉換對應概念模型中的變化1，
對于情況二，比較復雜，首先我們需要對節點20進行顏色翻轉，此時節點10和20在一行路徑上，對節點20的左連接右旋，右旋之后節點10變為新的根節點，對齊進行顏色翻轉，整個程序如下
這種轉換對應概念模型中的變化2，
情況三和情況二可以采用完全相同的變化步驟，轉換方式對應概念模型中的變化3，如下圖所示：
綜合情況一、二、三，我們可以將變換的代碼撰寫為
private Node moveRedRight(Node h)
{
colorFlip(h);//先翻轉
if (isRed(h.left.left))//此時為情況二或者三
{
h = rotateRight(h);
colorFlip(h);
}
return h;
}
結合紅鏈接右旋和轉換2-節點，我們可以將洗掉最大key的代碼撰寫如下：
public void deleteMax()
{
root = deleteMax(root);
root.color = BLACK;//如果根節點右子節點為2-節點，翻轉root節點會導致其顏色變紅，不符合定義，因此洗掉完成后，將顏色恢復為顏色，
}
private Node deleteMax(Node h)//洗掉h節點為根節點的子樹中的最大節點，并且回傳洗掉后的子樹的根節點
{
if (isRed(h.left))
{
h = rotateRight(h);
}
if (h.right == null)//沒有右子樹了，洗掉該節點
{
return null;
}
if (!isRed(h.right) && !isRed(h.right.left))//右子節點為2-節點，進行變化程序，
{
h = moveRedRight(h);
}
h.right = deleteMax(h.right);
return fixUp(h);
}
private Node fixUp(Node h) //修正可能存在的例外鏈接情況，
{
if (isRed(h.right))
{
h = rotateLeft(h);
}
if (isRed(h.left) && isRed(h.left.left))
{
h = rotateRight(h);
}
if (isRed(h.left) && isRed(h.right))
{
colorFlip(h);
}
return setN(h);
}
這個實作中引入了一個之前未曾提到的方法fixUp，因為在洗掉的程序自頂向下的變換會產生一些不符合定義的鏈接情況：比如右傾斜的紅鏈接，比如連續的紅鏈接，在洗掉完畢后，需要沿著之前的搜索路徑，自底向上，進行例外鏈接修復，
洗掉最小Key
洗掉最小Key的思路和洗掉最大Key的思路非常接近，只不過在于搜索的方向不同，是沿著左子節點一直向下搜索，相比于洗掉最大Key，洗掉最小Key在搜索路徑向下的程序中不需要對紅鏈接方向進行旋轉，當搜索路徑的下一節點存在2-節點時轉化為非2-節點，可能存在的初始情況如下圖：
情況一很簡單，只需要對節點20進行顏色翻轉，該變換對應概念樹中的變化1，
對于情況二，先對節點20進行翻轉，再對節點30的左連接右旋，再對節點20的右鏈接左旋，最后對頂點進行翻轉，流程如下圖所示：
該變換對應概念模型中的變化2，
對于情況三則更復雜一些，其對應概念模型中的變化3，流程如下
和洗掉最大key不同的地方在于情況三無法復用情況2的操作，否則會產生一個右傾斜的紅鏈接，不過即使是右傾斜紅鏈接，仍然是黑色平衡，但是與左傾斜紅黑樹定義不吻合，所以情況三使用了更多的步驟來產生符合定義的紅黑樹，
結合上述程序，我們可以將洗掉最小Key的代碼撰寫如下
public void deleteMin()
{
root = deleteMin(root);
root.color = BLACK;
}
private Node deleteMin(Node h)
{
if (h.left == null)
{
return null;
}
if (!isRed(h.left) && !isRed(h.left.left))
{
h = moveRedLeft(h);
}
h.left = deleteMin(h.left);
return fixUp(h);
}
private Node moveRedLeft(Node h)
{
colorFlip(h);
if (isRed(h.right.left))
{
if (isRed(h.right.right))
{
h.right = rotateRight(h.right);
h = rotateLeft(h);
h = rotateLeft(h);
h.left = rotateRight(h.left);
colorFlip(h);
}
else
{
h.right = rotateRight(h.right);
h = rotateLeft(h);
colorFlip(h);
}
}
return h;
}
洗掉任意Key
和概念模型的洗掉操作相似，自頂向下搜索，按照key的比較結果，可能向左右任意方向前進，如果下一步是一個2-節點，則參照洗掉最大最小key中的變化方式進行變化，在確定key所在的節點后，將該key值替換為中序遍歷的后繼節點，繼而洗掉該節點右子樹的最小節點，代碼如下
public void delete(Key key)
{
root = delete(root, key);
root.color = BLACK;
}
private Node delete(Node h, Key key)
{
if (less(key, h.key))
{
if (!isRed(h.left) && !isRed(h.left.left))
{
h = moveRedLeft(h);
}
h.left = delete(h.left, key);
}
else
{
if (isRed(h.left))
{
h = rotateRight(h);
}
if (eq(key, h.key) && (h.right == null))
{
return null;
}
if (!isRed(h.right) && !isRed(h.right.left))
{
h = moveRedRight(h);
}
if (eq(key, h.key))
{
h.value = https://www.cnblogs.com/jfire/p/get(h.right, min(h.right));
h.key = min(h.right);
h.right = deleteMin(h.right);
}
else
{
h.right = delete(h.right, key);
}
}
return fixUp(h);
}
總結
紅黑樹作為概念樹的實際實作，其代碼很復雜，要求的變化方式也很多，從概念樹的映射來說，2-3樹，2-3-4樹都可以映射到紅黑樹上，而左傾斜紅黑樹，使用遞回方式實作的代碼，無疑是很好理解，代碼量也較少的，而JDK中TreeMap采用概念模型也是2-3-4樹，不過并不限制右傾斜，總體而言，紅黑樹有太多變種，了解其原理最為重要，實作上，能使用即可，深究的話，意義不大，
參考文獻
《Left-Leaning Red-Black Trees》（Princeton University）
文章原創首發于公眾號：林斌說Java，轉載請注明來源，謝謝，
更多高質量原創文章，歡迎掃碼關注
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/35282.html
標籤：架構設計