Este sitio web usa cookies de terceros para analizar el tráfico y personalizar los anuncios. Si no está de acuerdo, abandone el sitio y no siga navegando por él. ×


9.6. Árboles binarios

###

type
    puntero = ^ nodo;

En las listas, cada elemento tiene un siguiente. Esto supone que, cuando busquemos un dato, en el mejor de los casos se encuentre en la primera posición, y en el peor de los casos se encuentre en la última posición. Eso supone que como medida, podamos respetar que un dato se encuentre en n/2 pasos. Es decir, si buscamos números al azar en un conjunto de 1.000, como medida necesitaremos 500 comparaciones para encontrarlo. Con un millón de datos, sería esperable hacer cerca de 500.000 comparaciones. Eso mejora ligeramente si los datos están ordenados, pero sigue siendo un coste relativamente alto. Si queremos una mejora sustancial de velocidad, hay que cambiar el planteamiento. ### Una estructura alternativa, que hace que las búsquedas sean más rápidas, es que cada elemento tenga más de un sucesor. Por ejemplo, si cada elemento tiene dos "hijos", uno que sea menor que él y otro que sea mayor que él, la estructura que obtenemos no es lineal, como en las listas, sino ramificada, un "árbol". En una estructura como esa, si tuviéramos 1.000 datos (perfectamente equilibrados, algo en lo que no profundizaremos todavía), bastaría con 10 comparaciones para ver si existe un dato concreto. Y si fuera un millón de datos, sólo necesitaríamos 20 comparaciones. La diferencia es abismal. Vamos a detallar un poco más y a ver un ejemplo.... ###

Un árbol es 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 (es decir, 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 
### Una operación adicional que podríamos hacer, y en la que vamos a profundizar, es "equilibrar" el árbol, para que no haya un desnivel entre ramas superior a uno. Por ejemplo, una estructura como se convertiría en algo como

Haciendo este paso adicional cada vez que sea necesario, el número máximo de comparaciones que tendríamos que hacer sería log2( n ), lo que supone que si tenemos 1.000. 000 datos, en una lista podríamos llegar a tener que hacer 1.000. 000 comparaciones en el peor caso, mientras que en un arbol binario serán log2(1000000) => 20 comparaciones como máximo. Pero no veremos cómo programar ese tipo de operaciones, que son propias de un curso de programación más avanzado, o incluso de uno de "Tipos Abstractos de Datos" o de "Algorítmica", y nos centraremos en la operaciones básicas, como añadir un dato o mostrar todo el árbol. ###

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

#####

¿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.