Dato un BST , il compito è eliminare un nodo in this BST , che può essere suddiviso in 3 scenari:
Caso 1. Eliminare un nodo foglia in BST
Cancellazione nella BST
Caso 2. Eliminare un nodo con figlio singolo in BST
Anche eliminare un singolo nodo figlio è semplice in BST. Copia il figlio nel nodo ed elimina il nodo .
Cancellazione nella BST
array.sort in Java
Caso 3. Elimina un nodo con entrambi i figli in BST
Eliminare un nodo con entrambi i figli non è così semplice. Qui dobbiamo farlo eliminare il nodo è tale che l'albero risultante segua le proprietà di un BST.
Il trucco è trovare il successore in ordine del nodo. Copia il contenuto del successore in ordine nel nodo ed elimina il successore in ordine.
Nota: È possibile utilizzare anche il predecessore in ordine.
inferno di richiamata in javascript
Cancellazione nell'albero binario
Nota: Il successore in ordine è necessario solo quando il figlio destro non è vuoto. In questo caso particolare, il successore in ordine può essere ottenuto trovando il valore minimo nel figlio destro del nodo.
Pratica consigliata Elimina un nodo da BST Provalo!Implementazione dell'operazione di cancellazione in un BST:
C++ #include using namespace std; struct Node { int key; struct Node *left, *right; }; // A utility function to create a new BST node Node* newNode(int item) { Node* temp = new Node; temp->chiave = oggetto; temp->sinistra = temp->destra = NULL; temperatura di ritorno; } // Una funzione di utilità per eseguire l'attraversamento inordine del BST void inorder(Node* root) { if (root!= NULL) { inorder(root->left); printf('%d ', root->chiave); ordine(radice->destra); } } /* Una funzione di utilità per inserire un nuovo nodo con la chiave specificata in * BST */ Node* insert(Node* node, int key) { /* Se l'albero è vuoto, restituisce un nuovo nodo */ if (node = = NULL) restituisce nuovoNodo(chiave); /* Altrimenti, ricorre lungo l'albero */ if (key< node->chiave) nodo->sinistra = inserisci(nodo->sinistra, chiave); else nodo->destra = insert(nodo->destra, chiave); /* restituisce il puntatore del nodo (invariato) */ restituisce il nodo; } /* Dato un albero di ricerca binario e una chiave, questa funzione cancella la chiave e restituisce la nuova radice */ Node* deleteNode(Node* root, int k) { // Caso base if (root == NULL) restituisce root; // Se la chiave da eliminare è più piccola della chiave di root, // allora si trova nel sottoalbero di sinistra if (k< root->chiave) { root->sinistra = deleteNode(root->sinistra, k); restituisce radice; } // Se la chiave da eliminare è maggiore della chiave di root, // allora si trova nel sottoalbero destro else if (k> root->key) { root->right = deleteNode(root->right , K); restituisce radice; } // Se la chiave è uguale alla chiave di root, allora questo è il nodo da eliminare // Nodo con un solo figlio o nessun figlio if (root->left == NULL) { Node* temp = root-> Giusto; elimina la radice; temperatura di ritorno; } else if (root->right == NULL) { Node* temp = root->left; elimina la radice; temperatura di ritorno; } // Nodo con due figli: ottieni il successore in ordine (il più piccolo // nel sottoalbero di destra) Node* succParent = root; Nodo* succ = root->destra; while (succ->sinistra!= NULL) { succParent = succ; succ = succ->sinistra; } // Copia il contenuto del successore in ordine su questo nodo root->key = succ->key; // Cancella il successore in ordine if (succParent->left == succ) succParent->left = succ->right; altrimenti succParent->destra = succ->destra; elimina succ; restituisce radice; } // Driver Code int main() { /* Creiamo il seguente BST 50 / 30 70 / / 20 40 60 80 */ Node* root = NULL; radice = inserisci(radice, 50); radice = inserisci(radice, 30); radice = inserisci(radice, 20); radice = inserisci(radice, 40); radice = inserisci(radice, 70); radice = inserisci(radice, 60); radice = inserisci(radice, 80); printf('BST originale: '); ordine(radice); printf('
Elimina un nodo foglia: 20
'); root = deleteNode(root, 20); printf('Albero BST modificato dopo aver eliminato il nodo foglia:
'); ordine(radice); printf('
Elimina nodo con figlio singolo: 70
'); root = deleteNode(root, 70); printf('Albero BST modificato dopo aver eliminato il singolo nodo figlio:
'); ordine(radice); printf('
Elimina nodo con entrambi i figli: 50
'); root = deleteNode(root, 50); printf('Albero BST modificato dopo aver eliminato entrambi i nodi figli:
'); ordine(radice); restituire 0; }> C #include #include struct Node { int key; struct Node *left, *right; }; // A utility function to create a new BST node struct Node* newNode(int item) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->chiave = oggetto; temp->sinistra = temp->destra = NULL; temperatura di ritorno; } // Una funzione di utilità per eseguire l'attraversamento in ordine del BST void inorder(struct Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->chiave); ordine(radice->destra); } } /* Una funzione di utilità per inserire un nuovo nodo con una determinata chiave in BST */ struct Node* insert(struct Node* node, int key) { /* Se l'albero è vuoto, restituisce un nuovo nodo */ if (node == NULL) restituisce nuovoNodo(chiave); /* Altrimenti, ricorre lungo l'albero */ if (key< node->chiave) nodo->sinistra = inserisci(nodo->sinistra, chiave); else nodo->destra = insert(nodo->destra, chiave); /* restituisce il puntatore del nodo (invariato) */ restituisce il nodo; } /* Dato un albero di ricerca binario e una chiave, questa funzione cancella la chiave e restituisce la nuova radice */ struct Node* deleteNode(struct Node* root, int k) { // Caso base if (root == NULL) return radice; // Se la chiave da eliminare è più piccola della chiave di root, allora si trova nel sottoalbero di sinistra if (k< root->chiave) { root->sinistra = deleteNode(root->sinistra, k); restituisce radice; } // Se la chiave da eliminare è maggiore della chiave di root, allora si trova nel sottoalbero destro else if (k> root->key) { root->right = deleteNode(root->right, k ); restituisce radice; } // Se la chiave è uguale alla chiave di root, allora questo è il nodo da eliminare // Nodo con un solo figlio o nessun figlio if (root->left == NULL) { struct Node* temp = root->giusto; libero(radice); temperatura di ritorno; } else if (root->right == NULL) { struct Node* temp = root->left; libero(radice); temperatura di ritorno; } // Nodo con due figli: ottieni il successore in ordine (il più piccolo nel sottoalbero di destra) struct Node* succParent = root; struct Node* succ = root->destra; while (succ->sinistra!= NULL) { succParent = succ; succ = succ->sinistra; } // Copia il contenuto del successore in ordine su questo nodo root->key = succ->key; // Cancella il successore in ordine if (succParent->left == succ) succParent->left = succ->right; altrimenti succParent->destra = succ->destra; libero(successo); restituisce radice; } // Driver Code int main() { /* Creiamo il seguente BST 50 / 30 70 / / 20 40 60 80 */ struct Node* root = NULL; radice = inserisci(radice, 50); inserisci(radice, 30); inserisci(radice, 20); inserisci(radice, 40); inserisci(radice, 70); inserisci(radice, 60); inserisci(radice, 80); printf('BST originale: '); ordine(radice); printf('
Elimina un nodo foglia: 20
'); root = deleteNode(root, 20); printf('Albero BST modificato dopo aver eliminato il nodo foglia:
'); ordine(radice); printf('
Elimina nodo con figlio singolo: 70
'); root = deleteNode(root, 70); printf('Albero BST modificato dopo aver eliminato il singolo nodo figlio:
'); ordine(radice); printf('
Elimina nodo con entrambi i figli: 50
'); root = deleteNode(root, 50); printf('Albero BST modificato dopo aver eliminato entrambi i nodi figli:
'); ordine(radice); restituire 0; }> Giava class Node { int key; Node left, right; Node(int item) { key = item; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } // A utility function to insert a new node with the given key Node insert(Node node, int key) { // If the tree is empty, return a new node if (node == null) { return new Node(key); } // Otherwise, recur down the tree if (key < node.key) { node.left = insert(node.left, key); } else if (key>nodo.chiave) { nodo.destra = insert(nodo.destra, chiave); } // restituisce il puntatore del nodo (invariato) return node; } // Una funzione di utilità per eseguire l'attraversamento inordine del BST void inorder(Node root) { if (root!= null) { inorder(root.left); System.out.print(root.key + ' '); ordine(root.right); } } // Dato un albero di ricerca binario e una chiave, questa funzione cancella la chiave e restituisce la nuova radice Node deleteNode(Node root, int key) { // Caso base if (root == null) { return root; } // Se la chiave da eliminare è più piccola della chiave di root, allora si trova nel sottoalbero di sinistra se (key< root.key) { root.left = deleteNode(root.left, key); } // If the key to be deleted is greater than the root's key, then it lies in the right subtree else if (key>root.key) { root.right = deleteNode(root.right, key); } // Se la chiave è uguale alla chiave di root, allora questo è il nodo da eliminare else { // Nodo con un solo figlio o nessun figlio if (root.left == null) { return root.right; } else if (root.right == null) { return root.left; } // Nodo con due figli: ottieni il successore in ordine (il più piccolo nel sottoalbero di destra) root.key = minValue(root.right); // Elimina il successore in ordine root.right = deleteNode(root.right, root.key); } restituisce root; } int minValue(Nodo root) { int minv = root.key; while (root.left!= null) { minv = root.left.key; radice = radice.sinistra; } restituisce minv; } // Codice driver public static void main(String[] args) { BinaryTree tree = new BinaryTree(); /* Creiamo il seguente BST 50 / 30 70 / / 20 40 60 80 */ tree.root = tree.insert(tree.root, 50); albero.insert(albero.root, 30); albero.insert(albero.root, 20); albero.insert(albero.root, 40); albero.insert(albero.root, 70); albero.insert(albero.root, 60); albero.insert(albero.root, 80); System.out.print('BST originale: '); albero.inordine(albero.root); System.out.println(); System.out.println('
Elimina un nodo foglia: 20'); tree.root = tree.deleteNode(tree.root, 20); System.out.print('Albero BST modificato dopo aver eliminato il nodo foglia:
'); albero.inordine(albero.root); System.out.println(); System.out.println('
Elimina nodo con figlio singolo: 70'); tree.root = tree.deleteNode(tree.root, 70); System.out.print('Albero BST modificato dopo aver eliminato il singolo nodo figlio:
'); albero.inordine(albero.root); System.out.println(); System.out.println('
Elimina nodo con entrambi i figli: 50'); tree.root = tree.deleteNode(tree.root, 50); System.out.print('Albero BST modificato dopo aver eliminato entrambi i nodi figli:
'); albero.inordine(albero.root); } }> Python3 class Node: def __init__(self, key): self.key = key self.left = None self.right = None class BinaryTree: def __init__(self): self.root = None # A utility function to insert a new node with the given key def insert(self, node, key): # If the tree is empty, return a new node if node is None: return Node(key) # Otherwise, recur down the tree if key < node.key: node.left = self.insert(node.left, key) elif key>node.key: node.right = self.insert(node.right, key) # restituisce il puntatore del nodo (invariato) return node # Una funzione di utilità per eseguire l'attraversamento in ordine di BST def inorder(self, root): if root: self .inorder(root.left) print(root.key, end=' ') self.inorder(root.right) # Dato un albero di ricerca binario e una chiave, questa funzione cancella la chiave e restituisce la nuova root def deleteNode (self, root, key): # Caso base se root è None: return root # Se la chiave da eliminare è più piccola della chiave di root, allora si trova nel sottoalbero sinistro if key< root.key: root.left = self.deleteNode(root.left, key) # If the key to be deleted is greater than the root's key, then it lies in the right subtree elif key>root.key: root.right = self.deleteNode(root.right, key) # Se la chiave è uguale alla chiave di root, allora questo è il nodo da eliminare altrimenti: # Nodo con un solo figlio o nessun figlio se root.left is None: return root.right elif root.right is None: return root.left # Nodo con due figli: ottieni il successore in ordine (il più piccolo nel sottoalbero di destra) root.key = self.minValue(root.right) # Elimina il successore in ordine root.right = self.deleteNode(root.right, root.key) return root def minValue(self, root): minv = root.key while root.left: minv = root.left.key root = root.left return minv # Codice driver if __name__ == '__main__': tree = BinaryTree() # Creiamo il seguente BST # 50 # / # 30 70 # / / # 20 40 60 80 tree.root = tree.insert(tree.root, 50) tree.insert(tree.root, 30) tree.insert(tree.root, 20) tree.insert(tree.root, 40) tree.insert(tree.root, 70 ) tree.insert(tree.root, 60) tree.insert(tree.root, 80) print('BST originale:', end=' ') tree.inorder(tree.root) print() print ('
Elimina un nodo foglia: 20') tree.root = tree.deleteNode(tree.root, 20) print('Albero BST modificato dopo aver eliminato il nodo foglia:') tree.inorder(tree.root) print() print('
Elimina nodo con singolo figlio: 70') tree.root = tree.deleteNode(tree.root, 70) print('Albero BST modificato dopo aver eliminato un singolo nodo figlio:') tree. inorder(tree.root) print() print('
Elimina nodo con entrambi i figli: 50') tree.root = tree.deleteNode(tree.root, 50) print('Albero BST modificato dopo aver eliminato entrambi i nodi figli :') albero.inorder(albero.root)> C# using System; public class Node { public int key; public Node left, right; public Node(int item) { key = item; left = right = null; } } public class BinaryTree { public Node root; // A utility function to insert a new node with the given key public Node Insert(Node node, int key) { // If the tree is empty, return a new node if (node == null) return new Node(key); // Otherwise, recur down the tree if (key < node.key) node.left = Insert(node.left, key); else if (key>nodo.chiave) nodo.destra = Inserisci(nodo.destra, chiave); // restituisce il puntatore del nodo (invariato) return node; } // Una funzione di utilità per eseguire l'attraversamento in ordine del BST public void Inorder(Node root) { if (root!= null) { Inorder(root.left); Console.Write(root.key + ' '); Inordine(root.right); } } // Dato un albero di ricerca binario e una chiave, questa funzione cancella la chiave e restituisce la nuova root public Node DeleteNode(Node root, int key) { // Caso base if (root == null) return root; // Se la chiave da eliminare è più piccola della chiave di root, allora si trova nel sottoalbero di sinistra if (key< root.key) root.left = DeleteNode(root.left, key); // If the key to be deleted is greater than the root's key, then it lies in the right subtree else if (key>root.key) root.right = EliminaNode(root.right, chiave); // Se la chiave è uguale alla chiave di root, allora questo è il nodo da eliminare else { // Nodo con un solo figlio o nessun figlio if (root.left == null) return root.right; altrimenti se (root.right == null) restituisce root.left; // Nodo con due figli: ottieni il successore in ordine (il più piccolo nel sottoalbero di destra) root.key = MinValue(root.right); // Elimina il successore in ordine root.right = DeleteNode(root.right, root.key); } restituisce root; } public int MinValue(Nodo root) { int minv = root.key; while (root.left!= null) { minv = root.left.key; radice = radice.sinistra; } restituisce minv; } // Codice driver public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); /* Creiamo il seguente BST 50 / 30 70 / / 20 40 60 80 */ tree.root = tree.Insert(tree.root, 50); albero.Inserisci(albero.root, 30); albero.Inserisci(albero.root, 20); albero.Inserisci(albero.root, 40); albero.Inserisci(albero.root, 70); albero.Inserisci(albero.root, 60); albero.Inserisci(albero.root, 80); Console.Write('BST originale: '); albero.Inordine(albero.root); Console.WriteLine(); Console.WriteLine('
Elimina un nodo foglia: 20'); albero.root = albero.DeleteNode(albero.root, 20); Console.Write('Albero BST modificato dopo aver eliminato il nodo foglia:
'); albero.Inordine(albero.root); Console.WriteLine(); Console.WriteLine('
Elimina nodo con figlio singolo: 70'); albero.root = albero.DeleteNode(albero.root, 70); Console.Write('Albero BST modificato dopo aver eliminato il singolo nodo figlio:
'); albero.Inordine(albero.root); Console.WriteLine(); Console.WriteLine('
Elimina nodo con entrambi i figli: 50'); albero.root = albero.DeleteNode(albero.root, 50); Console.Write('Albero BST modificato dopo aver eliminato entrambi i nodi figli:
'); albero.Inordine(albero.root); }> Javascript class Node { constructor(key) { this.key = key; this.left = null; this.right = null; } } class BinaryTree { constructor() { this.root = null; } // A utility function to insert a new node with the given key insert(node, key) { // If the tree is empty, return a new node if (node === null) return new Node(key); // Otherwise, recur down the tree if (key < node.key) node.left = this.insert(node.left, key); else if (key>nodo.chiave) nodo.destra = this.insert(nodo.destra, chiave); // restituisce il puntatore del nodo (invariato) return node; } // Una funzione di utilità per eseguire l'attraversamento in ordine del BST inorder(node) { if (node !== null) { this.inorder(node.left); console.log(nodo.chiave + ' '); this.inorder(nodo.destra); } } // Dato un albero di ricerca binario e una chiave, questa funzione cancella la chiave e restituisce la nuova radice deleteNode(root, key) { // Caso base if (root === null) return root; // Se la chiave da eliminare è più piccola della chiave di root, allora si trova nel sottoalbero di sinistra if (key< root.key) root.left = this.deleteNode(root.left, key); // If the key to be deleted is greater than the root's key, then it lies in the right subtree else if (key>root.key) root.right = this.deleteNode(root.right, chiave); // Se la chiave è uguale alla chiave di root, allora questo è il nodo da eliminare else { // Nodo con un solo figlio o nessun figlio if (root.left === null) return root.right; else if (root.right === null) restituisce root.left; // Nodo con due figli: ottieni il successore in ordine (il più piccolo nel sottoalbero di destra) root.key = this.minValue(root.right); // Elimina il successore in ordine root.right = this.deleteNode(root.right, root.key); } restituisce root; } minValue(nodo) { let minv = nodo.chiave; while (nodo.sinistra!== null) { minv = nodo.sinistra.chiave; nodo = nodo.sinistra; } restituisce minv; } } // Codice driver let tree = new BinaryTree(); /* Creiamo il seguente BST 50 / 30 70 / / 20 40 60 80 */ tree.root = tree.insert(tree.root, 50); albero.insert(albero.root, 30); albero.insert(albero.root, 20); albero.insert(albero.root, 40); albero.insert(albero.root, 70); albero.insert(albero.root, 60); albero.insert(albero.root, 80); console.log('BST originale:'); albero.inordine(albero.root); console.log('
Elimina un nodo foglia: 20'); tree.root = tree.deleteNode(tree.root, 20); console.log('Albero BST modificato dopo aver eliminato il nodo foglia:'); albero.inordine(albero.root); console.log('
Elimina nodo con figlio singolo: 70'); tree.root = tree.deleteNode(tree.root, 70); console.log('Albero BST modificato dopo aver eliminato un singolo nodo figlio:'); albero.inordine(albero.root); console.log('
Elimina nodo con entrambi i figli: 50'); tree.root = tree.deleteNode(tree.root, 50); console.log('Albero BST modificato dopo aver eliminato entrambi i nodi figli:'); albero.inordine(albero.root);> Produzione
Original BST: 20 30 40 50 60 70 Delete a Leaf Node: 20 Modified BST tree after deleting Leaf Node: 30 40 50 60 70 Delete Node with single child: 70 Modified BST tree after deleting single child No...>
Complessità temporale: O(h), dove h è l'altezza della BST.
Spazio ausiliario: SU).
Link correlati:
- Operazione di ricerca nell'albero di ricerca binaria
- Operazione di inserimento dell'albero di ricerca binario