ARBOLES DE BÚSQUEDA BINARIA

Arboles de búsqueda Binaria

La búsqueda en árboles binarios es un método de búsqueda simple, dinámico y eficiente considerado como uno de los fundamentales en Ciencia de la Computación. De toda la terminología sobre árboles, tan sólo recordar que la propiedad que define un árbol binario es que cada nodo tiene a lo más un hijo a la izquierda y uno a la derecha. Para construir los algoritmosconsideraremos que cada nodo contiene un registro con un valor clave a través del cual efectuaremos las búsquedas.

En las implementaciones que presentaremos sólo se considerará en cada nodo del árbol un valor del tipo t Elemento aunque en un caso general ese tipo estará compuesto por dos: una clave indicando el campo por el cual se realiza la ordenación y una información asociada a dicha clave ovisto de otra forma, una información que puede ser compuesta en la cual existe definido un orden.

Un árbol binario de búsqueda(ABB) es un árbol binario con la propiedad de que todos los elementos almacenados en el subárbol izquierdo de cualquier nodo x son menores que el elemento almacenado en x ,y todos los elementos almacenados en el subárbol derecho de x son mayores que el elementoalmacenado en x.

La figura 1 muestra dos ABB construidos en base al mismo conjunto de enteros:

Obsérvese la interesante propiedad de que si se listan los nodos del ABB en in-orden nos da la lista de nodos ordenada. Esta propiedad define un método de ordenación similar al Quicksort, con el nodo raíz jugando un papel similar al del elemento de partición del Quicksort aunque con los ABB hay un gastoextra de memoria mayor debido a los punteros. La propiedad de ABB hace que sea muy simple diseñar un procedimiento para realizar la búsqueda. Para determinar si k está presente en el árbol la comparamos con la clave situada en la raíz, r. Si coinciden la búsqueda finaliza con éxito, si khizda = NODO_NULO;
raiz->hdcha = NODO_NULO;
raiz->etiqueta = et;
return(raiz);
}


intPertenece(tElemento x,ABB t)
{

if(!t)
return FALSE
else if(t->etiqueta==x)
return TRUE;
else if(t->etiqueta>x)
return pertenece(x,t->hizqda);
else return pertenece(x,t->hdrcha);
}


Es conveniente hacer notar la diferencia entre este procedimiento y el de búsqueda binaria.En éste podría pensarse en que se usa un árbol binario para describir lasecuencia de comparaciones hecha por una función de búsqueda sobre el vector.En cambio en los ABB se construye una estructura de datos con registros conectados por punteros y se usa esta estructura para la búsqueda.El procedimiento de construcción de un ABB puede basarse en un procedimiento de inserción que vaya añadiendo elementos al árbol. Tal procedimiento comenzaría mirando si el árbol es vacíoy de ser así se crearía un nuevo nodo para el elemento insertado devolviendo como árbol resultado un puntero a ese nodo.Si el árbol no está vacio se busca el elemento a insertar como lo hace el procedimiento pertenece sólo que al encontrar un puntero NULL durante la búsqueda,se reemplaza por un puntero a un nodo nuevo que contenga el elemento a insertar.El código podría ser el siguiente:void Inserta(tElemento x,ABB *t)
{

if(!(*t)){
*t=(nodoABB)malloc(sizeof(struct tipoceldaABB));
if(!(*t)){
error("Memoria Insuficiente.");
}
(*t)->etiqueta=x;
(*t)->hizqda=NULL;
(*t)->hdrcha=NULL;
} else if(xetiqueta)
inserta(x,&((*t)->hizqda));
else
inserta(x,&((*t)->hdrcha));
}


Por ejemplo supongamos que queremosconstruir un ABB a partir del conjunto de enteros {10,5,14,7,12} aplicando reiteradamente el proceso de inserción.El resultado es el que muestra la figura 2.




2. ANÁLISIS DE LA EFICIENCIA DE LAS OPERACIONES.

Puede probarse que una búsqueda o una inserción en un ABB requiere (log2n) operaciones en el caso medio, en un árbol construido a partir de n claves aleatorias, y en el peor caso una...