Eliminación en un árbol de búsqueda binaria

Suponga que T es un árbol de búsqueda binaria, y suponga un ITEM de información dado. Esta sección da un algoritmo que elimina ITEM del árbol T.

El algoritmo de eliminación, para encontrar la posición del nodo N que contiene a ITEM, así como la posición del nodo padre p(N). la forma en que N es eliminado del árbol depende principalmente del número de hijos de N. existen tres casos.

Caso1.- N no tiene hijos. Entonces se elimina de T simplemente reemplazado la                                      

              Posición de N en p(N) por el puntero nulo.

Caso 2.- N tiene exactamente un hijo. Entonces N se elimina de T simplemente

                  Reemplazado la posición de N en P(N) por la posición del hijo único de

                 N.

Caso 3.- N tiene dos  sea S(N) el sucesor inorden de N. [el elector puede verificar que S(N) no tiene hijo izquierdo,] entonces N es eliminado de T primero eliminando  S(N) de T (mediante los casos 1 ó 2) y luego reemplazando N en T por el nodo S(N).

Observe que el tercer paso es mucho más complicado que los dos primeros, en los tres casos, el espacio de memoria del nodo N eliminando se devuelve a la lista DISP.

		INFO	IZQ	DER
RAIZ	1	33	0	9
3	2	25	8	10
	3	60	2	4
	4	66	0	0
DISP	5		6
7	6		0
	7		5
	8	15	0	0
	9	44	0	0
	10	50	1	0