Donat a BST , la tasca és eliminar un node d'aquest BST , que es pot dividir en 3 escenaris:
Cas 1. Eliminar un node de fulla a BST
Eliminació en BST
Cas 2. Suprimeix un node amb un sol fill a BST
Suprimir un sol node fill també és senzill a BST. Copieu el fill al node i suprimiu el node .
Eliminació en BST
Cas 3. Suprimeix un node amb els dos fills a BST
Suprimir un node amb els dos fills no és tan senzill. Aquí ho hem de fer eliminar el node és de tal manera que l'arbre resultant segueix les propietats d'un BST.
El truc és trobar el successor en ordre del node. Copieu el contingut del successor de l'ordre al node i suprimiu el successor de l'ordre.
Nota: També es pot utilitzar el predecessor Inorder.
ctc forma completa
Eliminació a l'arbre binari
Nota: El successor en ordre només es necessita quan el fill adequat no està buit. En aquest cas particular, el successor de l'ordre es pot obtenir trobant el valor mínim al fill dret del node.
Pràctica recomanada Eliminar un node de BST Prova-ho!Implementació de l'operació de supressió en 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->clau = element; temp->esquerra = temp->dreta = NULL; temperatura de retorn; } // Una funció d'utilitat per fer un recorregut en ordre de BST void inorder(Node* arrel) { if (arrel != NULL) { inorder (arrel->esquerra); printf('%d', arrel->clau); inordre(arrel->dreta); } } /* Una funció d'utilitat per inserir un nou node amb una clau donada a * BST */ Node* insert(Node* node, int key) { /* Si l'arbre està buit, retorna un nou node */ if (node = = NULL) retorn nouNode(clau); /* En cas contrari, torna a baixar per l'arbre */ if (clau< node->clau) node->esquerra = inserir (node->esquerra, clau); else node->right = inserir (node->right, clau); /* retorna el punter del node (sense modificar) */ retorna el node; } /* Donat un arbre de cerca binari i una clau, aquesta funció elimina la clau i retorna la nova arrel */ Node* deleteNode(Node* arrel, int k) { // Cas base si (arrel == NULL) retorna arrel; // Si la clau que s'ha d'esborrar és més petita que la clau de l'arrel, // llavors es troba al subarbre esquerre si (k< root->clau) { arrel->esquerra = deleteNode (arrel->esquerra, k); retornar l'arrel; } // Si la clau que s'ha d'esborrar és més gran que la clau de l'arrel, // llavors es troba al subarbre dret, sinó si (k> arrel->clau) { arrel->right = deleteNode (arrel->dreta) , k); retornar l'arrel; } // Si la clau és la mateixa que la clau de l'arrel, aquest és el node que s'ha d'eliminar // Node amb només un fill o cap fill si (arrel->esquerra == NULL) { Node* temp = arrel-> dret; esborra l'arrel; temperatura de retorn; } else if (arrel->dreta == NULL) { Node* temp = arrel->esquerra; esborra l'arrel; temperatura de retorn; } // Node amb dos fills: Obteniu el successor de l'ordre (més petit // al subarbre dret) Node* succParent = arrel; Node* succ = arrel->dreta; mentre que (succ->esquerra != NULL) { succParent = succ; succ = succ->esquerra; } // Copia el contingut del successor de l'ordre a aquest node arrel->clau = succ->clau; // Esborra el successor de l'ordre si (succParent->esquerra == succ) succParent->esquerra = succ->dreta; else succParent->right = succ->right; esborra succ; retornar l'arrel; } // Codi del controlador int main() { /* Creem el següent BST 50 / 30 70 / / 20 40 60 80 */ Node* root = NULL; arrel = inserir (arrel, 50); arrel = inserir (arrel, 30); arrel = inserir (arrel, 20); arrel = inserir (arrel, 40); arrel = inserir (arrel, 70); arrel = inserir (arrel, 60); arrel = inserir (arrel, 80); printf('BST original: '); inorde (arrel); printf('
Suprimeix un node de fulla: 20
'); arrel = deleteNode (arrel, 20); printf('Arbre BST modificat després d'eliminar el Node Full:
'); inorde (arrel); printf('
Suprimeix el node amb un sol fill: 70
'); arrel = deleteNode (arrel, 70); printf('Arbre BST modificat després d'eliminar un sol node fill:
'); inorde (arrel); printf('
Suprimeix el node amb els dos fills: 50
'); arrel = deleteNode (arrel, 50); printf('Arbre BST modificat després d'eliminar els dos nodes secundaris:
'); inorde (arrel); retorn 0; }>>>Cesquerra); printf('%d', arrel->clau); inordre(arrel->dreta); } } /* Una funció d'utilitat per inserir un nou node amb una clau donada a BST */ struct Node* insert(struct Node* node, int key) { /* Si l'arbre està buit, retorna un nou node */ if (node == NULL) retorn nouNode(clau); /* En cas contrari, torna a baixar per l'arbre */ if (clau< node->clau) node->esquerra = inserir (node->esquerra, clau); else node->right = inserir (node->right, clau); /* retorna el punter del node (sense modificar) */ retorna el node; } /* Donat un arbre de cerca binari i una clau, aquesta funció elimina la clau i retorna la nova arrel */ struct Node* deleteNode(struct Node* arrel, int k) { // Cas base si (arrel == NULL) retorn arrel; // Si la clau que s'ha d'esborrar és més petita que la clau de l'arrel, llavors es troba al subarbre esquerre si (k< root->clau) { arrel->esquerra = deleteNode (arrel->esquerra, k); retornar l'arrel; } // Si la clau que s'ha d'esborrar és més gran que la clau de l'arrel, aleshores es troba al subarbre dret, sinó si (k> arrel->clau) { arrel->right = deleteNode (arrel->dreta, k ); retornar l'arrel; } // Si la clau és la mateixa que la clau de l'arrel, aquest és el node que s'ha d'eliminar // Node amb només un fill o cap fill si (arrel->esquerra == NULL) { struct Node* temp = arrel-> dret; lliure (arrel); temperatura de retorn; } else if (arrel->dreta == NULL) { struct Node* temp = arrel->esquerra; lliure (arrel); temperatura de retorn; } // Node amb dos fills: obteniu el successor de l'ordre (el més petit del subarbre dret) struct Node* succParent = root; struct Node* succ = arrel->dreta; while (succ->esquerra != NULL) { succParent = succ; succ = succ->esquerra; } // Copieu el contingut del successor de l'ordre en aquest node arrel->clau = succ->clau; // Esborra el successor de l'ordre si (succParent->esquerra == succ) succParent->esquerra = succ->dreta; else succParent->right = succ->right; lliure (succ); retornar l'arrel; } // Codi del controlador int main() { /* Creem el següent BST 50 / 30 70 / / 20 40 60 80 */ struct Node* root = NULL; arrel = inserir (arrel, 50); inserir (arrel, 30); inserir (arrel, 20); inserir (arrel, 40); inserir (arrel, 70); inserir (arrel, 60); inserir (arrel, 80); printf('BST original: '); inorde (arrel); printf('
Suprimeix un node de fulla: 20
'); arrel = deleteNode (arrel, 20); printf('Arbre BST modificat després d'eliminar el Node Full:
'); inorde (arrel); printf('
Suprimeix el node amb un sol fill: 70
'); arrel = deleteNode (arrel, 70); printf('Arbre BST modificat després d'eliminar un sol node fill:
'); inorde (arrel); printf('
Suprimeix el node amb els dos fills: 50
'); arrel = deleteNode (arrel, 50); printf('Arbre BST modificat després d'eliminar els dos nodes secundaris:
'); inorde (arrel); retorn 0; }>>> Javaroot.key) { root.right = deleteNode (root.right, clau); } // Si la clau és la mateixa que la clau de root, aquest és el node que s'ha d'eliminar else { // Node amb només un fill o cap fill if (root.left == null) { return root.right; } else if (arrel.dreta == nul) { retornar arrel.esquerra; } // Node amb dos fills: obteniu el successor de l'ordre (el més petit del subarbre dret) root.key = minValue(root.right); // Esborra el successor de l'ordre root.right = deleteNode(root.right, root.key); } retornar l'arrel; } int minValue (arrel del node) { int minv = root.key; mentre que (arrel.esquerra != nul) { minv = arrel.esquerra.clau; arrel = arrel.esquerra; } retorn minv; } // Codi del controlador public static void main(String[] args) { BinaryTree tree = new BinaryTree (); /* Creem el següent 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); System.out.print('BST original: '); tree.inorder(tree.root); System.out.println(); System.out.println('
Suprimeix un node de fulla: 20'); tree.root = tree.deleteNode (tree.root, 20); System.out.print('Arbre BST modificat després d'eliminar el node de fulla:
'); tree.inorder(tree.root); System.out.println(); System.out.println('
Suprimeix el node amb un sol fill: 70'); tree.root = tree.deleteNode (tree.root, 70); System.out.print('Arbre BST modificat després de suprimir un sol node fill:
'); tree.inorder(tree.root); System.out.println(); System.out.println('
Suprimeix el node amb els dos fills: 50'); tree.root = tree.deleteNode (tree.root, 50); System.out.print('Arbre BST modificat després d'eliminar els dos nodes secundaris:
'); tree.inorder(tree.root); } }>>> Python 3root.key: root.right = self.deleteNode(root.right, key) # Si la clau és la mateixa que la de root, aquest és el node que s'ha d'esborrar sinó: # Node amb només un fill o cap fill si root.left és Cap: retornar root.right elif root.right és Cap: retornar root.left # Node amb dos fills: obtenir el successor de l'ordre (el més petit del subarbre dret) root.key = self.minValue(root.right) # Suprimeix el successor de l'ordre root.right = self.deleteNode(root.right, root.key) return root def minValue(self, root): minv = root.key mentre root.left: minv = root.left.key root = root.left return minv # Codi del controlador if __name__ == '__main__': tree = BinaryTree() # Creem el següent 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 original:', final=' ') tree.inorder(tree.root) print() print ('
Suprimeix un node de fulla: 20') tree.root = tree.deleteNode(tree.root, 20) print('Arbre BST modificat després d'haver suprimit el node de fulla:') tree.inorder(tree.root) print() print('
Suprimeix el node amb un sol fill: 70') tree.root = tree.deleteNode(tree.root, 70) print('Arbre BST modificat després de suprimir un sol node fill:'). inorder(tree.root) print() print('
Suprimeix el node amb els dos fills: 50') tree.root = tree.deleteNode(tree.root, 50) print('Arbre BST modificat després d'eliminar els dos nodes secundaris :') tree.inorder(tree.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>node.key) node.right = Insereix (node.right, clau); // retorna el node de retorn del punter del node (no canviat); } // Una funció d'utilitat per fer un recorregut en ordre de BST public void Inorder (arrel del node) { if (arrel != nul) { Inorder (arrel.esquerra); Console.Write(root.key + ' '); Inorder(arrel.dreta); } } // Donat un arbre de cerca binari i una clau, aquesta funció elimina la clau i retorna la nova arrel pública Node DeleteNode(Arrel del node, clau int) { // Cas base si (arrel == null) retorna arrel; // Si la clau que s'ha d'esborrar és més petita que la clau de l'arrel, llavors es troba al subarbre esquerre si (clau< 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, clau); // Si la clau és la mateixa que la clau d'arrel, aquest és el node que s'ha d'eliminar else { // Node amb només un fill o cap fill si (root.left == null) retorna root.right; else if (root.right == null) retorna root.left; // Node amb dos fills: obteniu el successor de l'ordre (el més petit del subarbre dret) root.key = MinValue(root.right); // Esborra el successor de l'ordre root.right = DeleteNode(root.right, root.key); } retornar l'arrel; } public int MinValue (arrel del node) { int minv = root.key; mentre que (arrel.esquerra != nul) { minv = arrel.esquerra.clau; arrel = arrel.esquerra; } retorn minv; } // Codi del controlador public static void Main(string[] args) { BinaryTree tree = new BinaryTree (); /* Creem el següent 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); Console.Write('BST original: '); tree.Inorder(tree.root); Console.WriteLine(); Console.WriteLine('
Suprimeix un node de fulla: 20'); tree.root = tree.DeleteNode (tree.root, 20); Console.Write('Arbre BST modificat després d'eliminar el node de fulla:
'); tree.Inorder(tree.root); Console.WriteLine(); Console.WriteLine('
Suprimeix el node amb un sol fill: 70'); tree.root = tree.DeleteNode (tree.root, 70); Console.Write('Arbre BST modificat després de suprimir un sol node fill:
'); tree.Inorder(tree.root); Console.WriteLine(); Console.WriteLine('
Suprimeix el node amb els dos fills: 50'); tree.root = tree.DeleteNode (tree.root, 50); Console.Write('Arbre BST modificat després d'eliminar els dos nodes secundaris:
'); tree.Inorder(tree.root); }>>>Javascriptroot.key) root.right = this.deleteNode (root.right, clau); // Si la clau és la mateixa que la clau d'arrel, aleshores aquest és el node que s'ha d'eliminar else { // Node amb només un fill o cap fill si (root.left === null) retorna root.right; else if (root.right === null) retorna root.left; // Node amb dos fills: obteniu el successor de l'ordre (el més petit del subarbre dret) root.key = this.minValue(root.right); // Esborra el successor de l'ordre root.right = this.deleteNode(root.right, root.key); } retornar l'arrel; } minValue(node) { let minv = node.key; mentre que (node.esquerra !== nul) { minv = node.esquerra.clau; node = node.esquerra; } retorn minv; } } // Codi del controlador let tree = nou BinaryTree(); /* Creem el següent 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); console.log('BST original:'); tree.inorder(tree.root); console.log('
Suprimeix un node de fulla: 20'); tree.root = tree.deleteNode (tree.root, 20); console.log('Arbre BST modificat després d'eliminar el Node Full:'); tree.inorder(tree.root); console.log('
Suprimeix el node amb un sol fill: 70'); tree.root = tree.deleteNode (tree.root, 70); console.log('Arbre BST modificat després d'eliminar un sol node fill:'); tree.inorder(tree.root); console.log('
Suprimeix el node amb els dos fills: 50'); tree.root = tree.deleteNode (tree.root, 50); console.log('Arbre BST modificat després d'eliminar els dos nodes secundaris:'); tree.inorder(tree.root);>>>
Sortida Complexitat temporal: O(h), on h és l'alçada del BST.
Espai auxiliar: O(n). Enllaços relacionats: