ArbolesBB



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ón guardada en el nodo T. De
forma similar, todoslos valores
almacenados en el subárbol derecho de T
deben ser mayores o iguales a la
información guardada en el nodo T

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 se cumpla
alguna de las siguientes condiciones:
El subárbol derecho, o elsubárbol izquierdo, es
igual a vacío, en cuyo caso se procederá a insertar
el elemento en el lugar que le corresponde.
La clave que se quiere insertar está en el nodo
analizado, por lo tanto no selleva a cabo la
inserción. (Sólo cuando no se repitan elementos)



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

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



Consiste en eliminar un nodo sin
violar losprincipios que definen un
árbol binario de búsqueda (ABB). Se
deben distinguir los siguientes casos:

1.

2.

3.

Si el elemento a eliminar es terminal u hoja,
simplemente se suprime redefiniendo el
punterode 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 tieneque sustituir
por el nodo que se encuentra más a la
izquierda en el subárbol derecho ó por el
nodo que se encuentra más a la derecha en el
subárbol izquierdo.

Cabe destacar que antes de eliminar unnodo,
se debe localizar éste en el árbol.
Supongamos que se desea eliminar las
siguientes claves del árbol binario de búsqueda
indicado: 120
22, 99, 87, 120, 140, 135, 56
140

87
99

43
65

22

56...