1. Coloque las palabras FOTO SOBRE ARRIBASIETE YAANTES OBSERVA FELIZ BARATO FOMENTO, en el orden en el que aparecen, en un árbol de búsqueda binaria.
2. Escriba un algoritmo formal de búsqueda en un árbol de búsqueda binaria.
3. Escriba un algoritmo que almacene n palabras diferentes en un árbol de búsqueda binaria Tde altura mínima. Demuestre que el árbol T* obtenido, como se describe en el texto, tiene altura lg(n+1)
4. ¿Falso o verdadero? Sea T un árbol binario. Si para cada vértice v en T el dato en v es mayor que el dato en el hijo izquierdo de v, y el dato en v es menor que el dato en el hijo derecho de v, entonces T es un árbol de búsqueda binaria. Explique.
En los ejercicios 5 al 7, dibuje una gráfica que tenga las propiedades indicadas o explique por qué no existe la gráfica.
5. Árbol binario completo; 4 vértices internos; 5 vértices terminales
7. Árbol binario completo; altura =4; 9 vértices terminales
8. Un árbol m-ario completo es un árbol con raíz tal que todo padre tiene m hijos ordenados. Si T es un árbol m-ario completo con i vértices internos, ¿cuántos vértices tiene T? ¿Cuántos vértices terminales tiene T? Pruebe sus resultados.
9. Proporcione un algoritmo para construir un árbol binario completo con n > 1 vértices terminales.
10. Proporcione un algoritmo recursivo para insertar una palabra en un árbol de búsqueda binaria.
11. Encuentre la altura máxima de un árbol binario completo que tiene t vértices terminales.
12. Escriba un algoritmo que pruebe si un árbol binario en el que se almacenan datos en los vértices es un árbol de búsqueda binaria.
13. Sea T un árbol binario completo. Sea I la suma de las longitudes de las trayectorias simples de la raíz a los vértices internos. I se llama longitud de trayectoria interna. Sea E la suma de las longitudes de las trayectorias simples de la raíz a los vértices terminales. Ese llama longitud de trayectoria externa. Pruebe que si Ttiene n vértices terminales, entonces E=I−2n.
Un árbol binario T está balanceado si para cada vértice v en T, las alturas de los subárboles izquierdo y derecho de v difieren cuando mucho en 1. (Aquí, la altura de un árbol vacío se define como −1).
18. Demuestre que N0 =1, N1 =2 y N2 =4.
19. Demuestre que Nh =1 +Nh−1 +Nh−2, para h≥0.
20. Demuestre que Nh =fh+3 −1, para h≥0.
21. Demuestre que la altura h de un árbol binario balanceado de n vértices satisface h=O(lg n). Este resultado indica que el tiempo de búsqueda, en el peor caso, en un árbol de búsqueda binaria balanceado de n vértices es O(lg n).
22. Pruebe que si un árbol binario de altura h tiene n≥1 vértices, entonces lg n < h + 1. Este resultado, junto con el ejercicio 21, muestra que el tiempo de búsqueda en el peor caso en un árbol de búsqueda binaria balanceado de n vértices es (lg n).
