Gegeven een BST , de taak is om hierin een knooppunt te verwijderen BST , die kan worden opgesplitst in 3 scenario's:
Geval 1. Verwijder een Leaf-knooppunt in BST
Verwijdering in BST
Python of
Geval 2. Verwijder een knooppunt met één kind in BST
Het verwijderen van een enkel onderliggend knooppunt is ook eenvoudig in BST. Kopieer het kind naar het knooppunt en verwijder het knooppunt .
Verwijdering in BST
Geval 3. Verwijder een knooppunt met beide kinderen in BST
Een knooppunt met beide kinderen verwijderen is niet zo eenvoudig. Hier moeten we het verwijderen van het knooppunt is zo dat de resulterende boom de eigenschappen van een BST volgt.
De truc is om de niet-geordende opvolger van het knooppunt te vinden. Kopieer de inhoud van de niet-geordende opvolger naar het knooppunt en verwijder de niet-geordende opvolger.
Opmerking: Inorder voorganger kan ook worden gebruikt.
hoe je nep-abstracte klasse injecteert
Verwijdering in binaire structuur
reguliere expressie in Java
Opmerking: Een opvolger is alleen nodig als het juiste kind niet leeg is. In dit specifieke geval kan de opvolger in de verkeerde volgorde worden verkregen door de minimumwaarde in het rechterkind van het knooppunt te vinden.
Aanbevolen praktijk Een knooppunt uit BST verwijderen Probeer het!Implementatie van verwijderingsoperatie in een 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->sleutel = artikel; temp->links = temp->rechts = NULL; retourtemperatuur; } // Een hulpprogrammafunctie voor het in volgorde doorlopen van BST void inorder(Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->sleutel); inorder(wortel->rechts); } } /* Een hulpprogrammafunctie om een nieuw knooppunt met een bepaalde sleutel in te voegen in * BST */ Node* insert(Node* node, int key) { /* Als de boom leeg is, retourneert u een nieuw knooppunt */ if (node = = NULL) return newNode(sleutel); /* Ga anders verder in de boomstructuur */ if (key< node->sleutel) knooppunt->links = invoegen(knooppunt->links, sleutel); else knooppunt->rechts = invoegen(knooppunt->rechts, sleutel); /* retourneer de (ongewijzigde) knooppuntaanwijzer */ return node; } /* Gegeven een binaire zoekboom en een sleutel, verwijdert deze functie de sleutel en retourneert de nieuwe root */ Node* deleteNode(Node* root, int k) {// Basisgeval als (root == NULL) root retourneert; // Als de te verwijderen sleutel kleiner is dan de sleutel van de root, // dan ligt deze in de linker subboom als (k< root->sleutel) { root->left = deleteNode(root->left, k); terugkeer wortel; } // Als de te verwijderen sleutel groter is dan de sleutel van de root, // dan ligt deze in de rechter subboom else if (k> root->key) { root->right = deleteNode(root->right , k); terugkeer wortel; } // Als de sleutel hetzelfde is als de sleutel van root, dan is dit het knooppunt dat moet worden verwijderd // Knooppunt met slechts één kind of geen kind if (root->left == NULL) { Knooppunt* temp = root-> rechts; root verwijderen; retourtemperatuur; } else if (root->right == NULL) { Knooppunt* temp = root->left; root verwijderen; retourtemperatuur; } // Knooppunt met twee kinderen: Haal de opvolger in volgorde op (kleinste // in de rechter subboom) Knooppunt* succParent = root; Knooppunt* succ = root->rechts; while (succ->left!= NULL) { succParent = succ; succ = succ->links; } // Kopieer de inhoud van de opvolger naar dit knooppunt root->key = succ->key; // Verwijder de opvolger in de juiste volgorde if (succParent->left == succ) succParent->left = succ->right; anders succParent->right = succ->right; verwijder succ; retourwortel; } // Stuurprogrammacode int main() {/ /* Laten we de volgende BST 50 / 30 70 / / 20 40 60 80 */ Node* root = NULL maken; wortel = invoegen(wortel, 50); wortel = invoegen(wortel, 30); wortel = invoegen(wortel, 20); wortel = invoegen(wortel, 40); wortel = invoegen(wortel, 70); wortel = invoegen(wortel, 60); wortel = invoegen(wortel, 80); printf('Originele BST: '); inorde(wortel); printf('
Verwijder een Leaf-knooppunt: 20
'); root = deleteNode(root, 20); printf('Gewijzigde BST-boom na het verwijderen van Leaf Node:
'); inorde(wortel); printf('
Verwijder knooppunt met één kind: 70
'); root = deleteNode(root, 70); printf('Gewijzigde BST-boom na het verwijderen van één onderliggend knooppunt:
'); inorde(wortel); printf('
Verwijder knooppunt met beide onderliggende: 50
'); root = deleteNode(root, 50); printf('Gewijzigde BST-boom na het verwijderen van beide onderliggende knooppunten:
'); inorde(wortel); retour 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->sleutel = artikel; temp->links = temp->rechts = NULL; retourtemperatuur; } // Een hulpprogrammafunctie voor het in volgorde doorlopen van BST void inorder(struct Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->sleutel); inorder(wortel->rechts); } } /* Een hulpprogrammafunctie om een nieuw knooppunt met een bepaalde sleutel in BST in te voegen */ struct Node* insert(struct Node* node, int key) { /* Als de boom leeg is, retourneert u een nieuw knooppunt */ if (node == NULL) return newNode(sleutel); /* Ga anders verder in de boomstructuur */ if (key< node->sleutel) knooppunt->links = invoegen(knooppunt->links, sleutel); else knooppunt->rechts = invoegen(knooppunt->rechts, sleutel); /* retourneer de (ongewijzigde) knooppuntaanwijzer */ return node; } /* Gegeven een binaire zoekboom en een sleutel, verwijdert deze functie de sleutel en retourneert de nieuwe root */ struct Node* deleteNode(struct Node* root, int k) {/ // Basisscenario if (root == NULL) return wortel; // Als de sleutel die moet worden verwijderd kleiner is dan de sleutel van de root, dan ligt deze in de linker subboom als (k< root->sleutel) { root->left = deleteNode(root->left, k); terugkeer root; } // Als de te verwijderen sleutel groter is dan de sleutel van de root, dan ligt deze in de rechter subboom else if (k> root->key) { root->right = deleteNode(root->right, k ); terugkeer root; } // Als de sleutel hetzelfde is als de sleutel van root, dan is dit het knooppunt dat moet worden verwijderd // Knooppunt met slechts één kind of geen kind if (root->left == NULL) { struct Node* temp = root->rechts; gratis(wortel); retourtemperatuur; } else if (root->right == NULL) { struct Node* temp = root->left; gratis(wortel); retourtemperatuur; } // Knooppunt met twee kinderen: Haal de in de juiste volgorde opvolgende opvolger (kleinste in de rechter subboom) struct Knooppunt* succParent = root; struct Knooppunt* succ = root->rechts; while (succ->left!= NULL) { succParent = succ; succ = succ->links; } // Kopieer de inhoud van de opvolger naar dit knooppunt root->key = succ->key; // Verwijder de opvolger in de juiste volgorde if (succParent->left == succ) succParent->left = succ->right; anders succParent->right = succ->right; gratis(suc); retourwortel; } // Stuurprogrammacode int main() {/ /* Laten we de volgende BST 50 / 30 70 / / 20 40 60 80 */ struct Node* root = NULL maken; wortel = invoegen(wortel, 50); invoegen(wortel, 30); invoegen(wortel, 20); invoegen(wortel, 40); invoegen(wortel, 70); invoegen(wortel, 60); invoegen(wortel, 80); printf('Originele BST: '); inorde(wortel); printf('
Verwijder een Leaf-knooppunt: 20
'); root = deleteNode(root, 20); printf('Gewijzigde BST-boom na het verwijderen van Leaf Node:
'); inorde(wortel); printf('
Verwijder knooppunt met één kind: 70
'); root = deleteNode(root, 70); printf('Gewijzigde BST-boom na het verwijderen van één onderliggend knooppunt:
'); inorde(wortel); printf('
Verwijder knooppunt met beide onderliggende: 50
'); root = deleteNode(root, 50); printf('Gewijzigde BST-boom na het verwijderen van beide onderliggende knooppunten:
'); inorde(wortel); retour 0; }> Java 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>knooppunt.sleutel) { knooppunt.rechts = invoegen(knooppunt.rechts, sleutel); } // retourneer het (ongewijzigde) knooppunt pointer retourknooppunt; } // Een hulpprogrammafunctie voor het in volgorde doorlopen van BST void inorder(Node root) { if (root != null) { inorder(root.left); Systeem.uit.print(root.key + ' '); inorder(root.right); } } // Gegeven een binaire zoekboom en een sleutel, verwijdert deze functie de sleutel en retourneert de nieuwe root Node deleteNode(Node root, int key) {/ // Basisgeval if (root == null) { return root; } // Als de te verwijderen sleutel kleiner is dan de sleutel van de root, dan ligt deze in de linker subboom 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 = deleteNode(root.right, sleutel); } // Als de sleutel hetzelfde is als de sleutel van root, dan is dit het knooppunt dat moet worden verwijderd else {/ // Knooppunt met slechts één kind of geen kind if (root.left == null) { return root.right; } else if (root.right == null) { return root.left; } // Knooppunt met twee kinderen: haal de opvolger in de juiste volgorde op (kleinste in de rechter subboom) root.key = minValue(root.right); // Verwijder de opvolger root.right = deleteNode(root.right, root.key); } return root; } int minValue(knooppuntroot) { int minv = root.key; while (root.left!= null) { minv = root.left.key; root = root.links; } retour minv; } // Stuurprogrammacode public static void main(String[] args) { BinaryTree tree = new BinaryTree(); /* Laten we de volgende BST maken 50 / 30 70 / / 20 40 60 80 */ tree.root = tree.insert(tree.root, 50); boom.insert(boom.root, 30); boom.insert(boom.root, 20); boom.insert(boom.root, 40); boom.insert(boom.root, 70); boom.insert(boom.root, 60); boom.insert(boom.root, 80); System.out.print('Originele BST: '); boom.inorder(boom.root); Systeem.out.println(); System.out.println('
Verwijder een Leaf-knooppunt: 20'); boom.root = boom.deleteNode(boom.root, 20); System.out.print('Gewijzigde BST-boom na het verwijderen van Leaf Node:
'); boom.inorder(boom.root); Systeem.out.println(); System.out.println('
Verwijder knooppunt met één kind: 70'); boom.root = boom.deleteNode(boom.root, 70); System.out.print('Gewijzigde BST-boom na het verwijderen van één onderliggend knooppunt:
'); boom.inorder(boom.root); Systeem.out.println(); System.out.println('
Verwijder knooppunt met beide onderliggende elementen: 50'); boom.root = boom.deleteNode(boom.root, 50); System.out.print('Gewijzigde BST-boom na het verwijderen van beide onderliggende knooppunten:
'); boom.inorder(boom.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) # retourneer de (ongewijzigde) node pointer return node # Een nutsfunctie om in volgorde de BST te doorlopen def inorder (self, root): if root: self .inorder(root.left) print(root.key, end=' ') self.inorder(root.right) # Gegeven een binaire zoekboom en een sleutel, verwijdert deze functie de sleutel en retourneert de nieuwe root def deleteNode (self, root, key): # Basisgeval als root Geen is: return root # Als de sleutel die moet worden verwijderd kleiner is dan de sleutel van de root, dan ligt deze in de linker subboom als 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) # Als de sleutel hetzelfde is als de sleutel van root, dan is dit het knooppunt dat moet worden verwijderd. Anders: # Knooppunt met slechts één kind of geen kind als root.left is Geen: retourneert root.right elif root.right is Geen: retourneert root.left # Knooppunt met twee kinderen: haal de opvolger in volgorde op (kleinste in de rechter subboom) root.key = self.minValue(root.right) # Verwijder de opvolger root.right = self.deleteNode(root.right, root.key) return root def minValue(self, root): minv = root.key terwijl root.left: minv = root.left.key root = root.left return minv # Stuurprogrammacode if __name__ == '__main__': tree = BinaryTree() # Laten we de volgende BST maken # 50 # / # 30 70 # / / # 20 40 60 80 tree.root = boom.insert(boom.wortel, 50) boom.insert(boom.wortel, 30) boom.insert(boom.wortel, 20) boom.insert(boom.wortel, 40) boom.insert(boom.wortel, 70 ) tree.insert(boom.root, 60) tree.insert(boom.root, 80) print('Originele BST:', end=' ') tree.inorder(boom.root) print() print ('
Verwijder een Leaf Node: 20') tree.root = tree.deleteNode(tree.root, 20) print('Gewijzigde BST-boom na het verwijderen van Leaf Node:') tree.inorder(tree.root) print() print('
Verwijder knooppunt met één onderliggend knooppunt: 70') tree.root = tree.deleteNode(boom.root, 70) print('Gewijzigde BST-boom na het verwijderen van één onderliggend knooppunt:') boom. inorder(tree.root) print() print('
Verwijder knooppunt met beide onderliggende knooppunten: 50') tree.root = tree.deleteNode(boom.root, 50) print('Gewijzigde BST-boom na het verwijderen van beide onderliggende knooppunten :') boom.inorder(boom.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 = Invoegen(node.right, sleutel); // retourneer het (ongewijzigde) knooppunt pointer retourknooppunt; } // Een hulpprogrammafunctie om de BST public void Inorder(Node root) { if (root != null) { Inorder(root.left); Console.Write(root.key + ''); Inorde(root.right); } } // Gegeven een binaire zoekboom en een sleutel, verwijdert deze functie de sleutel en retourneert de nieuwe root public Node DeleteNode(Node root, int key) {// Basisgeval als (root == null) root retourneert; // Als de te verwijderen sleutel kleiner is dan de sleutel van de root, dan ligt deze in de linker subboom 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 = DeleteNode(root.right, sleutel); // Als de sleutel hetzelfde is als de sleutel van root, dan is dit het knooppunt dat verwijderd moet worden else {// Knooppunt met slechts één kind of geen kind if (root.left == null) retourneert root.right; else if (root.right == null) retourneert root.left; // Knooppunt met twee kinderen: haal de opvolger in volgorde op (kleinste in de rechter subboom) root.key = MinValue(root.right); // Verwijder de opvolger root.right = DeleteNode(root.right, root.key); } return root; } public int MinValue(Node root) { int minv = root.key; while (root.left!= null) { minv = root.left.key; root = root.links; } retour minv; } // Stuurprogrammacode public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); /* Laten we de volgende BST maken 50 / 30 70 / / 20 40 60 80 */ tree.root = tree.Insert(tree.root, 50); boom.Insert(boom.root, 30); boom.Insert(boom.root, 20); boom.Insert(boom.root, 40); boom.Insert(boom.root, 70); boom.Insert(boom.root, 60); boom.Insert(boom.root, 80); Console.Write('Originele BST: '); boom.Inorde(boom.root); Console.WriteLine(); Console.WriteLine('
Verwijder een Leaf-knooppunt: 20'); boom.root = boom.DeleteNode(boom.root, 20); Console.Write('Gewijzigde BST-boom na het verwijderen van Leaf Node:
'); boom.Inorde(boom.root); Console.WriteLine(); Console.WriteLine('
Verwijder knooppunt met één kind: 70'); boom.root = boom.DeleteNode(boom.root, 70); Console.Write('Gewijzigde BST-boom na het verwijderen van één onderliggend knooppunt:
'); boom.Inorde(boom.root); Console.WriteLine(); Console.WriteLine('
Verwijder knooppunt met beide onderliggende elementen: 50'); boom.root = boom.DeleteNode(boom.root, 50); Console.Write('Gewijzigde BST-boom na het verwijderen van beide onderliggende knooppunten:
'); boom.Inorde(boom.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>knooppunt.sleutel) knooppunt.rechts = dit.insert(knooppunt.rechts, sleutel); // retourneer het (ongewijzigde) knooppunt pointer retourknooppunt; } // Een hulpprogrammafunctie om BST in volgorde te doorlopen inorder(node) { if (node !== null) { this.inorder(node.left); console.log(knooppunt.sleutel + ''); this.inorder(knooppunt.right); } } // Gegeven een binaire zoekboom en een sleutel, verwijdert deze functie de sleutel en retourneert de nieuwe root deleteNode(root, key) {// Basisgeval if (root === null) return root; // Als de te verwijderen sleutel kleiner is dan de sleutel van de root, dan ligt deze in de linker subboom 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, sleutel); // Als de sleutel hetzelfde is als de sleutel van root, dan is dit het knooppunt dat verwijderd moet worden else {/ // Knooppunt met slechts één kind of geen kind if (root.left === null) retourneert root.right; else if (root.right === null) retourneert root.left; // Knooppunt met twee kinderen: haal de opvolger in volgorde op (kleinste in de rechter subboom) root.key = this.minValue(root.right); // Verwijder de opvolger root.right = this.deleteNode(root.right, root.key); } return root; } minValue(knooppunt) {let minv = knooppunt.sleutel; while (node.left!== null) { minv = node.left.key; knooppunt = knooppunt.links; } retour minv; } } // Stuurprogrammacode let tree = new BinaryTree(); /* Laten we de volgende BST maken 50 / 30 70 / / 20 40 60 80 */ tree.root = tree.insert(tree.root, 50); boom.insert(boom.root, 30); boom.insert(boom.root, 20); boom.insert(boom.root, 40); boom.insert(boom.root, 70); boom.insert(boom.root, 60); boom.insert(boom.root, 80); console.log('Originele BST:'); boom.inorder(boom.root); console.log('
Verwijder een Leaf-knooppunt: 20'); boom.root = boom.deleteNode(boom.root, 20); console.log('Gewijzigde BST-boom na het verwijderen van Leaf Node:'); boom.inorder(boom.root); console.log('
Verwijder knooppunt met één kind: 70'); boom.root = boom.deleteNode(boom.root, 70); console.log('Gewijzigde BST-boom na het verwijderen van één onderliggend knooppunt:'); boom.inorder(boom.root); console.log('
Verwijder knooppunt met beide onderliggende elementen: 50'); boom.root = boom.deleteNode(boom.root, 50); console.log('Gewijzigde BST-boom na het verwijderen van beide onderliggende knooppunten:'); boom.inorder(boom.root);> Uitvoer
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...>
Tijdcomplexiteit: O(h), waarbij h de hoogte van de BST is.
Hulpruimte: Op).
Gerelateerde Links: