Dawać BST , zadaniem jest usunięcie węzła w tym BST , które można podzielić na 3 scenariusze:
Przypadek 1. Usuń węzeł liścia w BST
Usunięcie w BST
Przypadek 2. Usuń węzeł z pojedynczym dzieckiem w BST
Usuwanie pojedynczego węzła podrzędnego jest również proste w BST. Skopiuj dziecko do węzła i usuń węzeł .
pyton w kształcie wielbłąda
sql wybór wielu tabel
Usunięcie w BST
Przypadek 3. Usuń węzeł z obydwoma dziećmi w BST
Usunięcie węzła z obydwoma dziećmi nie jest takie proste. Tutaj musimy usunięcie węzła odbywa się w taki sposób, aby powstałe drzewo było zgodne z właściwościami BST.
Sztuka polega na znalezieniu inorderowego następcy węzła. Skopiuj zawartość inorderowego następnika węzła i usuń inorder następcę.
Notatka: Można również użyć poprzednika Inorder.
jak wykonać skrypt
Usuwanie w drzewie binarnym
Notatka: Następnik Inorder jest potrzebny tylko wtedy, gdy prawe dziecko nie jest puste. W tym konkretnym przypadku następcę rzędu można uzyskać, znajdując minimalną wartość w prawym dziecku węzła.
Zalecana praktyka Usuń węzeł z BST Wypróbuj!Implementacja operacji usuwania w 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->klucz = przedmiot; temp->lewo = temp->prawo = NULL; temperatura powrotu; } // Funkcja narzędziowa umożliwiająca przechodzenie w kolejności BST void inorder(Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->key); inorder(root->right); } } /* Funkcja narzędziowa umożliwiająca wstawienie nowego węzła o podanym kluczu w * BST */ Node* wstaw(Węzeł* węzeł, int klucz) { /* Jeśli drzewo jest puste, zwróć nowy węzeł */ if (node = = NULL) zwróć nowyWęzeł(klucz); /* W przeciwnym razie wróć w dół drzewa */ if (key< node->klucz) węzeł->lewy = wstaw(węzeł->lewy, klucz); w przeciwnym razie węzeł->prawo = wstaw(węzeł->prawo, klawisz); /* zwróć (niezmieniony) wskaźnik węzła */ zwróć węzeł; } /* Biorąc pod uwagę drzewo wyszukiwania binarnego i klucz, ta funkcja usuwa klucz i zwraca nowy katalog główny */ Node* DeleteNode(Node* root, int k) { // Przypadek podstawowy if (root == NULL) return root; // Jeśli klucz do usunięcia jest mniejszy niż klucz roota, // to leży on w lewym poddrzewie if (k< root->klucz) { root->left = DeleteNode(root->left, k); zwróć korzeń; } // Jeśli klucz do usunięcia jest większy niż klucz roota, // to leży w prawym poddrzewie else if (k> root->key) { root->right = DeleteNode(root->right , k); zwróć korzeń; } // Jeśli klucz jest taki sam jak klucz roota, to jest to węzeł do usunięcia // Węzeł z tylko jednym dzieckiem lub bez dziecka if (root->left == NULL) { Node* temp = root-> Prawidłowy; usuń root; temperatura powrotu; } else if (root->right == NULL) { Węzeł* temp = root->left; usuń root; temperatura powrotu; } // Węzeł z dwójką dzieci: Uzyskaj następcę w kolejności (najmniejszy // w prawym poddrzewie) Węzeł* succParent = root; Węzeł* succ = root->right; while (succ->left != NULL) { succParent = succ; succ = succ->w lewo; } // Skopiuj zawartość kolejnego następnika do tego węzła root->key = succ->key; // Usuń następcę inorder if (succParent->left == succ) succParent->left = succ->right; w przeciwnym razie succParent->right = succ->right; usuń sukces; zwróć korzeń; } // Kod sterownika int main() { /* Utwórzmy następujące BST 50 / 30 70 / / 20 40 60 80 */ Węzeł* root = NULL; root = wstaw(korzeń, 50); root = wstaw(korzeń, 30); root = wstaw(korzeń, 20); root = wstaw(korzeń, 40); root = wstaw(korzeń, 70); root = wstaw(korzeń, 60); root = wstaw(korzeń, 80); printf('Oryginalny BST: '); inorder(root); printf('
Usuń węzeł liścia: 20
'); root = usuńNode(root, 20); printf('Zmodyfikowane drzewo BST po usunięciu węzła liścia:
'); inorder(root); printf('
Usuń węzeł z jednym dzieckiem: 70
'); root = usuńNode(root, 70); printf('Zmodyfikowane drzewo BST po usunięciu pojedynczego węzła podrzędnego:
'); inorder(root); printf('
Usuń węzeł z obydwoma dziećmi: 50
'); root = usuńNode(root, 50); printf('Zmodyfikowane drzewo BST po usunięciu obu węzłów podrzędnych:
'); inorder(root); zwróć 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->klucz = przedmiot; temp->lewo = temp->prawo = NULL; temperatura powrotu; } // Funkcja narzędziowa umożliwiająca przechodzenie w kolejności BST void inorder(struct Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', root->key); inorder(root->right); } } /* Funkcja narzędziowa umożliwiająca wstawienie nowego węzła o podanym kluczu w BST */ struct Node* wstaw(struct Node* węzeł, int klucz) { /* Jeśli drzewo jest puste, zwróć nowy węzeł */ if (węzeł == NULL) zwróć nowy węzeł (klucz); /* W przeciwnym razie wróć w dół drzewa */ if (key< node->klucz) węzeł->lewy = wstaw(węzeł->lewy, klucz); w przeciwnym razie węzeł->prawo = wstaw(węzeł->prawo, klawisz); /* zwróć (niezmieniony) wskaźnik węzła */ zwróć węzeł; } /* Biorąc pod uwagę drzewo wyszukiwania binarnego i klucz, ta funkcja usuwa klucz i zwraca nowy katalog główny */ struct Node* DeleteNode(struct Node* root, int k) { // Przypadek podstawowy if (root == NULL) return źródło; // Jeśli klucz do usunięcia jest mniejszy niż klucz roota, to leży on w lewym poddrzewie if (k< root->klucz) { root->left = DeleteNode(root->left, k); zwróć korzeń; } // Jeśli klucz do usunięcia jest większy niż klucz roota, to leży on w prawym poddrzewie else if (k> root->key) { root->right = DeleteNode(root->right, k ); zwróć korzeń; } // Jeśli klucz jest taki sam jak klucz roota, to jest to węzeł do usunięcia // Węzeł z tylko jednym dzieckiem lub bez dziecka if (root->left == NULL) { struct Node* temp = root-> prawda; darmowy (root); temperatura powrotu; } else if (root->right == NULL) { struct Node* temp = root->left; darmowy (root); temperatura powrotu; } // Węzeł z dwójką dzieci: Pobierz następcę w kolejności (najmniejszy w prawym poddrzewie) struct Node* succParent = root; struct Node* succ = root->right; while (succ->left != NULL) { succParent = succ; succ = succ->w lewo; } // Skopiuj zawartość kolejnego następnika do tego węzła root->key = succ->key; // Usuń następcę inorder if (succParent->left == succ) succParent->left = succ->right; w przeciwnym razie succParent->right = succ->right; wolny(sukces); zwróć korzeń; } // Kod sterownika int main() { /* Utwórzmy następujący BST 50 / 30 70 / / 20 40 60 80 */ struct Node* root = NULL; root = wstaw(korzeń, 50); wstaw(korzeń, 30); wstaw(korzeń, 20); wstaw(korzeń, 40); wstaw(korzeń, 70); wstaw(korzeń, 60); wstaw(korzeń, 80); printf('Oryginalny BST: '); inorder(root); printf('
Usuń węzeł liścia: 20
'); root = usuńNode(root, 20); printf('Zmodyfikowane drzewo BST po usunięciu węzła liścia:
'); inorder(root); printf('
Usuń węzeł z jednym dzieckiem: 70
'); root = usuńNode(root, 70); printf('Zmodyfikowane drzewo BST po usunięciu pojedynczego węzła podrzędnego:
'); inorder(root); printf('
Usuń węzeł z obydwoma dziećmi: 50
'); root = usuńNode(root, 50); printf('Zmodyfikowane drzewo BST po usunięciu obu węzłów podrzędnych:
'); inorder(root); zwróć 0; }> Jawa 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>węzeł.klucz) { węzeł.prawy = wstaw(węzeł.prawy, klucz); } // zwróć (niezmieniony) wskaźnik węzła. zwróć węzeł; } // Funkcja narzędziowa do wykonywania przejścia w kolejności BST void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(root.key + ' '); inorder(root.right); } } // Biorąc pod uwagę drzewo wyszukiwania binarnego i klucz, ta funkcja usuwa klucz i zwraca nowy element główny. Node DeleteNode(Node root, int key) { // Przypadek podstawowy if (root == null) { return root; } // Jeśli klucz do usunięcia jest mniejszy niż klucz roota, to leży on w lewym poddrzewie 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 = usuńNode(root.right, klucz); } // Jeśli klucz jest taki sam jak klucz roota, to jest to węzeł do usunięcia else { // Węzeł z tylko jednym dzieckiem lub bez dziecka if (root.left == null) { return root.right; } else if (root.right == null) { return root.left; } // Węzeł z dwójką dzieci: Pobierz następcę w kolejności (najmniejszy w prawym poddrzewie) root.key = minValue(root.right); // Usuń następcę kolejności root.right = DeleteNode(root.right, root.key); } zwróć korzeń; } int minValue(korzeń węzła) { int minv = root.key; while (root.left != null) { minv = root.left.key; root = root.left; } zwróć minv; } // Kod sterownika public static void main(String[] args) { Drzewo BinaryTree = nowe Drzewo Binary(); /* Stwórzmy następujące BST 50 / 30 70 / / 20 40 60 80 */ drzewo.root = drzewo.insert(drzewo.root, 50); drzewo.wstaw(drzewo.korzeń, 30); drzewo.wstaw(drzewo.korzeń, 20); drzewo.wstaw(korzeń drzewa, 40); drzewo.wstaw(korzeń drzewa, 70); drzewo.wstaw(korzeń drzewa, 60); drzewo.wstaw(drzewo.korzeń, 80); System.out.print('Oryginalny BST: '); drzewo.inorder(drzewo.korzeń); System.out.println(); System.out.println('
Usuń węzeł liścia: 20'); drzewo.root = drzewo.deleteNode(drzewo.root, 20); System.out.print('Zmodyfikowane drzewo BST po usunięciu węzła liścia:
'); drzewo.inorder(drzewo.korzeń); System.out.println(); System.out.println('
Usuń węzeł z pojedynczym dzieckiem: 70'); drzewo.root = drzewo.deleteNode(drzewo.root, 70); System.out.print('Zmodyfikowane drzewo BST po usunięciu pojedynczego węzła podrzędnego:
'); drzewo.inorder(drzewo.korzeń); System.out.println(); System.out.println('
Usuń węzeł z obydwoma dziećmi: 50'); drzewo.root = drzewo.deleteNode(drzewo.root, 50); System.out.print('Zmodyfikowane drzewo BST po usunięciu obu węzłów podrzędnych:
'); drzewo.inorder(drzewo.korzeń); } }> 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) # zwraca (niezmieniony) wskaźnik węzła return node # Funkcja użyteczności służąca do wykonywania inorderowego przechodzenia przez BST def inorder(self, root): if root: self .inorder(root.left) print(root.key, end=' ') self.inorder(root.right) # Biorąc pod uwagę drzewo wyszukiwania binarnego i klucz, ta funkcja usuwa klucz i zwraca nowy root def DeleteNode (self, root, key): # Podstawowy przypadek, jeśli root to None: return root # Jeśli klucz do usunięcia jest mniejszy niż klucz roota, to leży w lewym poddrzewie 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) # Jeśli klucz jest taki sam jak klucz roota, to jest to węzeł do usunięcia w przeciwnym razie: # Węzeł z tylko jednym dzieckiem lub bez dziecka, jeśli root.left to Brak: return root.right elif root.right to None: return root.left # Węzeł z dwójką dzieci: Uzyskaj następcę w kolejności (najmniejszy w prawym poddrzewie) root.key = self.minValue(root.right) # Usuń następcę w kolejności 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 # Kod sterownika if __name__ == '__main__': drzewo = BinaryTree() # Utwórzmy następujący BST # 50 # / # 30 70 # / / # 20 40 60 80 drzewo.root = drzewo.insert(drzewo.korzeń, 50) drzewo.insert(drzewo.korzeń, 30) drzewo.insert(drzewo.korzeń, 20) drzewo.insert(drzewo.korzeń, 40) drzewo.insert(drzewo.korzeń, 70 ) drzewo.insert(drzewo.korzeń, 60) drzewo.insert(drzewo.korzeń, 80) print('Oryginalny BST:', end=' ') drzewo.inorder(drzewo.root) print() print ('
Usuń węzeł liścia: 20') Tree.root = drzewo.deleteNode(tree.root, 20) print('Zmodyfikowane drzewo BST po usunięciu węzła liścia:') Tree.inorder(tree.root) print() print('
Usuń węzeł z pojedynczym węzłem podrzędnym: 70') drzewo.root = drzewo.deleteNode(drzewo.root, 70) print('Zmodyfikowane drzewo BST po usunięciu pojedynczego węzła podrzędnego:') drzewo. inorder(tree.root) print() print('
Usuń węzeł z obydwoma węzłami podrzędnymi: 50') Tree.root = drzewo.deleteNode(tree.root, 50) print('Zmodyfikowane drzewo BST po usunięciu obu węzłów podrzędnych :') drzewo.inorder(drzewo.korzeń)> 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>węzeł.klucz) węzeł.prawo = Wstaw(węzeł.prawo, klucz); // zwróć (niezmieniony) wskaźnik węzła. zwróć węzeł; } // Funkcja narzędziowa umożliwiająca przechodzenie w kolejności BST public void Inorder(root węzła) { if (root != null) { Inorder(root.left); Console.Write(root.key + ' '); Inorder(root.right); } } // Biorąc pod uwagę drzewo wyszukiwania binarnego i klucz, ta funkcja usuwa klucz i zwraca nowy główny publiczny Node DeleteNode(Node root, int key) { // Przypadek podstawowy if (root == null) return root; // Jeśli klucz do usunięcia jest mniejszy niż klucz roota, to leży on w lewym poddrzewie 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, klucz); // Jeśli klucz jest taki sam jak klucz roota, to jest to węzeł do usunięcia else { // Węzeł z tylko jednym dzieckiem lub bez dziecka if (root.left == null) return root.right; else if (root.right == null) zwróć root.left; // Węzeł z dwójką dzieci: pobierz następcę kolejności (najmniejszy w prawym poddrzewie) root.key = MinValue(root.right); // Usuń następcę kolejności root.right = DeleteNode(root.right, root.key); } zwróć korzeń; } public int MinValue(korzeń węzła) { int minv = root.key; while (root.left != null) { minv = root.left.key; root = root.left; } zwróć minv; } // Kod sterownika public static void Main(string[] args) { Drzewo BinaryTree = nowe Drzewo Binary(); /* Stwórzmy następujące BST 50 / 30 70 / / 20 40 60 80 */ drzewo.root = drzewo.Insert(drzewo.root, 50); drzewo.Wstaw(drzewo.korzeń, 30); drzewo.Wstaw(drzewo.korzeń, 20); drzewo.Wstaw(drzewo.korzeń, 40); drzewo.Wstaw(drzewo.korzeń, 70); drzewo.Wstaw(drzewo.korzeń, 60); drzewo.Wstaw(drzewo.korzeń, 80); Console.Write('Oryginalny BST: '); drzewo.Inorder(drzewo.korzeń); Konsola.WriteLine(); Console.WriteLine('
Usuń węzeł liścia: 20'); drzewo.root = drzewo.DeleteNode(drzewo.root, 20); Console.Write('Zmodyfikowane drzewo BST po usunięciu węzła liścia:
'); drzewo.Inorder(drzewo.korzeń); Konsola.WriteLine(); Console.WriteLine('
Usuń węzeł z jednym dzieckiem: 70'); drzewo.root = drzewo.DeleteNode(drzewo.root, 70); Console.Write('Zmodyfikowane drzewo BST po usunięciu pojedynczego węzła podrzędnego:
'); drzewo.Inorder(drzewo.korzeń); Konsola.WriteLine(); Console.WriteLine('
Usuń węzeł z obydwoma dziećmi: 50'); drzewo.root = drzewo.DeleteNode(drzewo.root, 50); Console.Write('Zmodyfikowane drzewo BST po usunięciu obu węzłów podrzędnych:
'); drzewo.Inorder(drzewo.korzeń); }> 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>węzeł.klucz) węzeł.prawo = this.insert(węzeł.prawo, klucz); // zwróć (niezmieniony) wskaźnik węzła. zwróć węzeł; } // Funkcja narzędziowa umożliwiająca przechodzenie w kolejności BST inorder(node) { if (node !== null) { this.inorder(node.left); konsola.log(klucz.węzła + ' '); this.inorder(węzeł.prawy); } } // Biorąc pod uwagę drzewo wyszukiwania binarnego i klucz, ta funkcja usuwa klucz i zwraca nowy element główny. DeleteNode(root, key) { // Przypadek podstawowy if (root === null) return root; // Jeśli klucz do usunięcia jest mniejszy niż klucz roota, to leży on w lewym poddrzewie 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, klucz); // Jeśli klucz jest taki sam jak klucz roota, to jest to węzeł do usunięcia else { // Węzeł z tylko jednym dzieckiem lub bez dziecka if (root.left === null) return root.right; else if (root.right === null) zwróć root.left; // Węzeł z dwójką dzieci: pobierz następcę kolejności (najmniejszy w prawym poddrzewie) root.key = this.minValue(root.right); // Usuń następcę inorder root.right = this.deleteNode(root.right, root.key); } zwróć korzeń; } minValue(węzeł) { niech minv = węzeł.klucz; while (node.left !== null) { minv = node.left.key; węzeł = węzeł.lewy; } zwróć minv; } } // Kod sterownika let Tree = new BinaryTree(); /* Stwórzmy następujące BST 50 / 30 70 / / 20 40 60 80 */ drzewo.root = drzewo.insert(drzewo.root, 50); drzewo.wstaw(drzewo.korzeń, 30); drzewo.wstaw(drzewo.korzeń, 20); drzewo.wstaw(korzeń drzewa, 40); drzewo.wstaw(korzeń drzewa, 70); drzewo.wstaw(korzeń drzewa, 60); drzewo.wstaw(drzewo.korzeń, 80); console.log('Oryginalny BST:'); drzewo.inorder(drzewo.korzeń); console.log('
Usuń węzeł liścia: 20'); drzewo.root = drzewo.deleteNode(drzewo.root, 20); console.log('Zmodyfikowane drzewo BST po usunięciu węzła liścia:'); drzewo.inorder(drzewo.korzeń); console.log('
Usuń węzeł z jednym dzieckiem: 70'); drzewo.root = drzewo.deleteNode(drzewo.root, 70); console.log('Zmodyfikowane drzewo BST po usunięciu pojedynczego węzła podrzędnego:'); drzewo.inorder(drzewo.korzeń); console.log('
Usuń węzeł z obydwoma dziećmi: 50'); drzewo.root = drzewo.deleteNode(drzewo.root, 50); console.log('Zmodyfikowane drzewo BST po usunięciu obu węzłów podrzędnych:'); drzewo.inorder(drzewo.korzeń);> Wyjście
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...>
Złożoność czasowa: O(h), gdzie h jest wysokością BST.
Przestrzeń pomocnicza: NA).
łączenie lewe vs łączenie prawe
Powiązane linki:
- Operacja wyszukiwania drzewa wyszukiwania binarnego
- Operacja wstawiania drzewa wyszukiwania binarnego