二嬸三分四樹

二嬸三分四樹佇計算機科學中是階為四的 B 樹。

大體同 B 樹，二嬸三分四樹是一種自平衡資料結構，通好用著實作字典。伊會當佇咧 $ { \ text { O } } ( \ log n ) $ 時間內查揣、插入去攏共刪除，遮的 _ n _ 是樹中元素的數目。

二嬸三分四樹佇多數程式語言當中實現起來相對困難，因為佇樹仔頂的操作牽涉大量特殊情況。紅烏樹實現起來會閣較簡單一寡，所以伊會用得用伊來代替。

背景

二嬸三分四樹共數據存儲佇咧叫做 _ 元素 _ 的單獨單元內底。𪜶組合成 _ 節點 _，逐个節點攏是下列之一

• 二-節點，就是講乎，伊包含一个元素佮兩个子節點，
• 三-節點，就是講乎，伊包含兩个元素佮三个子節點，
• 四-節點，就是講乎，伊包含三个元素佮四个子節點。

逐个子節點（可能為空啦）攏是一个子二交三分四樹。_ 根 _ 節點是其中無父親的彼个節點；伊佇咱遍歷樹的時陣充當起點，因為對伊會當到所有的其他節點。_ 葉仔 _ 節點是有上少一个空仔節點的節點。

仝 B 樹仔仝款，二嬸三分四樹是 _ 有序的 _：逐个元素著愛大於抑是等於伊倒爿的佮伊的倒爿樹仔的任何其他元素。每一个子節點因此成為著伊的左佮正元素界定的一个區間。

二嬸三分四樹是紅烏樹的一種等同，這意味著𪜶是等價的資料結構。嘛會使講，對逐家二交三分四樹，攏有上無一个數據元素是仝款次序的紅烏樹。佇咧二五三分四樹頂頭的插入佮刪除操作也等價佇咧紅烏樹內底的色水反轉佮踅轉。這會當予伊成做理解紅烏樹背後的邏輯的重要工具。