Árboles Binarios de Búsqueda

Un árbol binario de búsqueda es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol.

Un árbol binario de búsqueda (ABB) es un árbol binario definido de la siguiente forma:

Todo árbol vacío es un árbol binario de búsqueda.

Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
• En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo almacenado en el subárbol izquierdo, y que el
subárbol izquierdo sea un árbol binario de búsqueda.
• En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo almacenado en el subárbol derecho, y que el
subárbol derecho sea un árbol binario de búsqueda.

Para una fácil comprensión queda resumido en que es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores.

Para estas definiciones se considera que hay una relación de orden establecida entre los elementos de los nodos. Que cierta relación este definida, o no, depende de cada lenguaje de programación. De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos.

El interés de los árboles binarios de búsqueda radica en que su recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.

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 número de comparaciones que necesitaríamos para saber si un elemento se encuentra en un árbol binario de búsqueda estaría entre [log2(N+1)] y N, siendo N el numero 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.

data Buscar_ABB(abb t,clave k)
{
abb p;
dato e;
e=NULL;
p=t;
if (!estaVacio(p))
{
while (!estaVacio(p) && (p->k!=k) )
{
if (k <>k)
{
p=p->l;
}
if (p->k < p="p-">r;
}
}
if (!estaVacio(p) &&(p->d!=NULL) )
{
e=copiaDato(p->d);
}
}
return e;
}
[+/-] Ejemplo Iterativo de busqueda ...

Véase ahora la versión recursiva en ese mismo lenguaje:

int buscar(tArbol *a, int elem)
{
if (a == NULL)
return 0;
else if (a->clave <>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.

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.

Nodo a eliminar 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.

Nodo a eliminar 70

--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:

Nodo a eliminar 59

El siguiente algoritmo en C realiza el borrado en un ABB. El procedimiento reemplazar busca la mayor clave del subárbol izquierdo y la asigna al nodo a eliminar.

void borrar(tArbol **a, int elem)
{
void reemplazar(tArbol **a, tArbol **aux);
tArbol *aux;

if (*a == NULL)
return;

if ((*a)->clave <>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);
}


Recorridos

Se puede hacer un recorrido de un árbol en profundidad o en anchura.

Los recorridos en anchura son por niveles, se realiza horizontalmente desde la raíz a todos los hijos antes de pasar a la descendencia de alguno de los hijos.

El recorrido en profundidad lleva al camino desde la raíz hacia el descendiente más lejano del primer hijo y luego continúa con el siguiente hijo. Como recorridos en profundidad tenemos inorden, preorden y postorden.

Una propiedad de los ABB es que al hacer un recorrido en profundidad inorden obtenemos los elementos ordenados de forma ascendente.

Ejemplo árbol binario de búsqueda

Resultado de hacer el recorrido en:

Inorden = [6, 9, 13, 14, 15, 17, 20, 26, 64, 72].
Preorden = [15, 9, 6, 14, 13, 20, 17, 64, 26, 72].
Postorden =[6, 13, 14, 9, 17, 26, 72, 64, 20, 15].

[+/-] Leer más...