Supposons que l'on insère les clés {1,2, ..., n} dans un arbre B vide de degré 2 minimum. Combien de nœuds l'arbre B final a-t-il?CLRS 18-2.4 Supposons que l'on insère les clés {1,2, ..., n} dans un arbre B vide de degré 2 minimum. Combien de nœuds l'arbre B final a-t-il?
Nous savons que chaque noeud à l'exception de la racine doit avoir au moins t-1 = 1 clés, et au plus 2t-1 = 3 clés. L'arbre final peut avoir au plus n-1 nœuds quand n≥2. À moins que n = 1, il ne peut jamais y avoir n nœuds puisque nous n'insérons jamais une clé dans un nœud non vide, donc il y aura toujours au moins un nœud avec 2 clés. Ensuite, observez que nous n'aurons jamais plus d'une clé dans un nœud qui n'est pas une colonne vertébrale droite de notre arbre B. C'est parce que chaque clé que nous insérons est plus grande que toutes les clés stockées dans l'arbre, donc elle sera insérée dans la colonne vertébrale droite de l'arbre. Le nombre de nœuds le plus faible possible se produit lorsque chaque nœud, à l'exception du nœud le plus profond de la colonne droite, possède 2 clés et que le nœud le plus profond de la spline droite possède 3 clés. Donc à la hauteur 1, 1 nœuds, à la hauteur 2, 3 nœuds, ..., au niveau h, 2^h-1 nœuds. Dans ce cas, n = 2^(h + 1) -1 où h est la hauteur de l'arbre B, et le nombre de nœuds dans B-Tree est #nodes = 2^(h + 1) -2-h = n-lg (n + 1). Donc, pour tout n, l'arbre B final doit avoir n-⌊lg (n + 1) ⌋≤ # nœuds≤n-1 (si n≥2).