Comment Équilibrés sont équilibrés B-arbres

Question

Dites que j'ai un B-Tree avec des nœuds dans une configuration 3-4 (3 éléments et 4 pointeurs). En supposant que je construise légalement mon arbre selon les règles, est-il possible pour moi d'atteindre une situation où il y a deux nœuds dans une couche et un nœud a 4 pointeurs sortants et l'autre a seulement deux pointeurs sortants?

En général, quelles garanties dois-je à la balancedness d'un B-Tree

Answer 1

correctement utilisé L'idée derrière l'équilibre (en général des structures de données d'arbre équilibré) est que la différence de profondeurs entre deux quelconques sous-arbres est zéro ou un (en fonction de l'arbre). En d'autres termes, le nombre de comparaisons utilisées pour trouver un nœud feuille est toujours similaire. Donc, oui, vous pouvez vous retrouver dans la situation que vous décrivez, simplement parce que les profondeurs sont les mêmes. Le nombre d'éléments dans chaque nœud ne concerne pas la balance (mais voir ci-dessous).

Ceci est parfaitement même légal si il y a plus d'éléments dans le nœud gauche que la droite (pointeurs nuls ne sont pas représentés):

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

Cependant, il est très rare d'avoir un 3-4 BTree (certains en fait dire que c'est pas un BTree du tout, mais une autre structure de données). Avec BTrees, vous avez généralement un nombre pair de clés au maximum dans chaque nœud (par exemple, un arbre 4-5) de sorte que la division et la combinaison sont plus faciles. Avec un arbre 4-5, la décision quant à la clé qui est promue quand un nœud se remplit est facile - c'est le milieu des cinq. Ce n'est pas une question si claire avec un arbre 3-4 car il pourrait être l'un des deux (il n'y a pas de milieu défini pour quatre éléments).

Il vous permet également de suivre la règle que vos nœuds doivent contenir entre n et 2n éléments. De plus (pour les "bons" BTrees), les nœuds feuilles sont tous à même profondeur, et pas seulement l'un dans l'autre.

Si vous avez ajouté les valeurs suivantes à un BTree vide, vous pourriez vous retrouver avec la situation que vous décrivez:

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