Curso de Pascal, por Nacho Cabanes

AnteriorPosterior

Tema 13: Variables dinámicas (2: árboles binarios)

  Curso: Curso de Pascal, por Nacho Cabanes

Tema 13.4: Variables dinámicas (4).

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:

  • Una pila es un caso particular de lista, en la que los elementos siempre se introducen y se sacan por el mismo extremo (se apilan o se desapilan). Es como una pila de libros, en la que para coger el tercero deberemos apartar los dos primeros (excluyendo malabaristas, que los hay). Este tipo de estructura se llama LIFO (Last In, First Out: el último en entrar es el primero en salir).
  • Una cola es otro caso particular, en el que los elementos se introducen por un extremo y se sacan por el otro. Es como se supone que debería ser la cola del cine: los que llegan, se ponen al final, y se atiende primero a los que están al principio. Esta es una estructura FIFO (First In, First Out).


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").

Tema 13.5: Ejercicios.

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.

Actualizado el: 08-07-2012 12:13

AnteriorPosterior

 

En los foros