¿Cómo es realmente desequilibrado el ejemplo de Wikipedia de un árbol AVL desequilibrado?

Question

??

La imagen de arriba es de " entrada de Wikipedia en los árboles AVL " que Wikipedia indica que es desequilibrado. ¿Cómo es que este árbol ya no está equilibrado? Aquí hay una cita del artículo:

  

El factor de equilibrio de un nodo es la altura de su subárbol derecho menos la altura de su subárbol izquierdo y un nodo con factor de equilibrio 1, 0 o -1 se considera equilibrado. Un nodo con cualquier otro factor de equilibrio se considera desequilibrado y requiere reequilibrar el árbol. El factor de equilibrio se almacena directamente en cada nodo o se calcula a partir de las alturas de los subárboles.

Tanto el subárbol izquierdo como el derecho tienen una altura de 4. El subárbol derecho del árbol de la izquierda tiene una altura de 3, que es solo 1 menos que 4. ¿Puede alguien explicar lo que me estoy perdiendo?

Answer 1

Para estar equilibrado, todos los nodos del árbol deben, cualquiera de los dos,

• no tiene hijos, (sea un nodo "hoja")
• Ten dos hijos.

• O, si solo tiene un hijo, ese hijo debe ser una hoja.

  En la tabla que publicaste, 9, 54 & amp; 76 violan la última regla.

Bien equilibrado, el árbol se vería así:

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

ACTUALIZACIÓN: (después de casi 9 años, creé un gráfico en línea para la gráfica en draw.io : //i.stack.imgur.com/n6KwW.png "rel =" nofollow noreferrer ">

Answer 2

El nodo 76 no está equilibrado, por ejemplo, porque su subárbol derecho es de altura 0 y el izquierdo es de altura 3.

Answer 3

Intuitivamente, es porque no es lo más pequeño posible. por ejemplo, 12 debe ser el padre de 9 y 14. Tal como está, 9 no tiene un subárbol izquierdo, por lo que está fuera de balance. Un árbol es una estructura de datos jerárquica, por lo que una regla como "equilibrado" a menudo se aplica a todos los nodos y no solo al nodo raíz.

Tienes razón, el nodo raíz está equilibrado, pero no todos los nodos del árbol lo están.

Answer 4

Otra forma de ver esto es que la altura h de cualquier nodo viene dada por:

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

y un nodo está desequilibrado siempre que:

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

Mirando el árbol de arriba:

- 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

Para determinar si el nodo 9 está equilibrado o no, miramos la altura de sus hijos:

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

Ahora resuelva para mostrar que el nodo 9 está desequilibrado:

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

Se pueden realizar cálculos similares para cada otro nodo.