動畫 | 什么是2-3-4樹?

畫了一系列樹的動畫,從二分搜索樹,到AVL樹,再到2-3樹,再到基于2-3樹的紅黑樹,都可以發現這些樹都跟二叉查找樹很像啊。

嘿嘿!二分搜索樹就是二叉查找樹;AVL樹也是一顆二分搜索樹,只多了高度差的限制;2-3樹雖滿足二分搜索樹的性質,但不是一顆二分搜索樹,2-3樹由2-節點和3-節點組成的,滿足了完美平衡性;基于2-3樹的紅黑樹就是希望不要有3-節點,將3-節點轉換成二叉,兩個元素之間由紅鏈接相連,并約定誰是子節點誰是紅的,如下圖。

本篇文章還會繼續介紹滿足二分搜索樹性質的一棵樹,它是2-3-4樹,和2-3樹一樣也不是一顆二分搜索樹。它在2-3樹的基礎上可以存儲4-節點,4-節點由三個元素組成,有四個子樹。

查找元素

和二分搜索樹一樣,根據元素的大小來決定查找的方向。要判斷一個元素是否存在,我們首先將待查找元素和根節點逐一比較,如果它和當前節點中的一個元素相等,就返回查找命中;如果它比當前節點任一元素要大,就選擇右遞歸進行下一個節點;如果它比當前節點任一元素要小,就選擇左遞歸進行下一個節點;直到樹底下的空節點,返回查找未命中。

插入元素

我們知道2-3樹樹底下最多是3-節點,可以直接插入元素然后再判斷是否是4-節點,如果是向2-節點插入一個元素,變成3-節點無需分解;如果是向3-節點插入一個元素變成4-節點,進行向上變換將中間的鍵合并到父節點,如果父節點也變成4-節點,也接著繼續分解4-節點,直到根節點,根節點也是4-節點,也接著分解,樹高+1。

而2-3-4樹的插入算法不一樣,它沒有向上進行變換分解4-節點的過程,因為2-3-4樹可以存儲4-節點。不過插入之前,進行查找命中的時候所過路徑都要分解4-節點,如果查找未命中,則在此空節點插入一個元素;如果查找命中,說明2-3-4樹是存在這個數的,則直接返回,之前的4-節點分解就分解了,沒有必要再次合并4-節點。

插入算法同樣也需要進行分解4-節點算法,不過是由向上變換變成了向下變換。

沿著鏈接向下進行變換分解4-節點,分為三種情況:

1)4-節點作為根節點,分解;

2)父節點為2-節點,當前節點為4-節點;

3)父節點為3-節點,當前節點為4-節點。

樹底下插入一個元素只有兩種情況了:向2-節點中插入元素和向3-節點中插入元素。

動畫:插入算法

刪除元素

既然是2-3-4樹滿足二分搜索樹性質的,查找算法、插入算法和刪除算法很多都是相似的。我們回憶一下二分搜索樹的刪除算法,它在刪除任何一個非葉子節點時,都會獲取右子樹的最小葉子節點去代替待刪除元素,然后進行右子樹的刪除最小葉子節點。

所以,2-3-4樹也是一樣,先進行命中查找,如果查找命中,就獲取待刪除元素的直接后繼節點去替換待刪除元素,然后進行右子樹的刪除最小元素。不過在查找待刪除元素的同時,需要沿著左鏈接或者右鏈接向下進行變換,所過路徑分解4-節點。

刪除最小元素

從樹底下刪除一個元素,如果不是2-節點是很好刪除的,從3-節點刪除一個元素變成2-節點和從4-節點刪除一個元素變成3-節點,都不會影響整個2-3-4樹的絕對平衡性。如果從2-節點刪除一個元素,而這個2-節點只有一個元素,刪除之后這個節點變成一條空鏈接,會破壞樹的絕對平衡性。

所以在沿著左鏈接向下進行變換的時候,確保當前節點不是2-節點(除了根節點)。如果當前節點是2-節點,可以先向兄弟節點借一個位置;如果兄弟節點也是2-節點,沒法借,可以借父節點的一個位置。

但借的先后順序不能弄錯了,如果先向父節點借來一個位置,不清楚兄弟節點有多少子樹會到時候沒法分解的。例如兄弟節點是4-節點,當前節點、父節點一個位置和兄弟節點合并就變成了6-節點,比4-節點分解更加麻煩。

沿著左鏈接向下進行變換可以分為三種情況:

1)當前節點不是2-節點,跳過;

2)當前節點是2-節點,兄弟節點是2-節點,將當前節點、父節點的最小元素和兄弟節點合并成4-節點;

3)當前節點是2-節點,兄弟節點不是2-節點,將兄弟節點的最小元素移到父節點,父節點的最小元素移到當前節點(兄弟節點的最小元素要比父節點的最小元素要大,不是同一個元素)。

動畫:刪除最小算法

刪除任意元素

刪除任意元素首先要查找到這個元素,如果查找未命中則忽略之;如果查找命中,通過右子樹中序遍歷找到第一個元素(右子樹最小元素),將這個元素直接替換掉待刪除元素。

刪除任意元素除了沿著左鏈接向下進行變換,還需要沿著右鏈接向下進行變換。沿著右鏈接向下進行變換也分為三種情況,將最小元素改為最大元素:

1)當前節點不是2-節點,跳過;

2)當前節點是2-節點,兄弟節點是2-節點,將當前節點、父節點的最大元素和兄弟節點合并成4-節點;

3)當前節點是2-節點,兄弟節點不是2-節點,將兄弟節點的最大元素移到父節點,父節點的最大元素移到當前節點(父節點的最大元素要比兄弟節點的最大元素要大,不是同一個元素)。

動畫:刪除任意算法

posted @ 2020-01-11 16:10  我脫下短袖  閱讀(...)  評論(...編輯  收藏
ag二分彩