Arbre binaire équilibré

Question

Quel est le nom de l'arbre binaire (ou la famille des arbres binaires ), qui est équilibré, et a le nombre minimum de nœuds possible pour sa hauteur?

Answer 1

Il est appelé arbre Fibonacci

Answer 2

AVL est un arbre équilibré avec log (n) hauteur (ce qui est la plus faible hauteur possible arbre binaire).
Une autre implémentation d'une structure de données similaire est Red Black Tree.

Les deux arbres implémentent toutes les opérations dans O (log (n)).

Answer 3

AVL Tree est quelque chose que vous cherchiez.

de Wikipédia:

En informatique, un AVL tree est un arbre de recherche binaire auto-équilibrage, et il est la première structure de données à inventer. Dans un arbre AVL, les hauteurs des deux sous-arbres enfants de n'importe quel noeud diffèrent d'au plus un; par conséquent, il est également dit être équilibrée en hauteur. La recherche, l'insertion et la suppression prennent toutes le temps O (log n) dans les cas moyen et pire, où n est le nombre de nœuds dans l'arborescence avant l'opération. Les insertions et les suppressions peuvent nécessiter que l'arbre soit rééquilibré par une ou plusieurs rotations d'arbres.

Answer 4

arbre binaire équilibré

(structure de données)

de Définition: binary tree ou aucun leaf est supérieure à une certaine quantité plus loin de la root que tout autre. Après l'insertion ou la suppression d'un node, l'arborescence peut être rééquilibrée avec des "rotations".

Généralisation (je suis une sorte de ...) binary tree.

Spécialité (... est une sorte de moi.) AVL tree, red-black tree, B-tree, balanced binary search tree.

Agréger l'enfant (... fait partie de ou est utilisé en moi.) left rotation, right rotation. Voir également BB(α) tree, height-balanced tree.

-http://www.itl.nist.gov/div897/sqg/dads/HTML/balancedbitr.html