Théorie des graphes

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

Types d'arbre binaire

Arbre binaire plein

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.

Dans un arbre binaire plein, le nombre de feuilles est égal le nombre de noeuds internes plus 1
L = I + 1
L = Nombre de feuilles,
I = Nombre de nœuds internes
Arbre binaire complet

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.

Arbre binaire parfait

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 2h - 1 nœud.

Arbre binaire équilibré

Un arbre binaire est équilibré si sa hauteur est O(Log n),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.

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :