logo

Eliminació

La funció Suprimeix s'utilitza per eliminar el node especificat d'un arbre de cerca binari. Tanmateix, hem d'eliminar un node d'un arbre de cerca binari de tal manera que la propietat de l'arbre de cerca binari no infringeixi. Hi ha tres situacions d'eliminació d'un node de l'arbre de cerca binari.

El node que s'ha de suprimir és un node fulla

És el cas més senzill, en aquest cas, substituir el node fulla pel NULL i alliberar senzillament l'espai assignat.

A la imatge següent, estem suprimint el node 85, ja que el node és un node fulla, per tant, el node se substituirà per NULL i s'alliberarà l'espai assignat.

convertir una cadena a data

Supressió a l'arbre de cerca binari

El node que s'ha de suprimir només té un fill.

En aquest cas, substituïu el node pel seu fill i suprimiu el node fill, que ara conté el valor que s'ha de suprimir. Simplement substituïu-lo amb NULL i allibereu l'espai assignat.

convertir char en cadena

A la imatge següent, el node 12 s'ha de suprimir. Només té un fill. El node se substituirà pel seu node fill i el node substituït 12 (que ara és el node fulla) simplement s'eliminarà.


Supressió a l'arbre de cerca binari

El node que s'ha de suprimir té dos fills.

És un cas una mica complex en comparació amb altres dos casos. Tanmateix, el node que s'ha d'esborrar es substitueix pel seu successor o predecessor en ordre recursivament fins que el valor del node (que s'ha d'eliminar) es col·loca a la fulla de l'arbre. Després del procediment, substituïu el node per NULL i allibereu l'espai assignat.

A la imatge següent, s'ha de suprimir el node 50 que és el node arrel de l'arbre. El recorregut en ordre de l'arbre que es mostra a continuació.

int a cadena en java

6, 25, 30, 50, 52, 60, 70, 75.

substituïu 50 pel seu successor en ordre 52. Ara, 50 es mourà a la fulla de l'arbre, que simplement s'eliminarà.


Supressió a l'arbre de cerca binari

Algorisme

Suprimeix (ARBRE, ARTICLE)

    Pas 1:SI ARBRE = NULL
    Escriu 'element no trobat a l'arbre' ELSE IF DADES DE L'íTEM
    Suprimeix(ARBRE->ESQUERRA, ELEMENT)
    ELSE SI ARTICLE > ARBRE -> DADES
    Suprimeix(ARBRE -> DRET, ELEMENT)
    ALTRES SI ARBRE -> ESQUERRA I ARBRE -> DRET
    SET TEMP = findLargestNode (ARBRE -> ESQUERRA)
    SET ARBRE -> DADES = TEMP -> DADES
    Suprimeix (ARBRE -> ESQUERRA, TEMP -> DADES)
    ALTRES
    SET TEMP = ARBRE
    SI ARBRE -> ESQUERRA = NULL I ARBRE -> DRET = NULL
    SET TREE = NULL
    ELSE IF ARBRE -> ESQUERRA != NULL
    SET ARBRE = ARBRE -> ESQUERRA
    ALTRES
    SET ARBRE = ARBRE -> DRET
    [FI DE SI]
    LLIURE TEMP
    [FI DE SI]Pas 2:FINAL

Funció:

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