Hay 3 casos que deben considerarse al eliminar un nodo del Árbol de búsqueda binaria.
1. El nodo a eliminar no tiene elementos secundarios que no sean elementos secundarios izquierdos ni elementos secundarios derechos presentes.
Caso 1 en la imagen de abajo.
2. El nodo a eliminar solo tiene un hijo, ya sea izquierdo o derecho. Caso 2 en la imagen de abajo.
3. El nodo a eliminar tiene ambos elementos secundarios, izquierdo y derecho. Caso 3 en la imagen de abajo.
- ¿Qué tipo de algoritmos de visión por computadora se utilizan en los robots industriales?
- ¿Cuáles son las aplicaciones de las búsquedas lineales y binarias?
- Cómo encontrar todos los palíndromos posibles que se pueden generar usando las letras de una cadena dada
- ¿Cuál es la complejidad Big-O de una búsqueda lineal?
- ¿Qué son los patrones de búsqueda?
Caso 1:
Para el caso 1, es muy sencillo,
1. Busque el nodo que debe eliminarse.
2. El nodo a eliminar está en el lado izquierdo o en el lado derecho de su nodo padre.
3. Si el nodo que se va a eliminar está en el lado izquierdo de su nodo padre, marque el lado izquierdo del nodo padre como nulo.
Por ejemplo: parent.setLeft (nulo);
4. Si el nodo que se va a eliminar está en el lado derecho de su nodo padre, marque el lado derecho del nodo padre
a nulo. Por ejemplo: parent.setRight (nulo);
Caso 2:
Para el caso 2, es muy sencillo,
1. Busque el nodo que debe eliminarse.
2. El nodo a eliminar está en el lado izquierdo o en el lado derecho de su nodo padre.
3. El nodo a eliminar solo tiene un elemento secundario presente que puede estar en el lado izquierdo o derecho.
4. Si el nodo a eliminar ha dejado un niño presente,
luego conecte directamente su nodo primario al nodo secundario izquierdo del nodo que se va a eliminar.
Por ejemplo: parent.setLeft (child.getLeft ());
5. Si el nodo que se va a eliminar tiene un hijo secundario presente,
luego conecte directamente su nodo primario al nodo secundario derecho del nodo que se va a eliminar.
Por ejemplo: parent.setRight (child.getRight ());
6. De esta forma, el nodo que se eliminará se eliminará del árbol y el nodo principal
se conectará directamente al nodo secundario del nodo que se eliminará.
Caso 3:
Para el caso 3, es un poco complicado
1. Busque el nodo que debe eliminarse.
2. Ahora, en lugar de eliminar el nodo, reemplazaremos los datos del nodo que se eliminará
con los datos que mejor se ajusten a ese lugar.
3. ¿Qué datos se ajustarán mejor? Busque los datos del subárbol del nodo que se va a eliminar y
encontrar el nodo cuyos datos cuando se colocan en el lugar del nodo que se eliminará
mantener la propiedad del árbol de búsqueda binaria (la clave en cada nodo debe ser mayor
que todas las claves almacenadas en el subárbol izquierdo, y más pequeñas que todas las claves en el subárbol derecho) intactas.
4. Encuentre el elemento mínimo del subárbol derecho del nodo que se va a eliminar o
encuentre el elemento máximo del subárbol izquierdo del nodo que se va a eliminar y
copie los datos de ese nodo a los datos del nodo que se va a eliminar.
5. Elimine el nodo que encontramos el mejor ajuste en el paso 5.
Nodo privado deleteNode (Node rootNode, int data) {
if (rootNode == null) {
volver nulo;
}
if (data == rootNode.getData ()) {
if (rootNode.getLeft ()! = null && rootNode.getRight ()! = null) {
// Encuentra el mínimo del árbol derecho O encuentra el máximo del árbol izquierdo.
Nodo minNode = getHighestNodeFromRight (rootNode.getRight ());
rootNode.setData (minNode.getData ());
rootNode.setRight (deleteNode (rootNode.getRight (), minNode.getData ()));
System.out.println (minNode);
} else if (rootNode.getLeft () == null) {
return rootNode.getRight ();
}más{
return rootNode.getLeft ();
}
} else if (data> rootNode.getData ()) {
rootNode.setRight (deleteNode (rootNode.getRight (), data));
}más{
rootNode.setLeft (deleteNode (rootNode.getLeft (), data));
}
return rootNode;
}
Nodo público getHighestNodeFromRight (nodo Nodo) {
if (node.getLeft () == null) {
nodo de retorno;
}más{
Nodo n = getHighestNodeFromRight (node.getLeft ());
volver n;
}
}
Explicación detallada con el programa completo: eliminar un nodo en el árbol de búsqueda binaria.
