CLRS 18-2.4假設我們將密鑰{1,2，...，n}插入到一個空的B樹中，其最小度數爲2，最終的B樹有多少個節點？

Question

假設我們將密鑰{1,2，...，n}插入到一個空B樹中，其最小度數爲2，最終的B樹有多少個節點？

Answer 1

我們知道，除根以外的每個節點必須至少有t-1 = 1個鍵，並且至多2t-1 = 3個鍵。當n≥2時，最終的樹最多可以有n-1個節點。除非n = 1，否則不能有n個節點，因爲我們只將密鑰插入非空節點，所以總是會有至少一個帶有2個密鑰的節點。接下來觀察一下，我們將永遠不會有一個以上的密鑰在一個不是我們B-樹的正確脊柱的節點中。這是因爲我們插入的每個密鑰都大於存儲在樹中的所有密鑰，因此它將插入到樹的右側脊柱中。當右側脊柱中除最深節點之外的每個節點具有2個鍵並且右側樣條中最深的節點具有3個鍵時，節點數量最少。因此，在高度爲1,1節點，高度爲2,3的節點，...，在h級，2^h-1節點。在這種情況下，n = 2 ^（h + 1）-1其中h是B樹的高度，並且B樹中的節點數是＃節點= 2 ^（h + 1）-2-h = n-lg（n + 1）。因此，對於任何n，最終的B樹必須有n-⌊lg（n + 1）⌋≤＃nodes≤n-1（如果n≥2）。