Recorrido narrado · Borrar en un árbol de búsqueda

El borrado en pseudocódigo

Texto

función borrar(nodo, k):          # devuelve la nueva raíz del subárbol    si nodo = nada: devolver nada    si k < nodo.clave: nodo.izquierdo ← borrar(nodo.izquierdo, k)    si k > nodo.clave: nodo.derecho ← borrar(nodo.derecho, k)    si k = nodo.clave:        si nodo.izquierdo = nada: devolver nodo.derecho        si nodo.derecho = nada: devolver nodo.izquierdo        s ← mínimo(nodo.derecho)        nodo.clave ← s.clave        nodo.derecho ← borrar(nodo.derecho, s.clave)    devolver nodo

Los casos 1 y 2 salen juntos: si falta un hijo, se devuelve el otro (que puede ser nada). Todo el trabajo baja por un camino y quizá baja otra vez por el subárbol derecho: O(h).

En un árbol balanceado, al volver por el camino se recalculan alturas y se rota si hace falta, como al insertar.