Análisis de AlgoritmosEliminar un elemento de un árbol binario de búsqueda

Eliminación de un elementoLa eliminación de un nodo de un árbol binario de búsqueda es más complicada que la inserción, puesto que puede suponer la recolocación de varios de sus nodos. En líneas generales un posible esquema para abordar esta operación es el siguiente:

1. Buscar el nodo que se desea borrar manteniendo un enlace a su padre (p)2. Si se encuentra el nodo hay que contemplar tres casos posibles:a. Si el nodo a borrar no tiene hijos, simplemente se libera el espacio que ocupab. Si el nodo a borrar tiene un solo hijo, se añade como hijo de su padre (p), sustituyendo la posición ocupada por el nodo borrado.c. Si el nodo a borrar tiene los dos hijos se siguen los siguientes pasos:

i. Se busca el máximo de la rama izquierda o el mínimo de la rama derecha.ii. Se sustituye el nodo a borrar por el nodo encontrado.

Veamos gráficamente varios ejemplos de eliminación de un nodo:

L.I. María Luis Velasco Ramírez 1

Análisis de AlgoritmosEliminar un elemento de un árbol binario de búsqueda

public boolean delete (int llave){ Nodo actual = raíz; Nodo p = raíz; Bolean hijoizq= trae;

while (actual.iDato != llave) { p= actual; if (llave < actual.iDato) { hijoizq= trae; actual.actual.izq // va a la izquierda } else { hijoezq= false; actual= actual.der // va a la derecha } if (actual == null) // no lo encontro return false; } // fin while

// encontro el nodo a borrar

// si no tiene hijo, simplemente lo borra

if (actual.izq == null && actual.der == null) { (if actual == raiz) // si es la raíz root = null; // el árbol esta vacío else if(hijoizq) p.izq = null //lo desconecta de p else p.der = null; }

// si no tiene hijo derecho, lo reemplaza con el subárbol izquierdoelse if( actual.der == null) if (actual == raiz) raiz = actual.izq; else if (hijoizq) p.izq =actual.izq; else p.der= actual.izq; // si no tiene hijo izquierdo, lo reemplaza con el subarbol derecho else if (actual.izq == null)

L.I. María Luis Velasco Ramírez 2

Análisis de AlgoritmosEliminar un elemento de un árbol binario de búsqueda

if (actual == raiz) raiz = actual.der;

else if (hijoizq) p.izq =actual.der;

else p.der= actual.der;

else // tiene dos hijos, es reemplazado por el sucesor { // llama al metodo obtener sucesor del nodo a borrar (actual) Nodo sucesor = getSucesor (actual);

// conecta p de actual con el sucesor

if (actual ==raiz) raiz = sucesor; else if (hijoizq) p.izq= sucesor; else p.der=successor; successor.izq = actual.izq //conecta sucesor con la rama izq de actual } //fin tiene dos hijos return trae; } fin borrar

private Nodo getSucesor(Nodo delNodo) { Nodo sucerorp= delNodo; Nodo sucesor = delNodo; Nodo actual= delNodo.der; / va al hijo derecho while (actual != null) { sucesorp = sucesor; sucesor = actual; actual = actual.izq; } // if (sucesor != delNodo.der) { sucesorp.izq= sucesor.der; sucesor.der = delNodo.der; } return sucesor;

} // fin getSucesor

L.I. María Luis Velasco Ramírez 3

Análisis de AlgoritmosEliminar un elemento de un árbol binario de búsqueda

Nota: getSucesor encuentra el mínimo de la rama derecha

TAREA para la siguiente clase.Implementa el método getSucesor para encontrar el máximo de la rama izquierda.

L.I. María Luis Velasco Ramírez 4