Busqueda binaria analisis

ARBOLES BINARIOS DE BUSQUEDA




1. INTRODUCCIÓN.
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 construirlos algoritmos consideraremos 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 tElemento 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 adicha clave o visto 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 inorden 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 k #define ABB_VACIO NULL
#define TRUE 1
#define FALSE 0

typedef int tEtiqueta /*Algun tipo adecuado*/
typedef struct tipoceldaABB{
struct tipoceldaABB *hizqda,*hdrcha;
tEtiqueta etiqueta;
}*nodoABB;
typedef nodoABB ABB;




ABB Crear(tEtiqueta et)
{ABB raiz;

raiz = (ABB)malloc(sizeof(struct tceldaABB));
if (raiz == NULL)
error("Memoria Insuficiente.");
raiz->hizda = NODO_NULO;
raiz->hdcha = NODO_NULO;
raiz->etiqueta = et;
return(raiz);
}


int Pertenece(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);
}


ANÁLISIS DE LA EFICIENCIA DE LAS OPERACIONES.
Puede probarse que una búsqueda o una inserción en un ABB requiere O(log2n) operaciones en el caso medio,en un árbol construido a partir de n claves aleatorias, y en el peor caso una búsqueda en un ABB con n claves puede implicar revisar las n claves,o sea,es O(n).
Es fácil ver que si un árbol binariocon n nodos está completo (todos los nodos no hojas tienen dos hijos) y así ningún camino tendrá más de 1+log2n nodos.Por otro lado,las operaciones pertenece e insertatoman una cantidad de tiempo constante en un nodo.Por tanto,en estos árboles, el camino que forman desde la raíz,la secuencia de nodos que determinan la búsqueda o la inserción, es de longitud O(log2n),y el tiempo total consumidopara seguir el camino es también O(log2n).
Sin embargo,al insertar n elementos en un orden aleatorio no es seguro que se sitúen en forma de árbol binario completo.Por ejemplo,si sucede que el primer elemento(de n situados en orden) insertado es el más pequeño el árbol resultante será una cadena de n nodos donde cada nodo,excepto el más bajo en el árbol,tendrá un hijo derecho pero no un hijo...

Leer documento completo

Regístrate para leer el documento completo.