Définition d'un arbre équilibré

Je me demande simplement si quelqu'un pourrait clarifier la définition d'un arbre équilibré pour moi. J'ai que "un arbre est équilibré si chaque sous-arbre est équilibré et la hauteur des deux sous-arbres diffère d'au plus un.

Je m'excuse si c'est une question stupide, mais cette définition s'applique-t-elle à chaque nœud jusqu'aux feuilles d'un arbre ou uniquement aux sous-arbres gauche et droit immédiatement à la racine? Je suppose qu'une autre façon d'encadrer cela serait, est-il possible que les nœuds internes d'un arbre soient déséquilibrés et que l'arbre entier reste équilibré?

La contrainte est généralement appliquée de manière récursive à chaque sous-arbre. Autrement dit, l'arbre n'est équilibré que si:

1. Les hauteurs des sous-arbres gauche et droit diffèrent d'au plus un, ET
2. Le sous-arbre de gauche est équilibré, ET
3. Le bon sous-arbre est équilibré

Selon cela, l'arbre suivant est équilibré:

     A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G  

Le suivant n'est pas équilibré car les sous-arbres de C diffèrent de 2 par leur hauteur:

     A
   /   \
  B     C   <-- difference = 2
 /     /
D     E  
     /  
    G  

Cela dit, la contrainte spécifique du premier point dépend du type d'arbre. Celui répertorié ci-dessus est le type d' arbres AVL .

Les arbres rouge-noir , par exemple, imposent une contrainte plus douce.

Il existe plusieurs façons de définir «équilibré». L'objectif principal est de conserver les profondeurs de tous les nœuds O(log(n)).

Il me semble que la condition d'équilibre dont vous parliez concerne l' arbre AVL .
Voici la définition formelle de la condition d'équilibre de l'arbre AVL :

Pour tout nœud dans AVL, la hauteur de son sous-arbre gauche diffère d' au plus 1 de la hauteur de son sous-arbre droit.

Question suivante, qu'est-ce que la « hauteur »?

La " hauteur " d'un nœud dans un arbre binaire est la longueur du chemin le plus long de ce nœud à une feuille.

Il y a un cas étrange mais courant:

Les gens définissent la hauteur d'un arbre vide (-1).

Par exemple, l'enfant gauche de root est null:

              A  (Height = 2)
           /     \
(height =-1)       B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1
                    \
                     C (Height = 0)

Deux autres exemples à déterminer:

Oui, un exemple d' arbre équilibré :

        A (h=3)
     /     \
 B(h=1)     C (h=2)        
/          /   \
D (h=0)  E(h=0)  F (h=1)
               /
              G (h=0)

Non, pas un exemple d' arbre équilibré :

        A (h=3)
     /     \
 B(h=0)     C (h=2)        <-- Unbalanced: 2-0 =2 > 1
           /   \
        E(h=1)  F (h=0)
        /     \
      H (h=0)   G (h=0)      

Il n'y a aucune différence entre ces deux choses. Pensez-y.

Prenons une définition plus simple: «Un nombre positif est égal s'il est égal à zéro ou ce nombre moins deux est pair». Est-ce que cela dit que 8 est égal si 6 est pair? Ou est-ce que cela signifie que 8 est égal si 6, 4, 2 et 0 sont pairs?

Il n'y a aucune différence. S'il dit que 8 est même si 6 est pair, il dit également que 6 est même si 4 est pair. Et ainsi, il dit aussi 4 est même si 2 est pair. Et ainsi il dit que 2 est même si 0 est pair. Donc, s'il dit que 8 est même si 6 est pair, il dit (indirectement) que 8 est même si 6, 4, 2 et 0 sont pairs.

C'est la même chose ici. Tout sous-arbre indirect peut être trouvé par une chaîne de sous-arbres directs. Donc, même si cela ne s'applique directement qu'aux sous-arbres directs, il s'applique toujours indirectement à tous les sous-arbres (et donc à tous les nœuds).

L'arbre équilibré est un arbre dont la hauteur est de l'ordre du log (nombre d'éléments dans l'arbre).

height = O(log(n))
O, as in asymptotic notation i.e. height should have same or lower asymptotic
growth rate than log(n)
n: number of elements in the tree

La définition donnée "un arbre est équilibré de chaque sous-arbre est équilibré et la hauteur des deux sous-arbres diffère d'au plus un" est suivie par les arbres AVL.

Étant donné que les arbres AVL sont équilibrés mais que tous les arbres équilibrés ne sont pas des arbres AVL, les arbres équilibrés ne contiennent pas cette définition et les nœuds internes peuvent y être déséquilibrés. Cependant, les arborescences AVL nécessitent que tous les nœuds internes soient équilibrés.

le but de l'arbre équilibré est d'atteindre la feuille en un minimum de traversée (hauteur min). Le degré de l'arbre est le nombre de branches moins 1. Un arbre équilibré peut ne pas être binaire.

1. La hauteur d'un nœud dans un arbre est la longueur du chemin le plus long de ce nœud vers le bas jusqu'à une feuille, en comptant à la fois les sommets de début et de fin du chemin.
2. Un nœud dans un arbre est équilibré en hauteur si les hauteurs de ses sous-arbres ne diffèrent pas de plus de 1.
3. Un arbre est équilibré en hauteur si tous ses nœuds sont équilibrés en hauteur.