Son unas de las estructuras más importantes en las ciencias de la computación. Proporcionan una representación natural para muchas clases de datos y son útiles para resolver una gran variedad de problemas algorítmicos.

Un árbol con tipo base T es un conjunto de uno o más nodos que cumplen:

• Existe un nodo especial llamado raíz considerado el inicio del árbol.
• Los nodos restantes están separados en en n>=0 conjuntos distintos, cada uno de los cuales son a su vez un árbol (subárboles).

              (1)
             /    \
         (2)        (3)
       /  |  \
     (4) (5) (6)

Constituyentes del árbol:

• Nodos: elementos del árbol que almacenan información.
• Conexiones: expresan las relaciones entre los nodos.

Estructura del árbol:

• Nodo raíz: nodo más alto de la jerarquía, a partir del cual están conectados los demás.
• Nodo terminal u hoja: aquel que no contiene ningún subárbol.
• Hijos de un nodo: Aquellos nodos conectados a un nodo mediante enlace directo hacia abajo.
• Descendientes: Nodos que encontramos al movernos hacia abajo en un árbol.
• Ascendientes: Nodos que encontramos al movernos hacia arriba en un árbol.
• Padre de un nodo: Antecesor directo de un nodo.
• Hermanos: nodos hijos del mismo padre.
• Nodos internos: aquellos que tienen a su vez padre e hijos (los no terminales).

Topología del árbol:

• Grado de un nodo: número máximo de hijos del nodo.
• Grado de un árbol: grado máximo de los nodos del árbol.
• Camino entre 2 nodos: sucesión de nodos a visitar (único) para llegar desde un nodo a otro.
• Nivel de un nodo: Es la longitud del camino desde el nodo raíz (nivel 0) hasta ese nodo.
• Altura o profundidad de un árbol: nivel máximo del árbol más uno.
• Arbol vacío: árbol sin nodos ni conexiones.
• Bosque: conjunto de n>=0 árboles disjuntos.

Son árboles de grado 2 (cada nodo tiene, como máximo, 2 hijos). Es o bien un árbol vacío o un nodo que tiene subárboles izquierdo y/o derecho.

              (1)
             /    \
         (2)        (3)
       /     \
     (4)     (5)

• El número de nodos en un nivel i del árbol es como máximo (2 elevado a i).
• El número máximo de nodos de un árbol de altura k es (2 elevado a k)-1.
• Definimos un árbol lleno como aquel cuyos nodos internos llenan completamente todos los niveles, excepto quizás el último.
• Definimos un árbol binario completo (ABC) como un A.B.lleno pero con sus hojas dispuestas de tal manera que las hojas del nivel más bajo están situadas tan a la izquierda como sea posible.

Sea v[i] un vector que represente el árbol mediante el siguiente orden:

     ---------------------------------
     |   |   |   |   |   |   |   |   |
     ---------------------------------
v      0   1   2   3   4   5   6   7

Hijo izquierdo de   v[i] = v[2i]       si 2i <= n
Hijo derecho   de   v[i] = v[2i+1]    si 2i+1 <= n
Padre de            v[i] = v[i/2]        si i > 1
Nodo raíz                = v[1]
                 ( v[i] es una hoja si 2i > n )

typedef struct nodoarbolbin
{
    tipo_info clave;
    struct nodoarbolbin *izq;
    struct nodoarbolbin *der;
} NODOARBOL;
 
NODOARBOL *arbol;

Entendemos por recorrer un árbol visitar (y procesar) cada uno de los nodos que lo componen, una sola vez y en un determinado orden. Existen 3 métodos, los cuales difieren en el órden en que procesamos los nodos, y que comunmente a la hora de entrar en nuevos nodos comienzan por el subárbol izquierdo:

1. Visitar el nodo (y procesarlo).
2. Recorrer el subarbol izquierdo en preorden.
3. Recorrer el subarbol derecho en preorden.

1. Recorrer el subarbol izq en inorden
2. Visitar el nodo (y procesarlo).
3. Recorrer el subarbol der en inorden.

1. Recorrer el subarbol izq en postorden
2. Recorrer el subarbol der en postorden.
3. Visitar el nodo (y procesarlo).

Ejemplo:

void PreOrden( NODOARBOL *nodo )
{
  if( nodo!=NULL)
  {
      procesar(nodo);
      PreOrden(nodo->izq);
      PreOrden(nodo->der);
  }
}

• Coste temporal = O(n) (n=numnodos)
• procesar()=udad tº
• Coste espacial en pila = O(log n) = O(h)

Las operaciones sobre A.B. dependen del tipo de árbol que usemos, el tipo de clave, etc. De modo que las operaciones de inserción, búsqueda, son diferentes para cada tipo de árbol (sólo coinciden Crear y ArbolVacio).

Son árboles binarios que cumplen lo siguiente:

• Todos los nodos están identificados por un campo clave, y no hay 2 elementos con la misma clave.
• Dado un cierto nodo de clave 'x', todos los nodos del subarbol izq tienen una clave <x, y todos los nodos del subarbol der tienen una clave mayor que x.
• Los subárboles izquierdo y derecho son a su vez árboles binarios de búsqueda.

              (10)
             /    \
         (6)        (20)
       /     \
     (1)     (9)

Para encontrar un dato en un ABB se puede utilizar una función como la siguiente:

NODOARBOL *BuscarABB( tipoinfo x, NODOARBOL nodo )      /* version recursiva */
{
   if( nodo == NULL ) return(NULL);
   if( x==nodo->clave ) return( nodo);
   else
   {
       if( x<nodo->clave ) return(BuscarABB( x, nodo->izq);
       else		             return(BuscarABB( x, nodo->der);
    }
}

o bien:

NODOARBOL *BuscarABB( tipoinfo x, NODOARBOL nodo )      /* version iterativa */
{
   NODOARBOL *nd;
   nd = nodo;
   while( nd!=NULL && nd->clave != x )
   {
       if( x < nd->clave )  nd = nd->izq;
       else                 nd = nd->der;
    }
}

Un árbol AVL (Adelson-Velskii y Landis) es un árbol binario de búsqueda equilibrado. Un árbol es equilibrado si los subárboles izquierdo y derecho de cualquier nodo tienen alturas que difieren como mucho en 1. Esta condición asegura que la profundad del árbol sea log(n), siendo n el nº de nodos del árbol. Para mantener un árbol equilibrado se definen unas operaciones llamadas rotaciones tras la inserción o eliminación de elementos.

 ARBOL AVL:

              (1)
             /    \
         (2)        (3)
       /     \
     (4)     (5)

 ARBOL NO AVL:

              (1)
                  \
                    (2)
                      \
                       (3)

Un montículo es un ABC en el que se establece una relación de orden, de tal manera que se cumple que para cada nodo de éste, ninguno de sus 2 hijos tiene un valor mayor que él (montículo de máximos). El montículo de mínimos es aquel en que cada nodo no puede tener hijos con valores menores que él.

MONTICULO DE MAXIMOS:

              (13)
             /    \
         (5)        (10)
       /     \
     (1)     (3)



MONTICULO DE MINIMOS:

              (1)
             /    \
         (4)        (3)
       /     \
     (6)     (7)

Un árbol n-ario o de grado n es un árbol cuyos nodos tienen n o menos hijos, siendo n cualquier valor entero positivo. Su representación puede hacerse de 2 maneras diferentes:

              (1)
             /    \
         (2)        (3)
       /  |   \
     (4) (3)  (5)

A) mediante vectores de punteros para referenciar a los hijos del nodo:

#define MAX_HIJOS 10
struct nodoarboln
{
    tipo_info clave;
    struct nodoarboln *hijo[MAXHIJOS];
} NODOARBOL;

B). Manteniendo todos los hijos en una lista lineal (donde tendremos una referencia al primer hijo, y cada hijo una referencia a su hermano siguiente), una estructura mucho más flexible y que aprovecha mejor la memoria:

struct nodoarboln
{
    tipo_info clave;
    struct nodoarboln *hijo;
    struct nodoarboln *hermanos;
} NODOARBOL;

Ver teoría de grafos en cualquier libro sobre el tema (es bastante complicado dibujar grafos en ascii :).

<Volver a la sección de Tutoriales de Programación>