Ejercicios · Estructuras C24¶
El árbol binario de búsqueda: la definición, buscar, insertar y borrar con recursión y con ciclos, y lo que cuesta cada operación según la forma del árbol. Cada enlace abre una actividad que se trabaja directo en el navegador, en el mismo orden de los temas de la sesión. Los árboles y los programas no son los de la sesión: mismo tema, ronda nueva.
Buscar rápido sin perder el orden¶
arreglo¶
Un arreglo ordenado de quince claves: qué casillas mira la búsqueda binaria del 39, qué árbol forman sus comparaciones y cuánto cuesta agregar el 33 en el arreglo y en ese árbol.
El árbol binario de búsqueda¶
esabb¶
Cuatro árboles para decidir si son ABB, uno de ellos hecho para engañar a quien solo mira los hijos, el inorden que delata al que falla y dos huecos con el rango de claves que admiten.
Buscar¶
buscar¶
Buscar el 32, el 70 y el 45 contando comparaciones, los marcos de la versión
recursiva, las vueltas de buscarIterativa, el mínimo y el máximo, y la peor
búsqueda de un árbol de altura 3.
Insertar¶
insertar¶
Las claves 36 17 58 25 9 30 21 44 71 28 en un ABB vacío: el preorden y la
altura que dejan, una clave repetida, insertarIterativa con padre y
actual, y cuál de cuatro órdenes arma el mismo árbol.
reenganche¶
insertar línea por línea con la pila de marcos a la vista: cuál de las
asignaciones r->izq = insertar(r->izq, k) cambia de verdad un puntero, y qué
pasa cuando falta la asignación.
Borrar¶
borrar¶
Una hoja, un nodo con un hijo y dos nodos con dos hijos, uno de ellos la raíz,
cuyo sucesor tiene a su vez un hijo derecho. El preorden tras cada borrado,
borrar(raiz, 47) marco por marco y el olvido de raiz =.
Lo que cuesta: la forma del árbol¶
forma¶
Las claves 5, 10, …, 75 en orden decreciente, en zigzag, por niveles y revueltas: la altura de cada árbol, las comparaciones que cuesta armarlo y las cotas de h para 100 y 50 000 claves.
situaciones¶
Turnos que llegan crecientes, códigos revueltos, un millón de claves y una lista de 300 000 nodos: qué cobra el ABB en cada caso y cuándo le gana un arreglo ordenado.
Ejercicios con recursión¶
rango¶
esABBHijos y esABB sobre un árbol con el 47 fuera de lugar: el rango que
hereda cada nodo, dónde corta el && y qué valores arreglarían el árbol.
recorte¶
contarRango entre 27 y 55 y entre 92 y 99, y kEsimo con k = 3 y k = 7,
recursivo y con pila explícita: qué devuelven, en qué nodos entran y qué
subárboles se saltan.
Para el juez¶
preorden¶
Del preorden 63 38 21 9 30 52 45 57 80 71 94 al posorden, un preorden que llega ordenado, la raíz borrada con el sucesor frente al predecesor y el espacio antes de cada clave en la salida.