calculo

Estructuras de Datos

108

Ejercicio: Genere el árbol binario de búsqueda para la
siguiente secuencia de números: 8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1,
5, 6, 4, 13, 14, 10, 12, 17, 16, 18.Analice y describa lo que sucede
durante su inserción.
Si de alguna manera se pudiera garantizar que el árbol además
de que no es degenerado mantiene un balance perfecto, entonces el
mecanismo deeficiencia de búsqueda en un árbol binario se
mantendría inalterado.
La idea es aquí entonces, generar un árbol de altura mínima que
contenga el mismo número de nodos.

Ricardo Ruiz RodríguezEstructuras de Datos

109

8.4.1 Árboles perfectamente balanceados.
Se dice que un árbol es perfectamente balanceado, si para
cada nodo en el árbol, el número de nodos en sus subárboles
izquierdoy derecho difieren a lo más en 1.
Ejercicio: Dado un conjunto de elementos a insertar dentro de
un árbol binario perfectamente balanceado ¿En qué orden deben
insertarse los nodos para que el árbolpermanezca inalterado
respecto a su balance?
Considere el siguiente algoritmo para generar un árbol binario
perfectamente balanceado:

Ricardo Ruiz Rodríguez

Estructuras de Datos

110

1.Sea n el número de nodos a insertar
2. Utilizar un nodo para la raíz
3. Generar el subárbol izquierdo recursivamente con el
siguiente número de nodos:
n_izq = n / 2
4. Generar el subárbolderecho recursivamente con el
siguiente número de nodos:
n_der = n – n_izq – 1
Ejercicio: En base al algoritmo propuesto, genere el árbol
binario perfectamente balanceado para la siguiente secuencia denúmeros: 8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1, 5, 6, 4, 13, 14, 10, 12,
17, 16, 18.

Ricardo Ruiz Rodríguez

Estructuras de Datos

111

El algoritmo anterior asume que de antemano se conoceel
número total de elementos a insertar, lo cual no siempre es posible,
por otro lado, debe observarse como resultado del ejercicio que el
árbol no mantiene un orden respecto al los elementos...