Dos definiciones de árboles binarios balanceados.

26

He visto dos definiciones de árboles binarios equilibrados, que me parecen diferentes.

  1. Un árbol binario se equilibra si para cada nodo mantiene que el número de nodos internos en el subárbol izquierdo y el número de nodos internos en el subárbol derecho difieren en como máximo 1.

  2. Un árbol binario está equilibrado si para cualquiera de las dos hojas la diferencia de profundidad es como máximo 1.

¿Cada árbol que satisface def. 1 también satisface def. 2? ¿Qué pasa al revés?

Forrest Gump
fuente
2
¿Has intentado probar cualquier dirección? ¿Cuáles son tus hallazgos?
Raphael

Respuestas:

17

La definición 1. también se conoce como equilibrio de peso ¹ y la definición 2. como equilibrio de altura .

El equilibrio de altura no implica equilibrio de peso; ejemplos son AVL- y Red-Black-Trees. Ver aquí y aquí para pruebas, respectivamente.

Sin embargo, el equilibrio de peso implica equilibrio de altura. Esto se puede demostrar mostrando el siguiente hecho más fuerte por inducción (sobre la altura): un árbol con equilibrio de peso está completo en todos los niveles excepto en el más profundo². El argumento esencial en el paso inductivo es que los subárboles no pueden tener una diferencia de altura de más de uno porque, ambos teniendo la propiedad reclamada por hipótesis de inducción, no estarían equilibrados en peso.


  1. El artículo da una definición diferente y más general.
  2. En otras palabras, tal árbol de altura sin las hojas en el nivel k es un árbol perfecto de altura k - 1 .kkk1
Rafael
fuente
Me acabo de dar cuenta de que el hecho más fuerte se puede utilizar para simplificar las pruebas con las que enlazo.
Raphael
Quizás sea una buena idea incorporar esta comprensión en su respuesta.
Lagarto discreto
@Discretelizard ¿Quieres decir que las otras respuestas?
Raphael
Oh, no me di cuenta de que esos enlaces eran respuestas en informática o que eran tus respuestas. Bueno, en cualquier caso, todo lo que quería decir es que podría ser una buena idea escribir las pruebas simplificadas. Sus respuestas vinculadas parecen ser el lugar apropiado.
Lagarto discreto