ARBOLES BINARIOS DE BUSQUEDA
Introduccion
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.
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 a dicha clave o visto de otra forma,una información que puede ser compuesta en la cual existe definido un orden.
La figura 1 muestra dos ABB construidos en base al mismo conjunto de enteros:
.La función puede ser codificada
fácilmente de la siguiente forma:
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 gasto extra de memoria mayor debido a los punteros.
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)
int Pertenece(tElemento x,ABB t)
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);
]
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 la secuencia de comparaciones hecha por una función de búsqueda sobre el vector.
void Inserta(tElemento x,ABB *t)
if(!(*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(x<(t)->etiqueta)
inserta(x,&((t)->hizqda));
else
inserta(x,&((*t)->hdrcha));
ANÁLISIS DE LA EFICIENCIA
DE LAS OPERACIONES.
Es fácil ver que si un árbol binario con 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 inserta toman 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 consumido para seguir el camino es también O(log2n).
Es necesario pues determinar si el ABB promedio con n nodos se acerca en estructura al árbol completo o a la cadena,es decir,si el tiempo medio por operación es O(log2n),O(n) o una cantidad intermedia.
Al construir el árbol,x aparecerá en la raíz,los i elementos más pequeños serán descendientes izquierdos de la raíz y los restantes n-i-1 serán descendientes derechos.Esquemáticamente quedaría como muestra la figura 3.
Al tener tanto en un lado como en otro todos los elementos igual probabilidad se espera que los subárboles izqdo y drcho de la raíz tengan longitudes de camino medias P(i) y P(n-i-1) respectivamente.
El primer término es la longitud del camino promedio en el subárbol izquierdo ponderando su tamaño.
y con unas transformaciones simples podemos ponerla en la forma: