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

Question

La imagen anterior es de "Wikipedia's entry on AVL trees" que Wikipedia indica no está equilibrado. ¿Cómo es que este árbol ya no está balanceado? 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 equilibrada . 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 izquierdo tiene una altura de 3 que sigue siendo solo 1 menor que 4. ¿Puede alguien explicar lo que me falta?

Answer 1

que ser equilibrado, cada nodo en el árbol debe, o bien,

• no tienen hijos, (ser un nodo "hoja")
• tienen dos hijos.

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

  En la tabla que ha publicado, 9, 54 & 76 infringe la última regla.

con un buen equilibrio, 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, que crea un gráfico en línea fresco para la gráfica en draw.io)

Answer 2

nodo 76 está desequilibrada, por ejemplo, debido a que su subárbol derecho es de 0 y la altura de la izquierda es de la altura 3.

Answer 3

Intuitivamente, es porque no es tan pequeño como sea posible. Por ejemplo, 12 debe ser el padre de 9 y 14. Como es, 9 no tiene subárbol izquierdo por lo que está desequilibrado. Un árbol es una estructura de datos jerárquica, por lo que una regla como "equilibrado" a menudo se aplica a cada nodo y no solo al nodo raíz.

Tiene la razón de que el nodo raíz está equilibrado, pero no todos los nodos del árbol.

Answer 4

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

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

y un nodo no está equilibrada cuando:

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 es equilibrada o no mirar a 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 resuelve 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.