Eliminación de nodos en un árbol binario ordenado.

[NextByte]

Ya he dado con la solución de las operaciones básicas del árbol sin embargo me queda la duda dentro de la operación de eliminación. Durante la operación de eliminación tenemos primeramente dos casos.
1. El nodo ha eliminar es la raíz del árbol.
2. El nodo ha eliminar no es la raíz del árbol.

Independientemente cual sea el caso de los anteriores tenemos las siguientes posibilidades:
1. El nodo ha eliminar no tiene hijos. La eliminación implica simplemente eliminar la referencia de su padre que apuntaba hacia el y liberar memoria.
2. El nodo tiene un único hijo o rama. La eliminación implica que la referencia que tenia el padre hacia el nodo que se va eliminar sea reasignada ahora hacia la rama del nodo que se va eliminar.
3. El nodo tiene las dos ramas. Es aquí donde me surge la duda!!... En mi implementación lo que hice fue buscar el nodo mayor de los menores de las rama que tiene el nodo que se va eliminar, una vez localizado ese era mi candidato que ocuparía el lugar del nodo eliminado por lo tanto para este punto lo que hacia era:
   1. Remplazar el nodo a eliminar por aquel nodo que era el mayor de los menores haciendo ajustes como que el padre de este nodo ahora apunte a todo el subárbol que puede que existiría del lado izquierdo del nodo que vamos a usar como remplazo al eliminado.

Hasta este paso creo que estar bien... Mi incógnita queda en que he visto que algunos dan mas seguimiento al caso de que el nodo a eliminar tenga las dos ramas , es decir, primero hacen lo que yo hago... que es buscar la hoja o nodo que es el mayor de los menores del nodo a eliminar,posterior a eso veo que si ese nodo auxiliar o de remplazo tiene su rama izquierda hacen otra comprobación pero ahora por parte del nodo menor de los mayores del nodo a eliminar, es decir, vuelven a hacer lo mismo que yo hice pero ahora con el nodo menor de los mayores. Una vez comprobado esto pueden tener que:
   1.El nodo menor de los mayores resulta no tener la rama de la derecha por lo cual es un mejor candidato a ser el remplazo del nodo a eliminar.
   2.El nodo menor de los mayores tiene la rama derecha por lo cual hasta este punto tiene el mismo beneficio que el nodo mayor de los menores sin embargo aquí es cuando veo que hacen una segundo cuestionamiento y es ¿ Qué rama tiene menos niveles ?, hacen un conteo de los niveles en caso de que no hayan recorrido antes y finalmente determinan cual es el mejor candidato.

Mi duda es ¿ Realmente vale la pena realizar todo este proceso?, es decir, a mi forma de verlo yo solo modificaría a mi implementación el hecho de que si el candidato del lado izquierdo que es el mayor de los menores del nodo a eliminar tiene alguna rama solo verificaría si el candidato 2 o el candidato menor de los mayores no tiene la rama derecha , en ese caso eligiria el candidato de la derecha( el menor de los mayores ) pero en el caso de que este también tuviera su rama.. directamente pondría a hacer el proceso de poner como remplazo al nodo candidato de la izquierda(mayor de los menores) sin importarme cual es que menor nivel tiene por que yo solo estaría viendo si sus ramas son distintas de null para comprobar si tienen ramas  y en caso de que quisiera hacer toda la comparación con los niveles debería recorrer ambas ramas y creo que los beneficios que me podría traer esa segunda verificación podrían ser equivalente a su desventaja.

Me gustaría saber como han hecho las implementaciones en esta parte y si consideran que valga la pena llegar hasta ese detalle de comparar los niveles de las ramas.