Angenommen BST , die Aufgabe besteht darin, einen Knoten darin zu löschen BST , das in drei Szenarien unterteilt werden kann:
Fall 1. Löschen Sie einen Blattknoten in BST
Löschung in BST
Fall 2. Löschen Sie einen Knoten mit einem einzigen untergeordneten Knoten in BST
Das Löschen eines einzelnen untergeordneten Knotens ist in BST ebenfalls einfach. Kopieren Sie das untergeordnete Element auf den Knoten und löschen Sie den Knoten .
Löschung in BST
Fall 3. Löschen Sie einen Knoten mit beiden untergeordneten Knoten in BST
Einen Knoten mit beiden Kindern zu löschen ist nicht so einfach. Hier müssen wir Das Löschen des Knotens erfolgt so, dass der resultierende Baum den Eigenschaften eines BST folgt.
Der Trick besteht darin, den Inorder-Nachfolger des Knotens zu finden. Kopieren Sie den Inhalt des Inorder-Nachfolgers auf den Knoten und löschen Sie den Inorder-Nachfolger.
Notiz: Es können auch Inorder-Vorgänger verwendet werden.
Löschen im Binärbaum
Notiz: Inorder-Nachfolger werden nur benötigt, wenn das rechte Kind nicht leer ist. In diesem speziellen Fall kann der Inorder-Nachfolger ermittelt werden, indem der Mindestwert im rechten untergeordneten Knoten des Knotens ermittelt wird.
Empfohlene Vorgehensweise: Löschen Sie einen Knoten aus BST. Probieren Sie es aus!Implementierung der Löschoperation in einem 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->Schlüssel = Artikel; temp->left = temp->right = NULL; Rücklauftemperatur; } // Eine Hilfsfunktion zum Durchlaufen von BST in der Reihenfolge void inorder(Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->key); inorder(root->right); } } /* Eine Hilfsfunktion zum Einfügen eines neuen Knotens mit dem angegebenen Schlüssel in * BST */ Node* insert(Node* node, int key) { /* Wenn der Baum leer ist, gib einen neuen Knoten zurück */ if (node = = NULL) return newNode(key); /* Andernfalls den Baum nach unten wiederholen */ if (key< node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); /* den (unveränderten) Knotenzeiger zurückgeben */ return node; } /* Bei einem binären Suchbaum und einem Schlüssel löscht diese Funktion den Schlüssel und gibt die neue Wurzel zurück */ Node* deleteNode(Node* root, int k) { // Basisfall if (root == NULL) return root; // Wenn der zu löschende Schlüssel kleiner ist als der Schlüssel der Wurzel, // dann liegt er im linken Teilbaum, wenn (k< root->key) { root->left = deleteNode(root->left, k); root zurückgeben; } // Wenn der zu löschende Schlüssel größer ist als der Schlüssel des Roots, // dann liegt er im rechten Teilbaum else if (k> root->key) { root->right = deleteNode(root->right , k); root zurückgeben; } // Wenn der Schlüssel mit dem Schlüssel des Roots übereinstimmt, ist dies der zu löschende Knoten. // Knoten mit nur einem Kind oder keinem Kind if (root->left == NULL) { Node* temp = root-> Rechts; Root löschen; Rücklauftemperatur; } else if (root->right == NULL) { Node* temp = root->left; Root löschen; Rücklauftemperatur; } // Knoten mit zwei Kindern: Holen Sie sich den Inorder-Nachfolger (kleinster // im rechten Teilbaum) Node* succParent = root; Node* succ = root->right; while (succ->left != NULL) { succParent = succ; succ = succ->left; } // Inhalt des Inorder-Nachfolgers auf diesen Knoten kopieren root->key = succ->key; // Den Inorder-Nachfolger löschen if (succParent->left == succ) succParent->left = succ->right; else succParent->right = succ->right; löschen erfolgreich; root zurückgeben; } // Treibercode int main() { /* Lassen Sie uns folgendes BST erstellen 50 / 30 70 / / 20 40 60 80 */ Node* root = NULL; root = insert(root, 50); root = insert(root, 30); root = insert(root, 20); root = insert(root, 40); root = insert(root, 70); root = insert(root, 60); root = insert(root, 80); printf('Original BST: '); inorder(root); printf('
Einen Blattknoten löschen: 20
'); root = deleteNode(root, 20); printf('Geänderter BST-Baum nach dem Löschen des Blattknotens:
'); inorder(root); printf('
Knoten mit einzelnem Kind löschen: 70
'); root = deleteNode(root, 70); printf('Geänderter BST-Baum nach dem Löschen eines einzelnen untergeordneten Knotens:
'); inorder(root); printf('
Knoten mit beiden untergeordneten Elementen löschen: 50
'); root = deleteNode(root, 50); printf('Geänderter BST-Baum nach dem Löschen beider untergeordneter Knoten:
'); inorder(root); 0 zurückgeben; }> 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->Schlüssel = Artikel; temp->left = temp->right = NULL; Rücklauftemperatur; } // Eine Hilfsfunktion zum Durchlaufen von BST in der Reihenfolge void inorder(struct Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->key); inorder(root->right); } } /* Eine Hilfsfunktion zum Einfügen eines neuen Knotens mit dem angegebenen Schlüssel in BST */ struct Node* insert(struct Node* node, int key) { /* Wenn der Baum leer ist, einen neuen Knoten zurückgeben */ if (node == NULL) return newNode(key); /* Andernfalls den Baum nach unten wiederholen */ if (key< node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); /* den (unveränderten) Knotenzeiger zurückgeben */ return node; } /* Bei einem binären Suchbaum und einem Schlüssel löscht diese Funktion den Schlüssel und gibt die neue Wurzel zurück */ struct Node* deleteNode(struct Node* root, int k) { // Basisfall if (root == NULL) return Wurzel; // Wenn der zu löschende Schlüssel kleiner ist als der Schlüssel der Wurzel, dann liegt er im linken Teilbaum, wenn (k< root->key) { root->left = deleteNode(root->left, k); root zurückgeben; } // Wenn der zu löschende Schlüssel größer als der Schlüssel des Roots ist, dann liegt er im rechten Teilbaum else if (k> root->key) { root->right = deleteNode(root->right, k ); root zurückgeben; } // Wenn der Schlüssel mit dem Schlüssel von Root übereinstimmt, ist dies der zu löschende Knoten // Knoten mit nur einem Kind oder keinem Kind if (root->left == NULL) { struct Node* temp = root->richtig; frei(root); Rücklauftemperatur; } else if (root->right == NULL) { struct Node* temp = root->left; frei(root); Rücklauftemperatur; } // Knoten mit zwei Kindern: Holen Sie sich den Inorder-Nachfolger (der kleinste im rechten Teilbaum) struct Node* succParent = root; struct Node* succ = root->right; while (succ->left != NULL) { succParent = succ; succ = succ->left; } // Inhalt des Inorder-Nachfolgers auf diesen Knoten kopieren root->key = succ->key; // Den Inorder-Nachfolger löschen if (succParent->left == succ) succParent->left = succ->right; else succParent->right = succ->right; kostenlos(erfolgreich); root zurückgeben; } // Treibercode int main() { /* Lassen Sie uns folgendes BST erstellen 50 / 30 70 / / 20 40 60 80 */ struct Node* root = NULL; root = insert(root, 50); einfügen(Wurzel, 30); einfügen(Wurzel, 20); einfügen(Wurzel, 40); einfügen(Wurzel, 70); einfügen(Wurzel, 60); insert(root, 80); printf('Original BST: '); inorder(root); printf('
Einen Blattknoten löschen: 20
'); root = deleteNode(root, 20); printf('Geänderter BST-Baum nach dem Löschen des Blattknotens:
'); inorder(root); printf('
Knoten mit einzelnem Kind löschen: 70
'); root = deleteNode(root, 70); printf('Geänderter BST-Baum nach dem Löschen eines einzelnen untergeordneten Knotens:
'); inorder(root); printf('
Knoten mit beiden untergeordneten Elementen löschen: 50
'); root = deleteNode(root, 50); printf('Geänderter BST-Baum nach dem Löschen beider untergeordneter Knoten:
'); inorder(root); 0 zurückgeben; }> 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>node.key) { node.right = insert(node.right, key); } // den (unveränderten) Knotenzeiger zurückgeben return node; } // Eine Hilfsfunktion zum Durchlaufen von BST in der Reihenfolge void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(root.key + ' '); inorder(root.right); } } // Bei einem binären Suchbaum und einem Schlüssel löscht diese Funktion den Schlüssel und gibt den neuen Wurzelknoten zurück deleteNode(Node root, int key) { // Basisfall if (root == null) { return root; } // Wenn der zu löschende Schlüssel kleiner ist als der Schlüssel der Wurzel, dann liegt er im linken Teilbaum 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, key); } // Wenn der Schlüssel mit dem Schlüssel von Root identisch ist, ist dies der zu löschende Knoten. else { // Knoten mit nur einem Kind oder keinem Kind if (root.left == null) { return root.right; } else if (root.right == null) { return root.left; } // Knoten mit zwei Kindern: Holen Sie sich den Inorder-Nachfolger (der kleinste im rechten Teilbaum) root.key = minValue(root.right); // Den Inorder-Nachfolger löschen root.right = deleteNode(root.right, root.key); } return root; } int minValue(Node root) { int minv = root.key; while (root.left != null) { minv = root.left.key; root = root.left; } return minv; } // Treibercode public static void main(String[] args) { BinaryTree tree = new BinaryTree(); /* Lassen Sie uns folgende BST erstellen 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('Original BST: '); tree.inorder(tree.root); System.out.println(); System.out.println('
Blattknoten löschen: 20'); tree.root = tree.deleteNode(tree.root, 20); System.out.print('Geänderter BST-Baum nach dem Löschen des Blattknotens:
'); tree.inorder(tree.root); System.out.println(); System.out.println('
Knoten mit einzelnem Kind löschen: 70'); tree.root = tree.deleteNode(tree.root, 70); System.out.print('Geänderter BST-Baum nach dem Löschen eines einzelnen untergeordneten Knotens:
'); tree.inorder(tree.root); System.out.println(); System.out.println('
Knoten mit beiden untergeordneten Elementen löschen: 50'); tree.root = tree.deleteNode(tree.root, 50); System.out.print('Geänderter BST-Baum nach dem Löschen beider untergeordneter Knoten:
'); tree.inorder(tree.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) # den (unveränderten) Knotenzeiger zurückgeben return node # Eine Hilfsfunktion zum Durchlaufen von BST in der Reihenfolge def inorder(self, root): if root: self .inorder(root.left) print(root.key, end=' ') self.inorder(root.right) # Bei einem binären Suchbaum und einem Schlüssel löscht diese Funktion den Schlüssel und gibt den neuen Root-Definitions-DeleteNode zurück (self, root, key): # Basisfall, wenn root None ist: root zurückgeben # Wenn der zu löschende Schlüssel kleiner als der Schlüssel des Roots ist, liegt er im linken Teilbaum, wenn 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) # Wenn der Schlüssel mit dem Schlüssel von Root identisch ist, ist dies der zu löschende Knoten. Sonst: # Knoten mit nur einem Kind oder keinem Kind, wenn root.left ist None: Rückkehr root.right elif root.right ist None: Rückkehr root.left # Knoten mit zwei Kindern: Holen Sie sich den Inorder-Nachfolger (der kleinste im rechten Teilbaum) root.key = self.minValue(root.right) # Löschen Sie den Inorder-Nachfolger 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 # Treibercode if __name__ == '__main__': tree = BinaryTree() # Lassen Sie uns folgendes BST erstellen # 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('Original BST:', end=' ') tree.inorder(tree.root) print() drucken ('
Einen Blattknoten löschen: 20') tree.root = tree.deleteNode(tree.root, 20) print('Geänderter BST-Baum nach dem Löschen des Blattknotens:') tree.inorder(tree.root) print() print('
Knoten mit einzelnem untergeordnetem Knoten löschen: 70') tree.root = tree.deleteNode(tree.root, 70) print('Geänderter BST-Baum nach dem Löschen eines einzelnen untergeordneten Knotens:') Baum. inorder(tree.root) print() print('
Knoten mit beiden untergeordneten Knoten löschen: 50') tree.root = tree.deleteNode(tree.root, 50) print('Geänderter BST-Baum nach dem Löschen beider untergeordneter Knoten :') 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 = Insert(node.right, key); // den (unveränderten) Knotenzeiger zurückgeben return node; } // Eine Hilfsfunktion zum Durchlaufen von BST in der Reihenfolge public void Inorder(Node root) { if (root != null) { Inorder(root.left); Console.Write(root.key + ' '); Inorder(root.right); } } // Bei einem binären Suchbaum und einem Schlüssel löscht diese Funktion den Schlüssel und gibt den neuen Root zurück public Node DeleteNode(Node root, int key) { // Base case if (root == null) return root; // Wenn der zu löschende Schlüssel kleiner ist als der Schlüssel der Wurzel, dann liegt er im linken Teilbaum 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, key); // Wenn der Schlüssel mit dem Schlüssel von Root übereinstimmt, ist dies der zu löschende Knoten. else { // Knoten mit nur einem oder keinem Kind if (root.left == null) return root.right; sonst if (root.right == null) return root.left; // Knoten mit zwei Kindern: Holen Sie sich den Inorder-Nachfolger (der kleinste im rechten Teilbaum) root.key = MinValue(root.right); // Den Inorder-Nachfolger löschen 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.left; } return minv; } // Treibercode public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); /* Lassen Sie uns folgende BST erstellen 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('Original BST: '); tree.Inorder(tree.root); Console.WriteLine(); Console.WriteLine('
Blattknoten löschen: 20'); tree.root = tree.DeleteNode(tree.root, 20); Console.Write('Geänderter BST-Baum nach dem Löschen des Blattknotens:
'); tree.Inorder(tree.root); Console.WriteLine(); Console.WriteLine('
Knoten mit einzelnem Kind löschen: 70'); tree.root = tree.DeleteNode(tree.root, 70); Console.Write('Geänderter BST-Baum nach dem Löschen eines einzelnen untergeordneten Knotens:
'); tree.Inorder(tree.root); Console.WriteLine(); Console.WriteLine('
Knoten mit beiden untergeordneten Elementen löschen: 50'); tree.root = tree.DeleteNode(tree.root, 50); Console.Write('Geänderter BST-Baum nach dem Löschen beider untergeordneter Knoten:
'); tree.Inorder(tree.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>node.key) node.right = this.insert(node.right, key); // den (unveränderten) Knotenzeiger zurückgeben return node; } // Eine Hilfsfunktion zum Durchlaufen von BST in der Reihenfolge inorder(node) { if (node !== null) { this.inorder(node.left); console.log(node.key + ' '); this.inorder(node.right); } } // Bei einem binären Suchbaum und einem Schlüssel löscht diese Funktion den Schlüssel und gibt den neuen Root zurück deleteNode(root, key) { // Basisfall if (root === null) return root; // Wenn der zu löschende Schlüssel kleiner ist als der Schlüssel der Wurzel, dann liegt er im linken Teilbaum 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, key); // Wenn der Schlüssel mit dem Schlüssel von Root übereinstimmt, ist dies der zu löschende Knoten. else { // Knoten mit nur einem oder keinem Kind if (root.left === null) return root.right; sonst if (root.right === null) return root.left; // Knoten mit zwei Kindern: Holen Sie sich den Inorder-Nachfolger (der kleinste im rechten Teilbaum) root.key = this.minValue(root.right); // Den Inorder-Nachfolger löschen root.right = this.deleteNode(root.right, root.key); } return root; } minValue(node) { let minv = node.key; while (node.left !== null) { minv = node.left.key; node = node.left; } return minv; } } // Treibercode let tree = new BinaryTree(); /* Lassen Sie uns folgende BST erstellen 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('Original BST:'); tree.inorder(tree.root); console.log('
Blattknoten löschen: 20'); tree.root = tree.deleteNode(tree.root, 20); console.log('Geänderter BST-Baum nach dem Löschen des Blattknotens:'); tree.inorder(tree.root); console.log('
Knoten mit einzelnem Kind löschen: 70'); tree.root = tree.deleteNode(tree.root, 70); console.log('Geänderter BST-Baum nach dem Löschen eines einzelnen untergeordneten Knotens:'); tree.inorder(tree.root); console.log('
Knoten mit beiden untergeordneten Elementen löschen: 50'); tree.root = tree.deleteNode(tree.root, 50); console.log('Geänderter BST-Baum nach dem Löschen beider untergeordneter Knoten:'); tree.inorder(tree.root);> Ausgabe
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...>
Zeitkomplexität: O(h), wobei h die Höhe des BST ist.
Hilfsraum: An).
Verwandte Links: