chavez

Arboles binarios de búsqueda: Un árbol de búsqueda binaria es una estructura apropiada para muchas de las aplicaciones que se han discutido anteriormente con listas. La ventaja especial de utilizarun arbol es que se facilita la búsqueda. Un árbol binario de búsqueda es aquel en el que el hijo de la izquierda (si existe) de cualquier nodo contiene un valor más pequeño que el nodo padre, y elhijo de la derecha (si existe) contiene un valor más grande que el nodo padre.
Un ejemplo de arbol binario de búsqueda es el siguiente:


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 elelemento 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 maximo número decomparaciones 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 de Bú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 unnodo 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;
}
Véase ahora la...