Arboles ABB

Árboles Binarios de Búsqueda
Definición

• Para todo nodo T del árbol, se debe
cumplir que todos los valores
almacenados en el subárbol izquierdo de
T sean menores o iguales a la
informaciónguardada en el nodo T. De
forma similar, todos los valores
almacenados en el subárbol derecho de T
deben ser mayores o iguales a la
información guardada en el nodo T

INSERCIÓN
1.

2.Comparar la clave a insertar con la raíz del árbol.
Si es mayor, se sigue con el subárbol derecho. Si
es menor, se continúa con el subárbol izquierdo.
Repetir sucesivamente el paso 1 hasta que secumpla alguna de las siguientes condiciones:
El subárbol derecho, o el subárbol izquierdo,
es igual a vacío, en cuyo caso se procederá a
insertar el elemento en el lugar que le
corresponde.
La claveque se quiere insertar está en el nodo
analizado, por lo tanto no se lleva a cabo la inserción.
(Sólo cuando no se repitan elementos)

EJEMPLO
• Se quiere insertar las siguientes claves en
unárbol de búsqueda que se encuentra
vacío:

120, 87, 43, 65, 140, 99, 130, 22, 56

EJERCICIO
• Insertar las siguientes claves en un árbol
binario de búsqueda que se encuentra
vacío:5,21,9,15,74,90,50,14,35,42,7,12,58,28,1

ELIMINACIÓN
• Consiste en eliminar un nodo sin violar
los principios que definen un árbol
binario de búsqueda (ABB). Se deben
distinguir los siguientes casos:ELIMINACIÓN
1.

2.

3.

Si el elemento a eliminar es terminal u hoja,
simplemente se suprime redefiniendo el
puntero de su predecesor.
Si el elemento a eliminar tiene un solo
descendiente,entonces tiene que sustituirse
por ese descendiente.
Si el elemento a eliminar tiene los dos
descendientes, entonces se tiene que sustituir
por el nodo que se encuentra más a la
izquierda en elsubárbol derecho ó por el nodo
que se encuentra más a la derecha en el
subárbol izquierdo.

ELIMINACIÓN
Cabe destacar que antes de eliminar un nodo, se
debe localizar éste en el árbol....