OPERACIONES BÁSICAS SOBRE ÁRBOLES BINARIOS DE BÚSQUEDA

Búsqueda

La búsqueda consiste acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica. El maximo número de comparaciones que necesitaríamos para saber si un elemento se encuentra en un árbol binario de búsqueda estaría entre [log₂(N+1)] y N, siendo N el número de nodos. La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) se puede realizar de dos formas, iterativa o recursiva.

La versión recursiva:

int buscar(tArbol *a, int elem)

{

  if (a == NULL)

    return 0;

  else if (a->clave < elem)

    return buscar(a->hDerecho, elem);

  else if (a->clave > elem)

    return buscar(a->hIzquierdo, elem);

  else

    return 1;

}

Inserción

La inserción es similar a la búsqueda y 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. Si no lo está, 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.

void insertar(tarbol **a, int elem)

{

  if (*a == NULL) {

    *a = (arbol *) malloc(sizeof(arbol));

    (*a)->clave = elem;

    (*a)->izq = (*a)->der = NULL;

  }

  else if ((*a)->clave < elem) insertar(&(*a)->der, elem);

  else if ((*a)->clave > elem) insertar(&(*a)->izq, elem);

}

Borrado

La operación de borrado no es tan sencilla como las de búsqueda e inserción. Existen varios casos a tener en consideración:

• Borrar un nodo sin hijos ó nodo hoja: simplemente se borra y se establece a nulo el apuntador de su padre.

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

• Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho). En la siguiente figura se muestra cómo existe la posibilidad de realizar cualquiera de ambos reemplazos:

Codificación: el procedimiento sustituir es el que desciende por el árbol cuando se da el caso del nodo con descencientes por ambas ramas.

void borrar(tarbol **a, int elem)

{

  void sustituir(tarbol **a, tarbol **aux);

  tarbol *aux;

  if (*a == NULL) /* no existe la clave */

    return;

  if ((*a)->clave < elem) borrar(&(*a)->der, elem);

  else if ((*a)->clave > elem) borrar(&(*a)->izq, elem);

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

    aux = *a;

    if ((*a)->izq == NULL) *a = (*a)->der;

    else if ((*a)->der == NULL) *a = (*a)->izq;

    else sustituir(&(*a)->izq, &aux); /* se sustituye por

      la mayor de las menores */

    free(aux);

  }

}

-Bibliografia
http://es.wikipedia.org/wiki/%C3%81rbol_binario_de_b%C3%BAsqueda
http://www.algoritmia.net/articles.php?id=17