Dans les arbres B, quel élément est promu lorsque le nœud se divise

Question

Supposons qu'il y ait un arbre B d'ordre 8. Cela signifie qu'il peut avoir 8 pointeurs et 7 éléments. Imaginons que les lettres A à G soient stockées dans cet arbre B. Ainsi, cet arbre B n'est qu'un seul nœud contenant 7 éléments.

Ensuite, vous essayez d'insérer J dans l'arbre. Il n'y a pas de place, donc vous devez diviser le nœud et créer un nouveau nœud racine. Quel élément est promu dans le nœud racine ?

Answer 1

Lorsque vous souhaitez insérer un nouvel élément dans un nœud complet (avec 2*t - 1 clés)

• vous divisez en choisissant la clé médiane du nœud (la clé qui est au milieu)
• vous générez les deux nouveaux enfants avec t-1 clés chacun (en les divisant selon la clé précédente)
• la valeur médiane reste dans le nœud père
• ensuite, vous procédez selon l'algorithme d'insertion normal, en cherchant où vous devriez placer le nouvel élément.