¿Cuál es el mejor algoritmo para eliminar cualquier nodo en un BST?

Los mejores algoritmos posibles para BST son siempre aquellos en los que la altura del árbol disminuye o permanece igual. Tal algoritmo para la eliminación de un elemento es el siguiente.
Encuentre el nodo que desea eliminar, digamos N, atravesando el BST por el recorrido de profundidad primero. Se deben manejar 3 casos.
Caso I: el nodo no tiene hijos.
Simplemente elimine el elemento y ya está.
Caso II: el nodo tiene un hijo.
Eliminar N. Ahora solo adjunte el subárbol cuya raíz es el hijo de N, al padre de N, reemplazando así el lugar ocupado anteriormente por N por su hijo.
Caso III: el nodo tiene dos hijos.
Hay dos formas en que puedes hacer esto. Describiré uno; el otro es análogo. Primero encuentre el elemento del BST que viene justo antes de N en el recorrido en orden del BST. Puede hacer esto yendo al hijo izquierdo de N, y luego moviéndose a la derecha en el BST (es decir, yendo al hijo derecho del nodo) continuamente hasta llegar a un nodo sin hijo derecho, diga M. Ahora, simplemente reemplace el contenido de N por M (¡Piensa por qué puedes hacer eso!). Este caso ahora se reduce a Caso I (el caso sin hijo) o Caso II, es decir, eliminación de un nodo que solo tiene un hijo (en este caso M, que solo ha dejado hijo). Otra forma de manejar el Caso III es reemplazando N por el nodo que viene inmediatamente después de N en el recorrido en orden del BST. Un caso afín, ¿verdad?

El algoritmo para eliminar un nodo de BST se llama algoritmo de eliminación de Hibbard (llamado así por su fundador Hibbard, quien describió el algoritmo por primera vez en 1962)
El truco para eliminar un nodo de BST proviene del hecho después de la eliminación, el árbol resultante también debería ser un BST.
Hay tres casos:
Caso # 1: El nodo a ser eliminado no tiene hijos.
En este caso, simplemente podemos eliminar el nodo. El nodo principal que vincula este nodo es
solo se establece en nulo.
Caso # 2: El nodo a eliminar tiene un subárbol, es decir, subárbol izquierdo o derecho.
En este caso, hacemos que el nodo padre del nodo eliminado apunte al subárbol del nodo eliminado, ya sea a la izquierda o a la derecha en consecuencia.
Caso n. ° 3: el nodo que se va a eliminar tiene dos hijos, es decir, tiene subárboles izquierdo y derecho
Este es el caso para pensar, ya que después de la eliminación, no podemos simplemente reemplazar el nodo eliminado con uno de sus subárboles porque nos quedaremos con otro subárbol. Esto significa que el nodo eliminado debe ser reemplazado por otro nodo seleccionado de los subárboles y luego eliminar de forma recursiva el nodo que seleccionamos del subárbol en el que está presente.
La pregunta es ¿cuál es el nodo que debemos elegir para reemplazar el nodo eliminado? El nodo elegido debe mantener la propiedad BST. Esto requiere dos posibilidades: (1) elegir el nodo en el subárbol derecho con el valor más pequeño (2) elegir el nodo en el subárbol izquierdo con el subárbol más grande. (En el código de demostración, uso la opción (1))
La complejidad de esta eliminación es claramente proporcional a la altura del árbol.
Las eliminaciones frecuentes harán que el árbol quede sesgado, aumentando así su altura (en el peor de los casos, se vuelve tan grande como n, el número de nodos)
Código Haskell:

  data BinaryTree a = Empty
                     El |  Nodo a (BinaryTree a) (BinaryTree a)
                     derivando (Eq, Ord, Show)
 listToBST :: (Ord a) => [a] -> BinaryTree a
 listToBST [] = Vacío
 listToBST (x: xs) = Nodo x (listToBST (filtro (<= x) xs))
                            (listToBST (filtro (> x) xs))
 deleteBST :: (Ord a) => a -> BinaryTree a -> BinaryTree a
 deleteBST _ Empty = Empty
 deleteBST x t '@ (Nodo a izquierda derecha)
          El |  x  a = Nodo a izquierda (deleteBST x derecha)
          El |  de lo contrario = let
                         minElement :: BinaryTree a -> a
                         minElement (Nodo a Empty _) = a
                         minElement (Node _ l _) = minElement l
                         deleteBST ':: (Ord a) => a -> BinaryTree a -> BinaryTree a
                         deleteBST '_ (Nodo _ l Vacío) = l 
                         deleteBST '_ (Nodo _ Vacío r) = r
                         deleteBST '_ (Nodo _ lr) = let 
                                                         me = minElement r
                                                         r '= deleteBST me r 
                                                     en
                                                          Nodo me l r '
                         en 
                           deleteBST 'x t'