Types d'arbre binaire

Un arbre binaire est plein si chaque nœud a 0 ou 2 enfants. Nous pouvons également dire qu'un arbre binaire plein est un arbre binaire dans lequel tous les nœuds, à l'exception des feuilles, ont deux enfants.
Voici des exemples d'arbres binaires pleins.

Un arbre binaire est complet si tous les niveaux sont complètement remplis, sauf peut-être le dernier niveau et le dernier niveau a toutes les clés aussi gauche que possible.

Un arbre binaire est parfait si tous les nœuds internes ont deux enfants et toutes les feuilles sont au même niveau.

Un arbre binaire parfait de hauteur h a 2^h - 1 nœud.

Un arbre binaire est équilibré si sa hauteur est O(Log n), où n est le nombre de nœuds.

• Arbre AVL maintient la hauteur en O(Log n) en veillant à ce que la différence entre les hauteurs des sous-arbres gauche et droit soit de 1.
• Les arbres rouges-noirs maintiennent la hauteur en O(Log n) en s'assurant que le nombre de noeuds noirs sur chaque chemin de racine à feuille est le même et qu'il n'y a pas de noeuds rouges adjacents.

Les arbres binaires de recherche équilibrés sont bons du point de vue des performances car ils fournissent le temps O(Log n) Pour la recherche, l'insertion et la suppression.