B樹中的節點數

Question

在具有最小度數爲t的B樹中，除root之外的每個非葉節點至少有t個孩子和至多2 * t個孩子。假設將鍵{1,2,3 ...，n}插入到序列1,2,3 .....，n中具有最小次數2的空B樹中。最終的B樹有多少個節點？

從我所瞭解的情況來看，我覺得它會是n/t，因爲每個節點可以擁有的最小密鑰數是k，而密鑰的總數是n。我對麼？？如果不能告訴我我要去哪裏，我該怎麼做？

Answer 1

答案是(n-2)*log(n-2)與t=2

Answer 2

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