二嬸三樹

電腦科學中，二–三樹伊是一種樹型的資料結構，由約翰 ・ 霍普克洛夫特於一九七空年發明。

二–三樹中的內部節點會當有兩个子節點佮一个資料的元素、抑是三个子節點佮兩个資料元素，葉仔節點有一至二个資料元素。

• *

二–三樹佮 AA 樹是等距仝構的，意味著𪜶是仝一種資料結構。嘛會使講，對每一个二–三樹，上無攏存在一款 AA 樹仔佮伊的元素排出來是仝款的。二–三樹是平衡樹，意味著正爿，倒爿，中央的子樹的元素數量攏是仝抑是接近的。

定義

若是一个內底節點有一个資料的元素、兩个囝節點，則此節點為二節點。

若是一个內部節點有兩个資料的元素、三个子節點，則此節點為三節點。

而且唯若以下講有一條成立的時陣，T 為而–三樹：

• T 為空。即 T 無包括講任何節點。
• T 為下有資料的元素 a 的二節點。若是 T 的倒手節點為 L、正手節點為 R，著：
• L 和 R 是等高的二–三樹；
• a 大於 L 中的所有資料的元素；同時
• a 等於等於 R 中的所有資料的元素。
• T 為下有資料的元素 a 和 b 的三節點，其中 a < b。若是 T 的倒手節點為 L、中子節點為 M、正手節點為 R，著：
• L、M、和 R 是等高的二–三樹；
• a 大於 L 中的所有資料的元素，並且小於等於 M 中的所有資料的元素；同時
• b 大於 M 中的所有資料的元素，並且小於等於 R 中的所有資料的元素。

操作

二–三樹的走揣元素操作和二箍搜揣樹仔的走揣類似。因為節點內底的資料元素攏是食頭路的，所以走揣函式會當對遮來進入正確的子樹來進行走揣，終其尾揣著正確的彼个節點。

進行插入操作的時，會當先通過走揣操作確定合適的所在，然後共資料插入去對應節點。若是插入去了後的彼个節點變做四節點（包含三个資料的元素）， 著愛需要節點拆做兩个二節點，中央資料的元素進入父節點。按呢來喔，該父節點嘛可能會因此變做四節點，著這个父節點嘛會拆分做兩个二節點，中央的資料元素進入該父節點的父節點，以此類推，一直到修改了後的父節點毋免分裂，抑是去予人拆分做的是根節點，現時中央資料的元素就會孤獨形成二節點，成做新的根節點。

外部連結

• 二–三 Trees Complete Description
• 二–三 Tree Java Applet
• 二–三 Tree In-depth description
• 二–三 Tree in F #
• 二–三 Tree in Python