Glede na a BST , naloga je izbrisati vozlišče v tem BST , ki jih je mogoče razdeliti na 3 scenarije:
Primer 1. Izbrišite listno vozlišče v BST
Brisanje v BST
Primer 2. Brisanje vozlišča z enim podrejenim elementom v BST
Tudi brisanje enega podrejenega vozlišča je v BST preprosto. Kopirajte otroka v vozlišče in izbrišite vozlišče .
Brisanje v BST
Primer 3. Izbrišite vozlišče z obema otrokoma v BST
Brisanje vozlišča z obema otrokoma ni tako preprosto. Tukaj moramo brisanje vozlišča je tako, da nastalo drevo sledi lastnostim BST.
Trik je najti naslednika vozlišča po vrstnem redu. Kopirajte vsebino naslednika vrstnega reda v vozlišče in izbrišite naslednika vrstnega reda.
Opomba: Lahko se uporabi tudi predhodnik po vrstnem redu.
Izbris v binarnem drevesu
k algoritem najbližjega soseda
Opomba: Naslednik po vrstnem redu je potreben le, če desni otrok ni prazen. V tem posebnem primeru lahko naslednika po vrstnem redu dobimo z iskanjem najmanjše vrednosti v desnem podrejenem vozlišču.
Priporočena praksa Izbrišite vozlišče iz BST Poskusite!Izvedba operacije brisanja v 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->ključ = predmet; temp->levo = temp->desno = NULL; povratna temperatura; } // Pomožna funkcija za prečkanje po vrstnem redu BST void inorder(Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->key); inorder(root->desno); } } /* Pomožna funkcija za vstavljanje novega vozlišča z danim ključem v * BST */ Node* insert(Node* node, int key) { /* Če je drevo prazno, vrni novo vozlišče */ if (node = = NULL) vrni novo vozlišče (ključ); /* V nasprotnem primeru se ponovi po drevesu */ če (ključ< node->ključ) vozlišče->levo = vstavi(vozlišče->levo, ključ); sicer vozlišče->desno = vstavi(vozlišče->desno, ključ); /* vrne (nespremenjen) kazalec vozlišča */ vrni vozlišče; } /* Glede na binarno iskalno drevo in ključ ta funkcija izbriše ključ in vrne nov koren */ Node* deleteNode(Node* root, int k) { // Osnovni primer if (root == NULL) return root; // Če je ključ, ki ga želite izbrisati, manjši od korenskega ključa, // potem leži v levem poddrevesu, če (k< root->ključ) { root->left = deleteNode(root->left, k); povratni koren; } // Če je ključ za brisanje večji od korenskega ključa, // potem leži v desnem poddrevesu else if (k> root->key) { root->right = deleteNode(root->right , k); povratni koren; } // Če je ključ enak kot korenski ključ, potem je to vozlišče za brisanje // Vozlišče s samo enim podrejenim ali brez podrejenega if (root->left == NULL) { Node* temp = root-> prav; izbriši koren; povratna temperatura; } else if (root->right == NULL) { Node* temp = root->left; izbriši koren; povratna temperatura; } // Vozlišče z dvema otrokoma: Pridobite naslednika po vrstnem redu (najmanjši // v desnem poddrevesu) Vozlišče* succParent = root; Vozlišče* succ = root->desno; medtem ko (succ->left != NULL) { succParent = succ; succ = succ->levo; } // Kopiraj vsebino naslednika po vrstnem redu v to vozlišče root->key = succ->key; // Izbriši naslednika po vrstnem redu if (succParent->left == succ) succParent->left = succ->right; else succParent->right = succ->right; izbrisati succ; povratni koren; } // Koda gonilnika int main() { /* Ustvarimo naslednji BST 50 / 30 70 / / 20 40 60 80 */ Node* root = NULL; koren = vstavi(koren, 50); koren = vstavi(koren, 30); koren = vstavi(koren, 20); koren = vstavi (koren, 40); koren = vstavi(koren, 70); koren = vstavi(koren, 60); koren = vstavi(koren, 80); printf('Izvirni BST: '); inorder(root); printf('
Izbriši listno vozlišče: 20
'); root = deleteNode(root, 20); printf('Spremenjeno drevo BST po brisanju listnega vozlišča:
'); inorder(root); printf('
Izbriši vozlišče z enim podrejenim: 70
'); root = deleteNode(root, 70); printf('Spremenjeno drevo BST po brisanju enega podrejenega vozlišča:
'); inorder(root); printf('
Izbriši vozlišče z obema otrokoma: 50
'); root = deleteNode(root, 50); printf('Spremenjeno drevo BST po brisanju obeh podrejenih vozlišč:
'); inorder(root); vrni 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->ključ = predmet; temp->levo = temp->desno = NULL; povratna temperatura; } // Pomožna funkcija za prečkanje po vrstnem redu BST void inorder(struct Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->key); inorder(root->desno); } } /* Pomožna funkcija za vstavljanje novega vozlišča z danim ključem v BST */ struct Node* insert(struct Node* node, int key) { /* Če je drevo prazno, vrni novo vozlišče */ if (vozlišče == NULL) vrni novo vozlišče (ključ); /* V nasprotnem primeru se ponovi po drevesu */ če (ključ< node->ključ) vozlišče->levo = vstavi(vozlišče->levo, ključ); sicer vozlišče->desno = vstavi(vozlišče->desno, ključ); /* vrne (nespremenjen) kazalec vozlišča */ vrni vozlišče; } /* Glede na binarno iskalno drevo in ključ ta funkcija izbriše ključ in vrne nov koren */ struct Node* deleteNode(struct Node* root, int k) { // Osnovni primer if (root == NULL) return korenina; // Če je ključ, ki ga želite izbrisati, manjši od korenskega ključa, potem leži v levem poddrevesu, če (k< root->ključ) { root->left = deleteNode(root->left, k); povratni koren; } // Če je ključ, ki ga želite izbrisati, večji od korenskega ključa, potem leži v desnem poddrevesu else if (k> root->key) { root->right = deleteNode(root->right, k ); povratni koren; } // Če je ključ enak korenskemu ključu, potem je to vozlišče za brisanje // Vozlišče s samo enim podrejenim ali brez podrejenega if (root->left == NULL) { struct Node* temp = root-> desno; brezplačno (koren); povratna temperatura; } else if (root->right == NULL) { struct Node* temp = root->left; brezplačno (koren); povratna temperatura; } // Vozlišče z dvema otrokoma: Pridobite naslednika po vrstnem redu (najmanjši v desnem poddrevesu) struct Vozlišče* succParent = root; struct Node* succ = root->right; medtem ko (succ->left != NULL) { succParent = succ; succ = succ->levo; } // Kopiraj vsebino naslednika po vrstnem redu v to vozlišče root->key = succ->key; // Izbriši naslednika po vrstnem redu if (succParent->left == succ) succParent->left = succ->right; else succParent->right = succ->right; brezplačno (succ); povratni koren; } // Koda gonilnika int main() { /* Ustvarimo naslednji BST 50 / 30 70 / / 20 40 60 80 */ struct Node* root = NULL; koren = vstavi(koren, 50); vstavi (koren, 30); vstavi (koren, 20); vstavi (koren, 40); vstavi (koren, 70); vstavi (koren, 60); vstavi (koren, 80); printf('Izvirni BST: '); inorder(root); printf('
Izbriši listno vozlišče: 20
'); root = deleteNode(root, 20); printf('Spremenjeno drevo BST po brisanju listnega vozlišča:
'); inorder(root); printf('
Izbriši vozlišče z enim podrejenim: 70
'); root = deleteNode(root, 70); printf('Spremenjeno drevo BST po brisanju enega podrejenega vozlišča:
'); inorder(root); printf('
Izbriši vozlišče z obema otrokoma: 50
'); root = deleteNode(root, 50); printf('Spremenjeno drevo BST po brisanju obeh podrejenih vozlišč:
'); inorder(root); vrni 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>vozlišče.ključ) { vozlišče.desno = vstavi(vozlišče.desno, ključ); } // vrni (nespremenjen) kazalec vozlišča return node; } // Pomožna funkcija za prečkanje po vrstnem redu BST void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(root.key + ' '); inorder(root.right); } } // Glede na binarno iskalno drevo in ključ ta funkcija izbriše ključ in vrne novo korensko vozlišče deleteNode(Node root, int key) { // Osnovni primer if (root == null) { return root; } // Če je ključ, ki ga želite izbrisati, manjši od korenskega ključa, potem leži v levem poddrevesu, če (ključ< 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); } // Če je ključ enak kot korenski ključ, potem je to vozlišče, ki ga je treba izbrisati else { // Vozlišče samo z enim podrejenim ali brez podrejenega if (root.left == null) { return root.right; } else if (root.right == null) { return root.left; } // Vozlišče z dvema otrokoma: Pridobite naslednika po vrstnem redu (najmanjšega v desnem poddrevesu) root.key = minValue(root.right); // Brisanje naslednika po vrstnem redu root.right = deleteNode(root.right, root.key); } vrni koren; } int minValue(Node root) { int minv = root.key; medtem ko (root.left != null) { minv = root.left.key; koren = koren.levo; } vrni minv; } // Koda gonilnika public static void main(String[] args) { BinaryTree tree = new BinaryTree(); /* Ustvarimo naslednji BST 50 / 30 70 / / 20 40 60 80 */ tree.root = tree.insert(tree.root, 50); drevo.vstavi(drevo.koren, 30); drevo.vstavi(drevo.koren, 20); drevo.vstavi(drevo.koren, 40); drevo.vstavi(drevo.koren, 70); drevo.vstavi(drevo.koren, 60); drevo.vstavi(drevo.koren, 80); System.out.print('Izvirni BST: '); drevo.inorder(drevo.koren); System.out.println(); System.out.println('
Izbriši listno vozlišče: 20'); tree.root = tree.deleteNode(tree.root, 20); System.out.print('Spremenjeno drevo BST po brisanju listnega vozlišča:
'); drevo.inorder(drevo.koren); System.out.println(); System.out.println('
Izbriši vozlišče z enim podrejenim: 70'); tree.root = tree.deleteNode(tree.root, 70); System.out.print('Spremenjeno drevo BST po brisanju enega podrejenega vozlišča:
'); drevo.inorder(drevo.koren); System.out.println(); System.out.println('
Izbriši vozlišče z obema podrejenima: 50'); tree.root = tree.deleteNode(tree.root, 50); System.out.print('Spremenjeno drevo BST po brisanju obeh podrejenih vozlišč:
'); drevo.inorder(drevo.koren); } }> 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) # vrni (nespremenjen) kazalec vozlišča return node # Pomožna funkcija za prečkanje po vrstnem redu BST def inorder(self, root): if root: self .inorder(root.left) print(root.key, end=' ') self.inorder(root.right) # Glede na binarno iskalno drevo in ključ ta funkcija izbriše ključ in vrne novo root def deleteNode (self, root, key): # Osnovni primer, če je root None: return root # Če je ključ, ki ga želite izbrisati, manjši od ključa korena, potem leži v levem poddrevesu, če je ključ< 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) # Če je ključ enak kot korenov ključ, potem je to vozlišče, ki ga je treba izbrisati sicer: # Vozlišče samo z enim podrejenim ali brez podrejenega, če root.left je None: return root.right elif root.right is None: return root.left # Vozlišče z dvema otrokoma: Pridobite naslednika po vrstnem redu (najmanjši v desnem poddrevesu) root.key = self.minValue(root.right) # Izbrišite naslednika po vrstnem redu root.right = self.deleteNode(root.right, root.key) return root def minValue(self, root): minv = root.key medtem ko root.left: minv = root.left.key root = root.left return minv # Koda gonilnika if __name__ == '__main__': tree = BinaryTree() # Ustvarimo naslednji 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('Originalni BST:', konec=' ') tree.inorder(tree.root) print() print ('
Izbriši listno vozlišče: 20') tree.root = tree.deleteNode(tree.root, 20) print('Spremenjeno drevo BST po brisanju listnega vozlišča:') tree.inorder(tree.root) print() print('
Izbriši vozlišče z enim podrejenim: 70') tree.root = tree.deleteNode(tree.root, 70) print('Spremenjeno drevo BST po brisanju enega samega podrejenega vozlišča:') drevo. inorder(tree.root) print() print('
Izbriši vozlišče z obema podrejenima: 50') tree.root = tree.deleteNode(tree.root, 50) print('Spremenjeno drevo BST po brisanju obeh podrejenih vozlišč :') 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>vozlišče.ključ) vozlišče.desno = Vstavi(vozlišče.desno, ključ); // vrni (nespremenjen) kazalec vozlišča return node; } // Pomožna funkcija za prečkanje po vrstnem redu BST public void Inorder(Node root) { if (root != null) { Inorder(root.left); Console.Write(root.key + ' '); Inorder(root.right); } } // Glede na binarno iskalno drevo in ključ ta funkcija izbriše ključ in vrne novo korensko javno vozlišče DeleteNode(Node root, int key) { // Osnovni primer if (root == null) return root; // Če je ključ, ki ga želite izbrisati, manjši od korenskega ključa, potem leži v levem poddrevesu, če (ključ< 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); // Če je ključ enak kot korenski ključ, potem je to vozlišče, ki ga je treba izbrisati else { // Vozlišče samo z enim podrejenim ali brez podrejenega if (root.left == null) return root.right; else if (root.right == null) return root.left; // Vozlišče z dvema otrokoma: Pridobite naslednika po vrstnem redu (najmanjši v desnem poddrevesu) root.key = MinValue(root.right); // Izbriši naslednika po vrstnem redu root.right = DeleteNode(root.right, root.key); } vrni koren; } public int MinValue(Node root) { int minv = root.key; medtem ko (root.left != null) { minv = root.left.key; koren = koren.levo; } vrni minv; } // Koda gonilnika public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); /* Ustvarimo naslednji BST 50 / 30 70 / / 20 40 60 80 */ tree.root = tree.Insert(tree.root, 50); drevo.Vstavi(drevo.koren, 30); drevo.Vstavi(drevo.koren, 20); drevo.Vstavi(drevo.koren, 40); drevo.Vstavi(drevo.koren, 70); drevo.Vstavi(drevo.koren, 60); drevo.Vstavi(drevo.koren, 80); Console.Write('Originalni BST: '); drevo.Inorder(tree.root); Console.WriteLine(); Console.WriteLine('
Izbriši listno vozlišče: 20'); tree.root = tree.DeleteNode(tree.root, 20); Console.Write('Spremenjeno drevo BST po brisanju listnega vozlišča:
'); drevo.Inorder(tree.root); Console.WriteLine(); Console.WriteLine('
Izbriši vozlišče z enim podrejenim: 70'); tree.root = tree.DeleteNode(tree.root, 70); Console.Write('Spremenjeno drevo BST po brisanju enega podrejenega vozlišča:
'); drevo.Inorder(tree.root); Console.WriteLine(); Console.WriteLine('
Izbriši vozlišče z obema podrejenima: 50'); tree.root = tree.DeleteNode(tree.root, 50); Console.Write('Spremenjeno drevo BST po brisanju obeh podrejenih vozlišč:
'); drevo.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>vozlišče.ključ) vozlišče.desno = this.insert(vozlišče.desno, ključ); // vrni (nespremenjen) kazalec vozlišča return node; } // Pomožna funkcija za prečkanje po vrstnem redu BST inorder(node) { if (node !== null) { this.inorder(node.left); console.log(node.key + ' '); this.inorder(node.right); } } // Glede na binarno iskalno drevo in ključ ta funkcija izbriše ključ in vrne novo korensko deleteNode(root, key) { // Osnovni primer if (root === null) return root; // Če je ključ, ki ga želite izbrisati, manjši od korenskega ključa, potem leži v levem poddrevesu, če (ključ< 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); // Če je ključ enak kot korenski ključ, potem je to vozlišče, ki ga je treba izbrisati else { // Vozlišče samo z enim podrejenim ali brez podrejenega if (root.left === null) return root.right; else if (root.right === null) return root.left; // Vozlišče z dvema otrokoma: pridobi naslednika po vrstnem redu (najmanjšega v desnem poddrevesu) root.key = this.minValue(root.right); // Izbriši naslednika po vrstnem redu root.right = this.deleteNode(root.right, root.key); } vrni koren; } minVrednost(vozlišče) { naj minv = vozlišče.ključ; medtem ko (node.left !== null) { minv = node.left.key; vozlišče = vozlišče.levo; } vrni minv; } } // Koda gonilnika let tree = new BinaryTree(); /* Ustvarimo naslednji BST 50 / 30 70 / / 20 40 60 80 */ tree.root = tree.insert(tree.root, 50); drevo.vstavi(drevo.koren, 30); drevo.vstavi(drevo.koren, 20); drevo.vstavi(drevo.koren, 40); drevo.vstavi(drevo.koren, 70); drevo.vstavi(drevo.koren, 60); drevo.vstavi(drevo.koren, 80); console.log('Izvirni BST:'); drevo.inorder(drevo.koren); console.log('
Izbriši listno vozlišče: 20'); tree.root = tree.deleteNode(tree.root, 20); console.log('Spremenjeno drevo BST po brisanju listnega vozlišča:'); drevo.inorder(drevo.koren); console.log('
Izbriši vozlišče z enim podrejenim: 70'); tree.root = tree.deleteNode(tree.root, 70); console.log('Spremenjeno drevo BST po brisanju enega podrejenega vozlišča:'); drevo.inorder(drevo.koren); console.log('
Izbriši vozlišče z obema otrokoma: 50'); tree.root = tree.deleteNode(tree.root, 50); console.log('Spremenjeno drevo BST po brisanju obeh podrejenih vozlišč:'); drevo.inorder(drevo.koren);> Izhod
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...>
Časovna zapletenost: O(h), kjer je h višina BST.
Pomožni prostor: O(n).
Sorodne povezave: