La función de eliminación se utiliza para eliminar el nodo especificado de un árbol de búsqueda binario. Sin embargo, debemos eliminar un nodo de un árbol de búsqueda binario de tal manera que la propiedad del árbol de búsqueda binario no viole. Hay tres situaciones para eliminar un nodo del árbol de búsqueda binario.
El nodo que se va a eliminar es un nodo hoja.
Es el caso más simple, en este caso, reemplace el nodo hoja con NULL y simplemente libere el espacio asignado.
al hacer clic en javascript
En la siguiente imagen, estamos eliminando el nodo 85, ya que el nodo es un nodo hoja, por lo tanto, el nodo será reemplazado por NULL y se liberará el espacio asignado.
El nodo que se va a eliminar tiene un solo hijo.
En este caso, reemplace el nodo con su hijo y elimine el nodo hijo, que ahora contiene el valor que se va a eliminar. Simplemente reemplácelo con NULL y libere el espacio asignado.
cadena de longitud
En la siguiente imagen, se debe eliminar el nodo 12. Tiene un solo hijo. El nodo será reemplazado por su nodo hijo y el nodo 12 reemplazado (que ahora es el nodo hoja) simplemente se eliminará.
El nodo que se va a eliminar tiene dos hijos.
Es un caso un poco complejo en comparación con otros dos casos. Sin embargo, el nodo que se va a eliminar se reemplaza con su sucesor o predecesor en orden de forma recursiva hasta que el valor del nodo (que se va a eliminar) se coloca en la hoja del árbol. Después del procedimiento, reemplace el nodo con NULL y libere el espacio asignado.
En la siguiente imagen, se va a eliminar el nodo 50, que es el nodo raíz del árbol. El recorrido en orden del árbol que se muestra a continuación.
cadena.valor de java
6, 25, 30, 50, 52, 60, 70, 75.
reemplace 50 con su sucesor en orden 52. Ahora, 50 se moverá a la hoja del árbol, que simplemente se eliminará.
Algoritmo
Eliminar (ÁRBOL, ARTÍCULO)
Escriba 'artículo no encontrado en el árbol' ELSE IF ITEM DATA
Eliminar(ÁRBOL->IZQUIERDA, ARTÍCULO)
ELSE IF ARTÍCULO > ÁRBOL -> DATOS
Eliminar (ÁRBOL -> DERECHA, ARTÍCULO)
ELSE IF ÁRBOL -> IZQUIERDA Y ÁRBOL -> DERECHA
SET TEMP = buscarNodoMásGrande(ÁRBOL -> IZQUIERDA)
ESTABLECER ÁRBOL -> DATOS = TEMP -> DATOS
Eliminar (ÁRBOL -> IZQUIERDA, TEMP -> DATOS)
DEMÁS
TEMPERATURA AJUSTADA = ÁRBOL
SI ÁRBOL -> IZQUIERDA = NULO Y ÁRBOL -> DERECHA = NULO
ESTABLECER ÁRBOL = NULO
ELSE SI ÁRBOL -> IZQUIERDA! = NULO
ESTABLECER ÁRBOL = ÁRBOL -> IZQUIERDA
DEMÁS
ESTABLECER ÁRBOL = ÁRBOL -> DERECHA
[FIN DE SI]
TEMPERATURA LIBRE
[FIN DE SI]
Función:
void deletion(Node*& root, int item) { Node* parent = NULL; Node* cur = root; search(cur, item, parent); if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur- >right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? Cur- >left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } Node* findMinimum(Node* cur) { while(cur->left != NULL) { cur = cur->left; } return cur; }