logo

Supresión

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.


Eliminación en el árbol de búsqueda binaria

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á.


Eliminación en el árbol de búsqueda binaria

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á.


Eliminación en el árbol de búsqueda binaria

Algoritmo

Eliminar (ÁRBOL, ARTÍCULO)

    Paso 1:SI ÁRBOL = NULO
    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]Paso 2:FIN

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; }