Arboles binarios

Un árbol binario es un conjunto de finito de elementos, cuyo nombre es nodos de forma que cada nodo tiene dos hijos, un hijo izquierdo y uno derecho, no es posible que tengan más de dos hijos, si el árbol binario es vació si no tiene ningún elemento en el.

Algunos de los usos más comunes que tienen estos arboles son los de: árboles binarios de búsqueda, montículos binarios, y codificación de Huffman.

Imagen que demuestra la apariencia de un árbol binario.

Estructura de un árbol binario

Un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo b es hijo de un nodo a si existe un enlace desde b hasta a. Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Cada nodo tiene un dato, para el ordenamiento necesita una función de procedencia (de origen) y una regla de orden (esta regla implementa el orden relativo de los datos padre e hijos), el grado de un nodo es la cantidad de hijos que tiene (máximo dos).

Estructura típica de un nodo.

La profundidad de un nodo es el camino de la raíz al nodo, la profundidad de un árbol es la profundidad de la hoja más profunda.

Análisis asintótico 

n = número de nodos que contiene el árbol
Un árbol balanceado con n = 8 y profundidad tres

El peor caso de falta de balance para n = 8 tiene profundidad seis

Asintóticamente lineal.

Rotaciones

Ayudan a entender un problema cuando un nodo es capaz de detectar in imbalance (esto sucede cuando se agrega o elimina un nodo del árbol), estas rotaciones proceden recursivamente hasta la raíz hasta que no haya imbalance.

Existen cuatro distintos tipos de rotación, como:

Imagen que demuestra la rotación simple izquierda.

Imagen que demuestra la rotación simple derecha.

Imagen que demuestra la rotación doble izquierda-derecha.

Imagen que demuestra la rotación doble derecha-izquierda.

Condiciones de rotación

Estas son las condiciones que se tienen que llevar a cabo para poder realizar la operación de rotaciones.

Inserción

La inserción se puede dar una solución tanto iterativa como recursiva. Si tenemos inicialmente como parámetro un árbol vacío se crea un nuevo nodo como único contenido el elemento a insertar. En caso de que no este, se comprueba si el elemento dado es menor que la raíz del árbol inicial con lo que se inserta en el sub-árbol izquierdo y si es mayor se inserta en el sub-árbol derecho. De esta forma las inserciones se hacen en las hojas.

Proceso de inserción, número 5.

Ejemplo de pseudocódigo de inserción

PROC InsertarABB(árbol:TABB; dato:TElemento)

VARIABLES

   nuevonodo,pav,pret:TABB

   clavenueva:Tclave

   ele:TElemento

INICIO

   nuevonodo <- NUEVO(TNodoABB)

   nuevonodo^.izq <- NULO

   nuevonodo^.der <- NULO

   nuevonodo^.elem <- dato

   SI ABBVacío (árbol) ENTONCES

      árbol <- nuevonodo

   ENOTROCASO

      clavenueva <- dato.clave

      pav <- árbol                // Puntero Avanzado

      pret <- NULO                // Puntero Retrasado

      MIENTRAS (pav <- NULO) HACER

          pret <- pav

          ele = pav^.elem

          SI (clavenueva < ele.clave ) ENTONCES

               pav <- pav^.izq 

          EN OTRO CASO

               pav <- pav^.dch

          FINSI

      FINMIENTRAS

      ele = pret^.elem

      SI (clavenueva < ele.clave ) ENTONCES

          pret^.izq <- nuevonodo 

      EN OTRO CASO

          pret^.dch <- nuevonodo 

      FINSI

   FINSI

FIN

Eliminación

La operación de borrado no es tan sencilla. Existen varios casos que tenemos que considerar:
Borrar un nodo sin hijos o nodo hoja: simplemente se borra y se establece a NULL el apuntador de su padre.

Aquí se borra el nodo "74".

Borrar un nodo con un sub-árbol hijo: se borra el nodo y se asigna su sub-árbol hijo como sub-árbol de su padre.

Aquí se elimina el nodo "70".

Borrar un nodo con dos sub-árboles hijo: la solución está en reemplazar el valor del nodo por el de su padre o por el de su hijo en inorden y posteriormente borrar este nodo. Su padre en inorden será el nodo más a la derecha de su sub-árbol izquierdo (mayor nodo del sub-arbol izquierdo), y su hijo el nodo más a la izquierda de su sub-árbol derecho (menor nodo del subarbol derecho).

Aquí se elimina el nodo "59".

Ejemplo de codificación de eliminación

void borrar(tArbol **a, int elem)

{

  void reemplazar(tArbol **a, tArbol **aux);

  tArbol *aux;

 

  if (*a == NULL)

    return;

 

  if ((*a)->clave < elem)

    borrar(&(*a)->hDerecho, elem);

  else if ((*a)->clave > elem)

    borrar(&(*a)->hIzquierdo, elem);

  else if ((*a)->clave == elem)

  {

    aux = *a;

    if ((*a)->hIzquierdo == NULL)

      *a = (*a)->hDerecho;

    else if ((*a)->hDerecho == NULL)

      *a = (*a)->hIzquierdo;

    else

      reemplazar(&(*a)->hIzquierdo, &aux);

 

    free(aux);

  }

}

 

void reemplazar(tArbol **a, tArbol **aux)

{

  if ((*a)->hDerecho == NULL)

  {

    (*aux)->clave = (*a)->clave;

    *aux = *a;

    *a = (*a)->hIzquierdo;

  }

  else

    reemplazar(&(*a)->hDerecho, aux);

}

Referencias:

Árbol binario
Árbol binario de búsqueda
Estructura de árbol binario
Rotaciones