Arboles binarios

REPUBLICA BOLIVARIANA DE VENEZUELA
MININISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL
DE LA FUERZA ARMADA NACIONAL
“UNEFA”
PROGRAMACION

[pic]

INTEGRANTE:
Omar Telleria

Sección: IS5D-A

Santa Ana de Coro, julio del 2010

ARBOLES BINARIOS DE BUSQUEDA

La búsqueda en árboles binarios es un método de búsqueda simple, dinámico y eficienteconsiderado 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 algoritmos consideraremos que cada nodo contiene un registro con un valor clave a través del cual efectuaremos las búsquedas. En lasimplementaciones 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.
Un árbol binario debú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 elemento almacenado en x.
La figura 1 muestra dos ABB construidos en base al mismo conjunto de enteros:

[pic]

Obsérvese lainteresante 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. La propiedad de ABB hace que sea muy simple diseñar un procedimientopara 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);
}

int Pertenece(tElemento x,ABB t)
{

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

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 sidoencontrado 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 máximo 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 número de nodos. La búsqueda de un elemento en un ABB (Árbol Binario deBúsqueda) se puede realizar de dos formas, iterativa o recursiva.
Ejemplo de versión iterativa en el lenguaje de programación C, suponiendo que estamos buscando una clave alojada en un nodo donde está el correspondiente "dato" que precisamos encontrar:
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 < p->k)
{
p=p->l;
}
if (p->k < k)
{
p=p->r;
}
}
if (!estaVacio(p) &&(p->d!=NULL) )
{
e=copiaDato(p->d);
}
}
return e;
}

Inserción

La inserción es similar a la búsqueda y se puede dar una solución tanto...