我最近學習了 B 樹，據我所知，一個節點可以有最小t-1鍵和最大2t-1鍵給定最小度數t。例外是 root 甚至可以有 1 個密鑰。
這是來自 CLRS 第 3 版圖 18.7（第 498 頁）的示例，其中t=3
最小鍵 = 3-1 = 2
最大鍵 = 2*3-1 = 5
在d)示例中，當插入 L 時，為什么在當前不違反 B 樹屬性的情況下拆分根（它有 5 個鍵，這是允許的最大值）。
為什么不考慮將 L 插入 [JKL] 而不拆分 [GMPTX]。
當它達到最大值時我應該總是分裂根嗎？
uj5u.com熱心網友回復：
B樹的插入演算法有幾種變體。在這種情況下，插入演算法是“單次向下樹”變體。
此變體的背景在第 493 頁給出：
由于我們無法將密鑰插入到已滿的葉節點中，因此我們引入了一種操作，將完整節點 ??（具有 2?? - 1 個密鑰）圍繞其中間密鑰 ??：密鑰??分成兩個節點，每個節點只有 ?? - 1 個密鑰。中值鍵向上移動到 ?? 的父節點，以識別兩棵新樹之間的分界點。但是如果??的父節點也是滿的，我們必須在插入新鍵之前將其拆分，因此我們最終可能會在樹上一直拆分滿節點。
與二叉搜索樹一樣，我們可以在從根到葉的單次傳遞中將鍵插入 B 樹。為此，我們不必等待確定是否真的需要拆分一個完整節點才能進行插入。相反，當我們沿著樹搜索新鍵所屬的位置時，我們會拆分沿途到達的每個完整節點（包括葉子本身）。因此，無論何時我們想要拆分一個完整節點??，我們都可以確保它的父節點未滿。
換句話說，這種插入演算法將比可能嚴格需要的更早地拆分節點，以避免在回溯遞回時必須拆分節點。
該演算法在第 495 頁用偽代碼進一步描述。
這解釋了為什么在插入 L 時，根節點會在任何遞回呼叫之前立即被拆分。
替代演算法不會這樣做，并且會將分裂延遲到不可避免的程度。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/523840.html
標籤：算法数据结构树b树
上一篇：從陣列陣列創建嵌套物件陣列