動畫 | 什麼是2-3樹？（修改刪除操作方式）

• 2020 年 1 月 2 日
• 筆記

我們回憶一下AVL樹，它在插入和刪除節點時，總要保證任意節點左右子樹的高度差不超過1。正是因為有這樣的限制，插入一個節點和刪除一個節點都有可能調整多個節點的不平衡狀態。頻繁的左旋轉和右旋轉操作一定會影響整個AVL樹的性能，除非是平衡與不平衡變化很少的情況下，否則AVL樹所帶來的搜索性能提升不足以彌補平衡樹所帶來的性能損耗。

那有沒有絕對平衡的一種樹呢？沒有高度差也不會有平衡因子，沒有平衡因子就不會調整旋轉操作。2-3樹正是一種絕對平衡的樹，任意節點到它所有的葉子節點的深度都是相等的。

2-3樹的數字代表一個節點有2到3個子樹。它也滿足二分搜索樹的基本性質，但它不屬於二分搜索樹。

2-3樹定義

一顆2-3樹或為一顆空樹，或有以下節點組成：

2-節點，含有一個元素和兩個子樹（左右子樹），左子樹所有元素的值均小於它父節點，右子樹所有元素的值均大於它父節點；

3-節點，還有兩個元素和三個子樹（左中右子樹），左子樹所有元素的值均小於它父節點，中子樹所有元素的值都位於父節點兩個元素之間，右子樹所有元素的值均大於它父節點。

2-3樹查找元素

2-3樹的查找類似二分搜索樹的查找，根據元素的大小來決定查找的方向。要判斷一個元素是否存在，我們先將待查找元素和根節點比較，如果它和其中任意一個相等，那查找命中；否則根據比較的結果來選擇查找的方向。

2-3樹插入元素

插入元素首先進行查找命中，若查找命中則不予插入此元素，如果需要支援重複的元素則將這個元素對象添加一個屬性count。若查找未命中，則在葉子節點中插入這個元素。

空樹的插入很簡單，創建一個節點即可。如果不是空樹，插入的情況分為4種：

1. 向2-節點中插入元素；

2. 向一顆只含有一個3-節點的樹中插入元素；

3. 向一個父節點為2-節點的3-節點中插入元素；

4. 向一個父節點為3-節點的3-節點中插入元素。

向2-節點中插入元素

如果未命中查找結束於2-節點，直接將2-節點替換為3-節點，並將待插入元素添加到其中。

向一顆只含有一個3-節點的樹中插入元素

如果命中查找結束於3-節點，先臨時將其成為4-節點，把待插入元素添加到其中，然後將4-節點轉化為3個2-節點，中間的節點成為左右節點的父節點。如果之前臨時4-節點有父節點，就會變成向一個父節點為2-節點的3-節點中插入元素，中間節點與父節點為2-節點的合併。

向一個父節點為3-節點的3-節點中插入元素

插入元素後一直向上分解臨時的4-節點，直到遇到2-節點的父節點變成3-節點不再分解。如果達到樹根節點還是4-節點，則進行分解根節點，此時樹高+1（只有分解根節點才會增加樹高），下面動畫2-3樹插入會出這個例子。

動畫：2-3樹插入

2-3樹刪除

演算法4紅黑樹刪除最小鍵這一小結里沒有特別詳細地介紹，但給到了沿著左鏈接向下進行變換的三種情況：

1. 如果左子節點不是2-節點，完成；

2. 如果左子節點是2-節點，而兄弟節點不是2-節點，將兄弟節點的最小元素移到父節點，父節點的最小元素移到左子節點；

3. 如果左子節點是2-節點，而兄弟節點是2-節點，則左子結點、父節點中最小的元素和兄弟結點合併成4-結點。

刪除最小元素

我們注意到在葉子節點不是2-節點的時候，刪除一個元素是很簡單的，而且刪除時不考慮自平衡處理。如果刪除一個2-節點會留下一個空節點，破壞了2-3樹的絕對平衡。所以，為了保證不會刪除一個2-節點，可以設定最左邊或者最右邊進行向下變換節點。這裡設置沿最左邊的鏈接，進行向下變換的三種情況正是如上圖中，左子節點的父節點除了根節點都會變換成3-節點或4-節點。

刪除任意元素

刪除任意元素需要進行命中查找。如果查找未命中則忽略之；如果查找命中則像二分搜索樹刪除任意元素，將帶刪除元素右子樹的最小元素替換到待刪除元素上，然後對右子樹進行刪除最小元素。

動畫：2-3樹刪除

—–END—–