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

arboles avl rotaciones ejemplos

Question

La imagen de arriba es de "entrada de Wikipedia en árboles AVL" que Wikipedia indica está desequilibrada. ¿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.

Los subárboles izquierdo y 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

Para ser equilibrado, cada nodo en el árbol debe, tampoco,

• no tener hijos, (ser un nodo "hoja")
• Tengo dos niños.

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

  En el cuadro que publicó, 9, 54 y 76 infringen 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 excelente gráfico en línea para el gráfico en draw.io )

Answer 2

El nodo 76 está desequilibrado, 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 debería 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 razón, el nodo raíz está equilibrado, pero no todos los nodos del árbol.

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 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 hacer cálculos similares para cada otro nodo.