FAQ - Árbol Binario de Búsqueda
¿Cómo se destruye un dato en un ABB?
Recomendamos seguir este algoritmo para destruir datos en un árbol binario de búsqueda: después de localizar el nodo a eliminar se consideran tres casos:
- Si el nodo es una hoja (es decir: no tiene hijos), se elimina.
- Si el nodo tiene un solo hijo, se elimina el nodo y se reemplaza con su hijo.
- Si el nodo tiene dos hijos no se elimina el nodo, sino que se reemplaza con el siguiente inorder (es decir, con el menor de sus hijos mayores) o con el anterior inorder (el mayor de sus hijos menores). Para esto, se llama a la primitiva de Borrar con dicho reemplazante, y luego se pisan la clave y dato del nodo que contiene la clave que realmente queríamos borrar. Como se eligió o bien el menor de sus hijos mayores o el mayor de sus hijos menores, obligatoriamente al nodo a borrar le va a faltar un hijo, haciendo que se caiga en alguno de los dos primeros casos.