Comment l'exemple de Wikipedia d'un arbre AVL non équilibré est-il vraiment déséquilibré?

Question

L'image ci-dessus provient de "L'entrée de Wikipedia sur les arbres AVL" , ce que Wikipedia indique comme étant déséquilibré. Comment cet arbre n'est-il pas déjà équilibré? Voici une citation de l'article:

  

Le facteur d'équilibre d'un nœud est la hauteur de son sous-arbre droit moins la hauteur de son sous-arbre gauche. Un nœud avec un facteur d'équilibre de 1, 0 ou -1 est considéré comme équilibré. Un nœud avec tout autre facteur d'équilibre est considéré comme déséquilibré et nécessite un rééquilibrage de l'arborescence. Le facteur d'équilibre est soit stocké directement sur chaque noeud, soit calculé à partir des hauteurs des sous-arbres.

Les sous-arbres de gauche et de droite ont une hauteur de 4. Le sous-arbre de droite de l'arbre de gauche a une hauteur de 3 qui n'est encore que de 1 à 4. Quelqu'un peut-il expliquer ce que je manque?

Answer 1

Pour être équilibré, chaque nœud de l’arbre doit, soit,

• ne pas avoir d'enfants (être un nœud "feuille")
• Avoir deux enfants.

• Ou, s'il n'a qu'un enfant, cet enfant doit être une feuille.

  Dans le graphique que vous avez posté, 9, 54 & amp; 76 enfreignent la dernière règle.

Correctement équilibré, l’arbre ressemblerait à:

Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76

UPDATE: (après presque 9 ans, j'ai créé un graphique en ligne pour le graphique à l'adresse draw.io )

Answer 2

Le nœud 76 est déséquilibré, par exemple, car son sous-arbre droit est de hauteur 0 et son gauche est de hauteur 3.

Answer 3

Intuitivement, c’est parce que ce n’est pas aussi petit que possible. Par exemple, 12 doit être le parent de 9 et 14. Dans l’état actuel, 9 n’a pas de sous-arbre, ce qui le déséquilibre. Un arbre est une structure de données hiérarchique, donc une règle du type "équilibrée". s’applique souvent à chaque noeud et pas seulement au noeud racine.

Vous avez raison, le nœud racine est équilibré, mais tous les nœuds de l'arbre ne le sont pas.

Answer 4

Une autre façon de voir cela est que la hauteur h de tout nœud est donnée par:

h = 1 + max (left.height, right.height)

et un nœud est déséquilibré chaque fois que:

abs (left.height - right.height) > 1

En regardant l'arbre ci-dessus:

- Node 12 is a leaf node so its height = 1+max(0,0) = 1
- Node 14 has one child (12, on the left), so its height is = 1+max(1,0) = 2
- Node 9 has one child (14, on the right), so its height is = 1+max(0,2) = 3

Pour déterminer si le noeud 9 est équilibré ou non, nous regardons la hauteur de ses enfants:

- 9's left child is NULL, so 9.left.height = 0
- 9's right child (14) has height 2, so 9.right.height = 2

Maintenant, résolvez pour montrer que le noeud 9 est déséquilibré:

9.unbalanced = abs( 9.left.height - 9.right.height ) > 1
9.unbalanced = abs( 0 - 2 ) > 1
9.unbalanced = abs( -2 ) > 1
9.unbalanced = 2 > 1
9.unbalanced = true

Des calculs similaires peuvent être effectués pour tous les autres nœuds.