Ejercicios arbol avl

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ámetros unnodo 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 un programa paracomprobar 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 ÁRBOLESBINARIOS 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 parcialmente ordenado y binario de búsquedasimultá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, pero tienen el problema de que laeficiencia 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 alturas de sus dos subárboles difieren comomucho 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 pero con la ventaja de garantizaremos un caso peor deO(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 construir para una altura h el AVL Th, con mínimo número denodos. 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ón similar 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

En muchas implementaciones, para cada nodo no se almacena la...