平衡如何平衡B-樹

Question

說我有一個B-Tree，其中有3-4個配置的節點（3個元素和4個指針）。假設我按照規則合法地構建樹，是否有可能達到層中有兩個節點並且一個節點有4個退出指針而另一個節點只有兩個退出指針的情況？

在一般情況下，做什麼保證我作爲一個使用得當的平衡性B樹

Answer 1

平衡背後的想法（一般平衡樹的數據結構）是在任意兩點間深處的區別子樹是零個或一個（取決於樹）。換句話說，用於查找葉節點的比較數總是相似的。

所以是的，你可以在你描述的情況下結束，只是因爲深度是相同的。每個節點中的元素數量不是天平的問題（但請參見下文）。

這是即使在比右左節點更多的項目（NULL指針未顯示）完全合法：

    +---+---+---+ 
       | 8 | | | 
       +---+---+---+ 
     ________/ | 
    /   | 
     |    | 
+---+---+---+ +---+---+---+ 
| 1 | 2 | 3 | | 9 | | | 
+---+---+---+ +---+---+---+ 

然而，這是非常不尋常有3-4 B樹（有些人會實際上這是說不是一個BTree，但是其他一些數據結構）。

在BTrees中，每個節點（例如4-5樹）中通常都有最多偶數個鍵，以便拆分和組合更容易。使用4-5樹，節點填滿時推薦哪個鍵的決定很容易 - 它是五個中間的一個。對於3-4樹來說，這不是一個明確的問題，因爲它可能是兩個中的一個（對於四個元素沒有明確的中間值）。

它還允許您遵循節點應該包含在n和2n元素之間的規則。另外（對於「適當的」BTrees），葉節點全部位於相同的深度處，不僅在彼此之間。

如果添加以下值到一個空的B樹，你可以用的情況結束了你的描述：

Add   Tree Structure 
---   ---------------- 
1     1 

2     1,2 

5    1,2,5 

6    1,2,5,6 

7     5 
       /\ 
       1,2 6,7 

8     5 
       /\ 
       1,2 6,7,8 

9     5 
       /\ 
       1,2 6,7,8,9