Listes de sauts déterministes fortement équilibrés en poids

Dans la section 2.2 de Cache-Inconscient B-arbres , fortement poids équilibré Les arbres de recherche sont définis comme suit:

Pour une constante , chaque nœud à la hauteur a des descendants .v h Θ ( d h$d$$v$$h$$\Theta(d^h)$

Ils affirment:

Les arbres de recherche qui satisfont aux propriétés 1 et 2 comprennent les arbres B à poids équilibré, les listes de saut déterministes et les listes de saut dans le sens attendu.

D'autres articles affirment également que les listes de sauts déterministes sont fortement équilibrées en termes de poids, y compris les arbres B simultanés Cache-Oblivious et Cache-Oblivious Streaming B- Trees .

Je ne peux pas comprendre pourquoi les listes de saut déterministes ont cette propriété. L' article original sur les listes de sauts déterministes note que

Comme nous le voyons sur la figure 1, il existe une correspondance biunivoque entre 1-2 listes de sauts et 2-3 arbres.

Il me semble cependant que 2-3 arbres ne sont pas fortement équilibrés en poids, car un nœud à la hauteur peut avoir entre et descendants.2 h 3 $h$$2^h$$3^h$

J'ai été en contact avec l'un des auteurs. Il a confirmé que c'était une erreur.

Comme indiqué ci-dessus, cela n'affecte en aucune façon les résultats du document.