Ensayo De Arboles Binarios De Busqueda (ABB)

ÁRBOL BINARIO DE BÚSQUEDA (ABB)

El árbol binario de búsqueda es una estructura sobre la cual se pueden realizar eficientemente las operaciones de búsqueda, inserción y eliminación.

En las listas, las operaciones de inserción y eliminación se pueden llevar a cabo con facilidad, sin embargo la búsqueda es una operación bastante costosa que incluso nos puede llevar a recorrer todos los elementos de ella para localizar uno en particular.

 Reglas a cumplir:

 Cada nodo del árbol puede tener 0, 1 ó 2 hijos.

 Los descendientes izquierdos deben tener un valor menor al padre.

 Los descendientes derechos deben tener un valor mayor al padre.

¿Por qué son ABB?

¿Por qué no son ABB?

Ejemplo

También es posible observar que si se efectúa un recorrido inorden sobre un árbol de búsqueda se obtendrá una clasificación de los nodos en forma ascendente.

El recorrido inorden del árbol de la figura anterior produce el siguiente resultado:

22-43-56-65-87-93-99-120-130-135-140

BÚSQUEDA EN UN ÁRBOL BINARIO DE BÚSQUEDA

BÚSQUEDA (NODO, INFOR )

1. Si INFOR < NODO^.INFO

entonces

1.1 Si NODO^.IZQ = NIL

entonces

Escribir “El ncdo no se encuentra en el árbol”

si no

Regresar a BÚSQUEDA con N0DO^.IZQ e INFOR {Llamada recursiva}

1.2 { Fin del condicional del paso 1.1}

si no

1.3 Si INFOR> NODO^.INFO

entonces

1.3.1 Si NODO^.DER = NIL

entonces

Escribir “El nodo no se encuentra en el árbol”

si no

Regresar a BUSQUEDA con NODO^.DER e INFOR

{ Llamada recursiva)

1.3.2 (Fin del condicional del paso 1.3.1

si no

Escribir “El nodo se encuentra en el árbol”

1.4 { Fin del condicional del paso 1.3}

2. { Fin del condicional del paso 1}

BUSQUEDA1 (NODO, INFOR)

1. Si NODO ≠ NIL

entonces

1.1 Si INFOR < NODO^.INFO

entonces

Regresa a BÚSQUEDA1 con NODO^.IZQ e INFOR {Llamada recursiva}

si no

1.1.1 Si INFOR > NODO^.INFO

entonces

Regresa a BÚSQUEDA1 con NODO^.DER e INFOR {Llamada recursiva}

si no

Escribir “El nodo se encuentra en el árbol”

1.1.2 {Fin del condicional del paso 1.1.1}

1.2 {Fin del condicional del paso 1.1}

si no

Escribir “El nodo no se encuentra en el árbol”

2. {Fin del condicional del paso 1}

INSERCIÓN EN UN ÁRBOL BINARIO DE BÚSQUEDA

La inserción es una operación que se puede realizar eficientemente en un árbol binario de búsqueda. La estructura crece conforme se inserten elementos al árbol. Los pasos que deben realizarse para insertar un elemento a un árbol binario de búsqueda son los siguientes:

1. Debe compararse la clave a insertar con la raíz del árbol. Si es mayor, debe avanzarse hacia el subárbol derecho. Si es menor, debe avanzarse hacia el subárbol izquierdo.

2. Repetir sucesivamente el paso 1 hasta que se cumpla alguna de las siguientes condiciones:

2.1 LI subárbol derecho es igual a vacío, o el subárbol izquierdo es igual a vació; en cuyo caso se procederá a insertar el elemento en el lugar que le corresponde.

2.2 La clave que quiere insertarse es igual a la raíz del árbol; en cuyo caso no se realiza la inserción.

Ejemplo:

Supóngase que quieren insertarse las siguientes claves en un árbol binario de búsqueda que se encuentre vacío:

claves: 120-87 - 43-65-140-99- 130-22-56

Los resultados parciales que ilustran cómo funciona el procedimiento se presentan en las figuras que siguen:

INSERCIÓN EN UN ÁRBOL BINARIO DE BÚSQUEDA

INSERCIÓN (NODO, INFOR)

1. Si INFOR < NODO^.INFO

entonces

1.1 Si NODO^.IZQ = NIL

entonces

CREA (OTRO) {Crear un nuevo nodo}

Hacer OTRO^.IZQßNIL, OTRO^.DERßNIL, OTRO^.INFOßINFOR y

NODO^.IZQßOTRO

si no

Regresar a INSERCIÓN con NODO^.IZQ e INFOR

...