El último día vimos cómo hacer listas dinámicas enlazadas, y cómo podíamos ir insertando los elementos en ellas de forma que siempre estuviesen ordenadas.
Hay varios casos particulares. Sólo comentaré algunos
de ellos de pasada:
Estas dos son estructuras más sencillas de programar de lo
que sería una lista en su caso general, pero que son también
útiles en muchos casos. De momento no incluyo ejemplos de ninguna
de ellas, y me lo reservo para los ejercicios y para cuando lleguemos a
Programación Orientada a Objetos, y será entonces cuando
creemos nuestro objeto Pila y nuestro objeto Cola (recordádmelo
si se me pasa). Aun así, si alguien tiene dudas ahora, que
no se corte en decirlo, o que se espere un poco, hasta ver las soluciones
de los "deberes"... }:-)
Finalmente, antes de pasar con los "árboles", comentaré
una mejora a estas listas enlazadas que hemos visto. Tal y como las
hemos tratado, tienen la ventaja de que no hay limitaciones tan rígidas
en cuanto a tamaño como en las variables estáticas, ni hay
por qué saber el número de elementos desde el principio.
Pero siempre hay que recorrerlas desde DELANTE hacia ATRAS, lo que puede
resultar lento. Una mejora relativamente evidente es lo que se llama
una lista doble o lista doblemente enlazada: si guardamos punteros
al dato anterior y al siguiente, en vez de sólo al siguiente, podremos
avanzar y retroceder con comodidad. Pero tampoco me enrollo más
con ello, lo dejo como ejercicio para quien tenga inquietudes.
ARBOLES.
Vamos allá. En primer lugar, veamos de donde viene el nombrecito. En las listas, después de cada elemento venía otro (o ninguno, si habíamos llegado al final). Pero también nos puede interesar tener varias posibilidades después de cada elemento, 3 por ejemplo. De cada uno de estos 3 saldrían otros 3, y así sucesivamente. Obtendríamos algo que recuerda a un árbol: un tronco del que nacen 3 ramas, que a su veces se subdividen en otras 3 de menor tamaño, y así sucesivamente hasta llegar a las hojas.
Pues eso será un árbol: una estructura dinámica en la que cada nodo (elemento) puede tener más de un "siguiente". Nos centraremos en los árboles binarios, en los que cada nodo puede tener un hijo izquierdo, un hijo derecho, ambos o ninguno (dos hijos como máximo).
Para puntualizar aun más, aviso que trataremos los árboles binarios de búsqueda, en los que tenemos prefijado un cierto orden, que nos ayudará a encontrar un cierto dato dentro de un árbol con mucha rapidez.
¿Y como es este "orden prefijado"? Sencillo: para cada nodo tendremos que:
- la rama de la izquierda contendrá elementos menores.
- la rama de la derecha contendrá elementos mayores.
¿Asusta? Con un ejemplo seguro que no: Vamos a introducir en un árbol binario de búsqueda los datos 5,3,7,2,4,8,9
Primer número: 5 (directo)
5
Segundo número: 3 (menor que 5)
5
/
3
Tercer número: 7 (mayor que 5)
5
/ \
3 7
Cuarto: 2 (menor que 5, menor que 3)
5
/ \
3 7
/
2
Quinto: 4 (menor que 5, mayor que 3)
5
/ \
3 7
/ \
2 4
Sexto: 8 (mayor que 5, mayor que 7)
5
/ \
3 7
/ \ \
2 4 8
Séptimo: 9 (mayor que 5, mayor que 7, mayor que 8)
5
/ \
3 7
/ \ \
2 4 8
\
9
¿Y qué ventajas tiene esto? Pues la rapidez: tenemos 7 elementos, lo que en una lista supone que si buscamos un dato que casualmente está al final, haremos 7 comparaciones; en este árbol, tenemos 4 alturas => 4 comparaciones como máximo.
Y si además hubiéramos "equilibrado" el árbol (irlo recolocando, de modo que siempre tenga la menor altura posible), serían 3 alturas.
Esto es lo que se hace en la práctica cuando en el árbol se va a hacer muchas más lecturas que escrituras: se reordena internamente después de añadir cada nuevo dato, de modo que la altura sea mínima en cada caso.
De este modo, el número máximo de comparaciones que tendríamos que hacer sería log2( n ), lo que supone que si tenemos 1000 datos, en una lista podríamos llegar a tener que hacer 1000 comparaciones, y en un arbol binario, log2(1000) => 10 comparaciones como máximo. La ganancia es clara, ¿verdad?
No vamos a ver cómo se hace eso de los "equilibrados", que considero que sería propio de un curso de programación más avanzado, o incluso de uno de "Tipos Abstractos de Datos" o de "Algorítmica", y vamos a empezar a ver rutinas para manejar estos árboles binarios de búsqueda.
Recordemos que la idea importante es todo dato menor estará a la izquierda del nodo que miramos, y los datos mayores estarán a su derecha.
Ahora la estructura de cada nodo (dato) será:
type
TipoDato = string[10]; { Vamos a guardar texto, por ejemplo }
Puntero = ^TipoBase; { El puntero al tipo base }
TipoBase = record { El tipo base en sÃ: }
dato: TipoDato; { - un dato }
hijoIzq: Puntero; { - puntero a su hijo izquierdo }
hijoDer: Puntero; { - puntero a su hijo derecho }
end;
Y las rutinas de inserción, búsqueda, escritura, borrado, etc., podrán ser recursivas. Como primer ejemplo, la de escritura de todo el árbol (la más sencilla) sería:
procedure Escribir(punt: puntero);
begin
if punt <> nil then { Si no hemos llegado a una hoja }
begin
Escribir(punt^.hijoIzq); { Mira la izqda recursivamente }
write(punt^.dato); { Escribe el dato del nodo }
Escribir(punt^.hijoDer); { Y luego mira por la derecha }
end;
end;
Si alguien no se cree que funciona, que coja lápiz y papel y lo compruebe con el árbol que hemos puesto antes como ejemplo. Es MUY IMPORTANTE que este procedimiento quede claro antes de seguir leyendo, porque los demás serán muy parecidos.
La rutina de inserción sería:
procedure Insertar(var punt: puntero; valor: TipoDato);
begin
if punt = nil then { Si hemos llegado a una hoja }
begin
new(punt); { Reservamos memoria }
punt^.dato := valor; { Guardamos el dato }
punt^.hijoIzq := nil; { No tiene hijo izquierdo }
punt^.hijoDer := nil; { Ni derecho }
end
else { Si no es hoja }
if punt^.dato > valor { Y encuentra un dato mayor }
Insertar(punt^.hijoIzq, valor) { Mira por la izquierda }
else { En caso contrario (menor) }
Insertar(punt^.hijoDer, valor) { Mira por la derecha }
end;
Y finalmente, la de borrado de todo el árbol, casi igual que la de escritura:
procedure BorrarArbol(punt: puntero);
begin
if punt <> nil then { Si queda algo que borrar }
begin
BorrarArbol(punt^.hijoIzq); { Borra la izqda recursivamente }
dispose(punt); { Libera lo que ocupaba el nodo }
BorrarArbol(punt^.hijoDer); { Y luego va por la derecha }
end;
end;
Sólo un comentario: esta última rutina es peligrosa, porque indicamos que "punt" está libre y después miramos cual es su hijo izquierdo (después de haber borrado la variable). Esto funciona en Turbo Pascal porque marca esa zona de memoria como disponible pero no la borra físicamente, pero puede dar problemas con otros compiladores o si se adapta esta rutina a otros lenguajes (como C). Una forma más segura de hacer lo anterior sería memorizando lo que hay a la derecha antes de borrar el nodo central:
procedure BorrarArbol2(punt: puntero);
var
derecha: puntero; { Aquà guardaremos el hijo derecho }
begin
if punt <> nil then { Si queda algo que borrar }
begin
BorrarArbol2(punt^.hijoIzq); { Borra la izqda recursivamente }
derecha := punt^.hijoDer; { Guardamos el hijo derecho <=== }
dispose(punt); { Libera lo que ocupaba el nodo }
BorrarArbol2(derecha); { Y luego va hacia por la derecha }
end;
end;
O bien, simplemente, se pueden borrar recursivamente los dos hijos antes que el padre (ahora ya no hace falta ir "en orden", porque no estamos leyendo, sino borrando todo):
procedure BorrarArbol(punt: puntero);
begin
if punt <> nil then { Si queda algo que borrar }
begin
BorrarArbol(punt^.hijoIzq); { Borra la izqda recursivamente }
BorrarArbol(punt^.hijoDer); { Y luego va hacia la derecha }
dispose(punt); { Libera lo que ocupaba el nodo }
end;
end;
Finalmente, vamos a juntar casi todo esto en un ejemplo "que funcione":
{--------------------------}
{ Ejemplo en Pascal: }
{ }
{ Ejemplo de árboles }
{ binarios de búsqueda }
{ ARBOL.PAS }
{ }
{ Este fuente procede de }
{ CUPAS, curso de Pascal }
{ por Nacho Cabanes }
{ }
{ Comprobado con: }
{ - Free Pascal 2.2.0w }
{ - Turbo Pascal 7.0 }
{ - Tmt Pascal Lt 1.20 }
{--------------------------}
type
TipoDato = integer; { Vamos a guardar texto, por ejemplo }
Puntero = ^TipoBase; { El puntero al tipo base }
TipoBase = record { El tipo base en sí: }
dato: TipoDato; { - un dato }
hijoIzq: Puntero; { - puntero a su hijo izquierdo }
hijoDer: Puntero; { - puntero a su hijo derecho }
end;
procedure Escribir(punt: puntero);
begin
if punt <> nil then { Si no hemos llegado a una hoja }
begin
Escribir(punt^.hijoIzq); { Mira la izqda recursivamente }
write(punt^.dato, ' '); { Escribe el dato del nodo }
Escribir(punt^.hijoDer); { Y luego mira por la derecha }
end;
end;
procedure Insertar(var punt: puntero; valor: TipoDato);
begin
if punt = nil then { Si hemos llegado a una hoja }
begin
new(punt); { Reservamos memoria }
punt^.dato := valor; { Guardamos el dato }
punt^.hijoIzq := nil; { No tiene hijo izquierdo }
punt^.hijoDer := nil; { Ni derecho }
end
else { Si no es hoja }
if punt^.dato > valor { Y encuentra un dato mayor }
then
Insertar(punt^.hijoIzq, valor) { Mira por la izquierda }
else { En caso contrario (menor) }
Insertar(punt^.hijoDer, valor) { Mira por la derecha }
end;
{ Cuerpo del programa }
var
arbol1: Puntero;
begin
arbol1 := nil;
Insertar(arbol1, 5);
Insertar(arbol1, 3);
Insertar(arbol1, 7);
Insertar(arbol1, 2);
Insertar(arbol1, 4);
Insertar(arbol1, 8);
Insertar(arbol1, 9);
Escribir(arbol1);
end.
Nota: en versiones anteriores de este fuente, la variable se
llamaba "arbol". En la versión 3.5.1 del curso, he cambiado
esta variable por "arbol1", dado que Tmt Pascal Lite protesta si usamos
alguna variable que se llame igual que el nombre del programa (avisa de
que estamos usando dos veces un identificador: "duplicate identifier").
Ejercicio propuesto: Implementar una pila de strings[20]
Ejercicio propuesto: Implementar una cola de enteros
Ejercicio propuesto: Implementar una lista doblemente enlazada que almacene los datos leídos de un fichero de texto (mejorando el lector de ficheros que vimos)
Ejercicio propuesto: Implementar una lista simple que almacene los datos leídos de un fichero de texto, pero cuyos elementos sean otras listas de caracteres, en vez de strings de tamaño fijo
Ejercicio propuesto: Añadir la función "buscar" a nuestro árbol binario, que diga si un dato que nos interesa pertenece o no al árbol (TRUE cuando sí pertenece; FALSE cuando no).
Ejercicio propuesto: ¿Cómo se borraría un único elemento del árbol?
N.