Sí, esa es una forma correcta. Al eliminar un nodo con dos hijos, tiene dos opciones igualmente buenas.
Opción 1: intercambie los datos en el nodo con su nodo sucesor de orden, y luego elimine el nodo que contiene el valor a eliminar, es decir, el sucesor de orden.
Opción 2: intercambie los datos en el nodo con su nodo predecesor en orden y luego elimine el nodo predecesor en orden.
- ¿Qué algoritmos usa Dropbox para la compresión de datos?
- ¿Qué tan útil es el conocimiento de los algoritmos informáticos tradicionales para escribir códigos CFD?
- ¿Las siguientes declaraciones de bucle en C / C ++ tienen el mismo tiempo de ejecución?
- ¿Cuál es la intuición detrás del algoritmo de clasificación rápida de múltiples claves?
- Crear un algoritmo simple me lleva horas, ¿cómo puedo ser más rápido?
Puede encontrar el sucesor del pedido dando un paso a la derecha y luego yendo lo más a la izquierda posible (es decir, hasta llegar a un nodo sin hijo izquierdo). Del mismo modo, puede encontrar el predecesor en orden dando un paso a la izquierda y luego yendo lo más a la derecha posible. Tanto el sucesor como el predecesor no pueden tener dos hijos. Por lo tanto, eliminar este nodo es eliminar la hoja o eliminar un caso secundario, los cuales son fáciles.
La elección realizada en su ejemplo fue la opción 1. Para encontrar el sucesor de orden de 30, avance una vez a la derecha, a 45, y luego vaya lo más a la izquierda posible, que permanece en 45. Ahora intercambie los elementos de datos en estos dos nodos para que el nodo que antes contenía 30 ahora contenga 45. El nodo que ahora contiene 30 tiene un hijo, por lo que puede eliminarlo “empalmándolo” del árbol.
Otro ejemplo sería eliminar 20 que está en el nodo raíz. Para obtener el sucesor de orden, debe avanzar hacia la derecha (a 30 en el árbol original) y luego ir lo más a la izquierda posible: a 25, luego a 22. Intercambia los elementos de datos y luego elimina el nodo sucesor.
Ambas opciones mantienen la relación de orden para que el árbol siga siendo un árbol de búsqueda, además de que no hay ningún nodo para el que la ruta de búsqueda aumente de longitud, por lo tanto, el tiempo de búsqueda no aumenta para ningún nodo. Todos los nodos en el subárbol enraizados en el sucesor / predecesor tienen su longitud de ruta de búsqueda reducida en 1 (la longitud de la ruta de búsqueda al nodo sucesor / predecesor puede reducirse en más de uno).
