2-3-4樹

定義

1. 所有的葉子節點都擁有相同的深度
2. 節點只能是2-節點,3-節點,或者4-節點
   1. 2節點 包含一個元素的節點,有兩個子節點
   2. 3節點 包含兩個元素的節點,有三個子節點
   3. 4節點 包含三個元素的節點,有四個子節點
3. 所有節點都有至少兩個子節點或沒有子節點

來解釋一下性質和一些定義

1. 任意一個葉子節點(也就是沒有子節點的節點)到根節點的距離一致
2. 一個節點中可能包括1,2,3個元素,有2,3,4,個子節點,具體可以看下面的圖
3. 一個節點要么有至少兩個子節點,要么沒有節點

關于子節點如何定義的

• 2節點 左子樹所有元素小于key1,右子樹所有元素大于key1
• 3節點 左子樹所有元素小于key1,中間子樹所有元素大key1小于key2,右子樹大于key2
• 4節點 左子樹所有元素小于key1,第二個子樹所有元素大于key1小于key2,第三個子樹所有元素大于key2小于key3,右子樹所有元素大于key3

為什么要提到234樹呢,因為234樹和紅黑樹是完全等價的,在程式中實作234樹比較繁瑣,所以使用了紅黑樹來代替

來看234樹的添加操作

添加如果出現需要分裂的情況,分裂出的元素首先進行和父級合并,如果父級已經是4節點那么將父級分裂,遞回操作

234樹的生長全部都是從葉子節點進行生長的,從葉子節點進行分裂向上延伸

紅黑樹

性質

1. 每個節點要么紅色,要么黑色
2. 根節點是黑色
3. 每個子節點 (NIL) 是黑色
4. 每個紅色節點的兩個子節點一定是黑色
5. 任意一節點到每個葉子節點的路徑都包含數量相同的黑節點

解釋一下性質

性質4和性質5說一下

如果一個紅色節點那么它的兩個子節點必須為黑色,包括nil節點,也就是說不能有兩個紅色節點相連

任意一個葉子節點或沒有子節點的節點到根節點經過的黑色節點數量都一致,不懂下面再解釋

葉子節點 : 標記為NIL,為虛擬節點,顏色必須為黑色,234中葉子節點為沒有子節點的節點,而紅黑樹的葉子節點是虛擬的節點

234樹和紅黑樹對比

3節點的兩種形態如果紅色在左邊就叫做左傾,紅色在右邊就叫做右傾

將234樹進行轉換為紅黑樹操作

右傾

左傾

現在來看一下幾個沒有子節點的節點下面其實都有兩個NIL節點我們可以任意從一個nil節點出發,到6根節點,所經過的黑色節點個數是一樣的,一般情況下NIL節點是不畫出來的,但是不代表不存在

紅黑樹操作

變色：節點的顏色由黑變紅或者由紅變黑

左旋：以某個節點作為旋轉點，其右子節點變為旋轉節點的父節點，右子節點的左子節點變為旋轉節點的右子節點，左子節點保持不變，

右旋：以某個節點作為旋轉點，其左子節點變為旋轉節點的父節點，左子節點的右子節點變為旋轉節點的左子節點，右子節點保持不變

看圖!

右旋操作

左旋操作

新增節點

對比234樹進行添加

紅黑樹所有添加的節點默認都為紅色

1 添加一個根節點

添加第一個默認為紅色的節點,發現與紅黑樹性質"根節點必須為黑色"沖突,我們將5變色為黑色即可,完成添加操作

2 添加一個節點,與2節點合并

3 添加一個節點,與3節點合并

根據234樹轉紅黑樹的兩種狀態導致添加時可能會出現兩個紅色節點相連的情況

左傾通過選轉和變色可以變成右傾的狀態,反之亦然

4 添加一個節點和4節點合并

我們回到3和4,其中有需要調整的樹

對于3里面的兩種情況,看234樹和紅黑樹的對比,4節點的紅黑樹形態是上面黑色節點左右兩邊各一個紅色節點,而現在是三個元素一條線,上面黑色節點,下面兩個紅色,我們已經知道它的最終形態是什么樣子,只需要進行調整即可

而對于上面的添加還有一種情況需要旋轉兩次,解決思路就是變換為上面的情況,然后按照上面的步驟完成

而4里面的情況,進行變色即可

如果經過變色爺爺節點變色為紅色,假設不是根節點的話,與上面的其他節點發生沖突,我們把變色的爺爺節點當做新增的節點進行操作

如果爺爺節點的父親節點和叔叔節點都為紅色則繼續按照上面的操作進行調整,如果叔叔節點不是紅色則需要進行其他調整

例如下圖,如果4的叔叔節點為紅色,那么直接根節點變黑(先變紅發現是根節點然后變黑)即可,如果叔叔節點為黑色,那么就需要進行旋轉變色操作

紅黑樹在線演示網站

洗掉節點

前驅節點和后繼節點

洗掉一個節點肯定有人要替代被洗掉節點的位置,可以選擇前驅節點或后繼節點

前驅節點 : 小于當前節點的最大節點

后繼節點 : 大于當前節點的最小節點

例如 下面圖的6節點,前驅節點就是5,后繼節點就是9

除非左子樹或右子樹只有一個節點

尋找前驅節點就是尋找左子樹的第一個節點的右兒子,一直往右找直到找到沒有右子節點的節點

尋找后驅節點就是尋找右子樹的第一個節點的左兒子,一直往左找直到找到沒有左子節點的節點

洗掉一個節點可以理解為洗掉它的替換節點

為什么這么說呢,如果使用代碼實作紅黑樹,一個節點至少有3個指標,左孩子指標,右孩子指針,父親指標,節點中假設就存盤一個值,那么移除原來的節點替換為新的節點需要移動:左右孩子指標,父指標,替換的左右孩子指標,左右孩子的父指標.........

而我們將替換的節點的值賦值給需要洗掉的節點,還是上面那個圖,假如我們洗掉10,使用后繼節點11來替代,我們只需要將11的值賦值給10,然后洗掉11節點即可,也就是說只需要修改兩個指標,11的父指標和12的左孩子指標即可完成

而在234樹中,洗掉的永遠都是葉子節點,可以看上面的圖,前驅節點和后繼節點用于都是在最底層

那么我們洗掉的情況從是否有孩子來看就只有兩種

1. 洗掉沒有孩子的節點
2. 洗掉有一個孩子的節點

為什么沒有2個孩子的情況呢?如果洗掉一個節點來尋找它的替換節點,那么要么是前驅或后繼,而這兩個節點的條件是一直尋找左邊孩子或右邊孩子,如果一個節點有兩個孩子,那么它肯定不是一個前驅或后繼節點

后繼節點同理,如果一個前驅節點或后繼節點有兩個子節點,那么它一定不是前驅節點或后繼節點

前驅或后繼節點從葉子節點開始的層數不會大于2

那還有個疑問,會不會出現下面這種情況,10的后繼節點12這都3層了,不是說不會大于2嗎

這種情況存在嗎?現在都知道紅黑樹是234樹轉換來的,那么234樹中會出現一個節點只有一個孩子的情況嗎?

234樹的生長都是從葉子節點進行分裂的,也就是說除了葉子節點,就是說最少的子節點也就是兩個,最多4個,不可能出現上圖的情況,兩個子節點的節點為2-節點,2節點除了第一次添加為根節點或葉子節點以外,任何2-節點都會連接兩個子節點,而兩個子節點肯定是2,3,4節點其中之一,轉換紅黑樹不可能出現上圖情況,可以回去看看234樹轉換紅黑樹對應圖

那么下面開始進行洗掉

先在234樹上進行洗掉

可以直接進行洗掉的有4,11,13,其中4和5比較特殊,如果進行的是右傾操作,那么可以直接洗掉5

在234樹洗掉操作中3-節點和4-節點是可以自己搞定的,例如洗掉4或5, 11或12或13,隨便洗掉一個都不影響234樹的性質

而在紅黑樹中洗掉只能洗掉234樹對應的3-節點和4節點中紅色節點,這幾個節點可以直接洗掉,不需要任何額外操作

在紅黑樹中洗掉5只需要將4替換掉5,然后進行變色即可,紅黑樹的性質依然保持

洗掉

情況1,自己能搞定,對應234樹當前要的洗掉3-節點或4-節點

1. 葉子節點

   例如是234樹中的紅色葉子節點或紅黑樹中沒有子節點的紅色節點直接洗掉

   例如上圖的紅黑樹中4,11,13節點,可以直接洗掉

2. 有一個子節點

   使用子節點來替代,如果需要進行變色

   例如上圖的紅黑樹中5節點,洗掉后4節點替代自己,然后變黑色,而12節點可以找左兒子或右兒子都可以替換自己

情況2 自己搞不定,需要兄弟節點和父親節點幫忙

兄弟節點為3-節點的情況

例如現在想要洗掉5,這時候就需要兄弟節點和父節點幫忙

首先將5洗掉,之后需要從兄弟節點拿來一個節點來彌補空缺,但是兄弟節點都比6大,如果直接放入無論是234樹還是紅黑樹都會違反性質,234 : 3-節點的左子樹元素全部小于key1 ,紅黑樹: 任何一個節點左邊都是小于當前節點

這時我們把父親節點用來彌補洗掉的空缺

之后兄弟節點去彌補父節點的空缺

那么回到紅黑樹呢?

為什么會出現這種情況呢?我們回想一下234樹轉換紅黑樹的圖,在234樹中一個3-節點可能出現左傾或右傾的情況

上面是6在上面10在下面的情況,我們換成相反的情況來看看

這時5的兄弟節點就和234樹中的一樣了,234樹的3-節點轉換為紅黑樹的兩種情況都可以通過左旋變色或右旋變色進行變化

例如上圖,我們6和8節點進行右旋,就會變成上面第二張圖,而上面的第二張圖6節點和8節點進行左旋又會變成上面的這張圖

有沒有發現一個問題呢,當紅黑樹5節點的兄弟節點為黑色時也就是說明它的兄弟節點和234樹中5節點的兄弟節點一致

也就是說如果它的兄弟節點為紅色,需要先進行旋轉變色才能進行洗掉,而6和8變色在234樹上等于沒動,因為234樹根本就沒有顏色,只是為了方便對比紅黑樹添加的顏色

上面的圖還有一種情況,就是3-節點7和8位置反的,8在上面7在下面,而替代需要兄弟節點中最小的元素來替代,如果出現這種情況需要先將7和8進行旋轉換色,成為上面的情況,然后再進行替換

再來看兄弟節點為4-節點的情況

還是洗掉5節點,離它最近的兄弟節點是個4-節點

兄弟節點為4-節點的洗掉

只畫需要修改的地方,先來看234樹

紅黑樹

還有一種方法

而對應紅黑樹就比較簡單了

最后關于變色為什么不是8和9變成黑色,因為紅黑樹必須保證每個葉子節點到根節點經過黑色節點個數相同,同時保證沒有兩個紅色節點相連,如果是8和9變成黑色,為了第一條那么6和7必須變為紅色,而變成紅色就違反了第二條,上面的洗掉第一種操作最后的變色同理,如果7和9為黑色,那么從9的葉子節點出發將會比從7的葉子節點多一個黑色節點,違反了紅黑樹的性質

看個動圖加深記憶

這里使用的是第二種洗掉方式,因為可以少旋轉一次

情況3,自己解決不了,兄弟節點也幫助不了(兄弟節點也沒有子節點)

如果父親不是紅色節點呢?沒有辦法補償失去的黑色節點?那么就需要往上面將父節點的兄弟節點變為紅色,來彌補爺爺節點的黑色平衡,然后將爺爺節點的父節點變黑,但是,如果爺爺節點的父節點也是黑色,那么就需要遞回往上進行操作,知道找到父節點不為黑色的節點

進行上面操作后再根據洗掉節點的父節點,把父節點當做要洗掉的節點(并不真正洗掉),根據上面情況進行調整

本文僅個人理解,如果有不對的地方歡迎評論指出或私信,謝謝?(?>?<?)?

標籤：其他

上一篇：屬于線性代數，在深度學習領域的主要概念

下一篇：B樹的進化版----B+樹