Ejercicios de arboles binarios (Matematicas)

EJERCICIOS DE ÁRBOLES BINARIOS
1) Supongamos que tenemos una función valor tal que dado un valor de tipo char
(una letra del alfabeto) devuelve un valor entero asociado a dicho
identificador. Supongamos también la existencia de un árbol de expresión T
cuyos nodos hoja son letras del alfabeto y cuyos nodos interiores son los
caracteres *, +, -, /. Diseñar una función que tome como parámetrosun nodo
y un árbol binario y devuelva el resultado entero de la evaluación de la
expresión representada.
2) El recorrido en preorden de un determinado árbol binario es: GEAIBMCLDFKJH
y en inorden IABEGLDCFMKHJ.
•
•
•

Dibujar el árbol binario.
Dar el recorrido en postorden.
Diseñar una función para dar el recorrido en postorden dado el recorrido
en preorden e inorden y escribir unprograma para comprobar el resultado
del apartado anterior.

3) Implementar una función no recursiva para recorrer un árbol binario en
inorden.
4) Implementar una función no recursiva para recorrer un árbol binario en
postorden.
5) Escribir una función recursiva que encuentre el número de nodos de un árbol
binario.
6) Escribir una función recursiva que encuentre la altura de un árbol binario.EJERCICIOS DE ÁRBOLES BINARIOS DE BÚSQUEDA (ABB)
1) ¿Puede reconstruirse de forma única un ABB dado su inorden? ¿Y dados el
preorden y el postorden?.
2) Construir un ABB con las claves 50, 25, 75, 10, 40, 60, 90, 35, 45, 70, 42.
3) Construir un ABB equilibrado a partir de las claves 10, 75, 34, 22, 64, 53, 41,
5, 25, 74, 20, 15, 90.
4) ¿Bajo qué condiciones puede un árbol ser parcialmenteordenado y binario de
búsqueda simultáneamente?. Razonar la respuesta.

1

Árboles AVL.
Supongamos que deseamos construir un ABB para la siguiente tabla de datos:

El resultado se muestra en la figura siguiente:
Como ve el resultado es un árbol muy poco balanceado y con características muy
pobres para la búsqueda. Los ABB trabajan muy bien para una amplia variedad de
aplicaciones, perotienen el problema de que la eficiencia en el peor caso es
O(n). Los árboles que estudiaremos a continuación nos darán una idea de cómo
podría resolverse el problema garantizando en el peor caso un tiempo O(log2 n).

2

ÁRBOLES EQUILIBRADOS AVL.
Diremos que un árbol binario está equilibrado (en el sentido de Addelson-Velskii y
Landis) si, para cada uno de sus nodos ocurre que las alturasde sus dos
subárboles difieren como mucho en 1. Los árboles que cumplen esta condición
son denominados a menudo árboles AVL.
En la primera figura se muestra un árbol que es AVL, mientras que el de la
segunda no lo es al no cumplirse la condición en el nodo k.

Árbol AVL

No es Árbol AVL

A través de los árboles AVL llegaremos a un procedimiento de búsqueda análogo
al de los ABB perocon la ventaja de garantizaremos un caso peor de O(log2 n),
manteniendo el árbol en todo momento equilibrado. Para llegar a este resultado,
podríamos preguntarnos cual podría ser el peor AVL que podríamos construir con
n nodos, o dicho de otra forma cuanto podríamos permitir que un árbol binario se
desequilibrara manteniendo la propiedad de AVL.
Para responder a la pregunta podemos construirpara una altura h el AVL Th, con
mínimo número de nodos. Cada uno de estos árboles mínimos debe constar de
una raíz, un subárbol AVL mínimo de altura h-1 y otro subárbol AVL también
mínimo de altura h-2. Los primeros Ti pueden verse en la siguiente figura:

3

Es fácil ver que el número de nodos n(Th) está dado por la relación de
recurrencia [1]:
n(Th) = 1 + n(Th-1) + n(Th-2)
Relaciónsimilar a la que aparece en los números de Fibonacci (Fn = Fn-1 + Fn2), de forma que la s
iguiente sucesión, de valores para n(Th) está relacionada
con los valores de la siguiente sucesión de Fibonacci:
AVL -> -, -, 1, 2, 4, 7, 12,...
FIB -> 1, 1, 2, 3, 5, 8, 13,...
es decir [2],
n(Th) = Fh+2 - 1
Resolviendo [1] y utilizando [2] llegamos tras algunos cálculos a:
log 2(n+1) b)?(a):(b))

4...