Diferencia entre revisiones de «Árbol binario de búsqueda»

 

* '''Borrar un nodo sin hijos o nodo hoja''': simplemente se borra y se establece a nulo el apuntador de su padre.

* '''Borrar un nodo con un subárbol hijo''': se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.

* '''Borrar un nodo con dos subárboles hijo''': la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho). En la siguiente figura se muestra cómo existe la posibilidad de realizar cualquiera de ambos reemplazos:

 

El siguiente algoritmo en [[Lenguaje de programación C|C]] realiza el borrado en un ABB. El procedimiento ''reemplazar'' busca la mayor clave del subárbol izquierdo y la asigna al nodo a eliminar.