Враховуючи а BST , завдання полягає у видаленні вузла в цьому BST , який можна розбити на 3 сценарії:
Випадок 1. Видалення кінцевого вузла в BST
Видалення в BST
3d в автокад
Випадок 2. Видалення вузла з одним дочірнім елементом у BST
У BST також легко видалити один дочірній вузол. Скопіюйте дочірній елемент у вузол і видаліть вузол .
Видалення в BST
Випадок 3. Видалення вузла з обома дочірніми елементами в BST
Видалити вузол з обома дочірніми елементами не так просто. Тут ми повинні видалити вузол таким чином, щоб результуюче дерево відповідало властивостям BST.
Хитрість полягає в тому, щоб знайти порядкового наступника вузла. Скопіюйте вміст наступника inorder до вузла та видаліть наступника inorder.
Примітка: Також можна використовувати попередник у порядку.
Видалення в бінарному дереві
Примітка: Упорядку наступник потрібен лише тоді, коли правий дочірній елемент не порожній. У цьому конкретному випадку наступника за порядком можна отримати, знайшовши мінімальне значення в правій дочірній частині вузла.
Рекомендована практика. Видаліть вузол із BST. Спробуйте!Реалізація операції видалення в 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->ключ = елемент; temp->left = temp->right = NULL; зворотна температура; } // Допоміжна функція для обходу BST за порядком void inorder(Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', корінь->ключ); inorder(корінь->справа); } } /* Допоміжна функція для вставки нового вузла з заданим ключем у * BST */ Node* insert(Node* node, int key) { /* Якщо дерево порожнє, повертає новий вузол */ if (node = = NULL) повертає новий вузол (ключ); /* В іншому випадку, повторити вниз по дереву */ якщо (ключ< node->ключ) node->left = вставити(node->left, key); else node->right = insert(node->right, key); /* повертає (незмінений) покажчик на вузол */ повертає вузол; } /* За наявності бінарного дерева пошуку та ключа ця функція видаляє ключ і повертає новий корінь */ Node* deleteNode(Node* root, int k) { // Базовий випадок if (root == NULL) return root; // Якщо ключ, який потрібно видалити, менший за кореневий ключ, // він лежить у лівому піддереві, якщо (k< root->ключ) { root->left = deleteNode(root->left, k); повернути корінь; } // Якщо ключ, який потрібно видалити, більший за ключ кореня, // тоді він лежить у правому піддереві else if (k> root->key) { root->right = deleteNode(root->right , k); повернути корінь; } // Якщо ключ збігається з ключем кореня, то цей вузол буде видалено // Вузол лише з одним дочірнім або без дочірнього if (root->left == NULL) { Node* temp = root-> справа; видалити корінь; зворотна температура; } else if (root->right == NULL) { Node* temp = root->left; видалити корінь; зворотна температура; } // Вузол із двома дочірніми елементами: отримати наступника за порядком (найменший // у правому піддереві) Вузол* succParent = root; Node* succ = root->right; while (succ->left != NULL) { succParent = succ; succ = succ->ліворуч; } // Скопіюйте вміст наступника за порядком до цього вузла root->key = succ->key; // Видалити наступника в порядку if (succParent->left == succ) succParent->left = succ->right; інакше succParent->right = succ->right; видалити succ; повернути корінь; } // Код драйвера int main() { /* Створимо наступний BST 50 / 30 70 / / 20 40 60 80 */ Node* root = NULL; корінь = вставка (корінь, 50); корінь = вставити (корінь, 30); корінь = вставити (корінь, 20); корінь = вставка (корінь, 40); корінь = вставка (корінь, 70); корінь = вставити (корінь, 60); корінь = вставка (корінь, 80); printf('Оригінальний BST: '); inorder(корінь); printf('
Видалити листковий вузол: 20
'); корінь = deleteNode(корінь, 20); printf('Змінене дерево BST після видалення листового вузла:
'); inorder(корінь); printf('
Видалити вузол з одним дочірнім: 70
'); root = deleteNode(root, 70); printf('Змінене дерево BST після видалення одного дочірнього вузла:
'); inorder(корінь); printf('
Видалити вузол з обома дочірніми: 50
'); root = deleteNode(root, 50); printf('Змінене дерево BST після видалення обох дочірніх вузлів:
'); inorder(корінь); повернути 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->ключ = елемент; temp->left = temp->right = NULL; зворотна температура; } // Допоміжна функція для обходу BST за порядком void inorder(struct Node* root) { if (root != NULL) { inorder(root->left); printf('%d ', корінь->ключ); inorder(корінь->справа); } } /* Допоміжна функція для вставки нового вузла з заданим ключем у BST */ struct Node* insert(struct Node* node, int key) { /* Якщо дерево порожнє, повертає новий вузол */ if (вузол == NULL) повертає новий вузол (ключ); /* В іншому випадку, повторити вниз по дереву */ якщо (ключ< node->ключ) node->left = вставити(node->left, key); else node->right = insert(node->right, key); /* повертає (незмінений) покажчик на вузол */ повертає вузол; } /* За наявності бінарного дерева пошуку та ключа ця функція видаляє ключ і повертає новий корінь */ struct Node* deleteNode(struct Node* root, int k) { // Базовий випадок if (root == NULL) return корінь; // Якщо ключ, який потрібно видалити, менший за кореневий ключ, тоді він знаходиться в лівому піддереві, якщо (k< root->ключ) { root->left = deleteNode(root->left, k); повернути корінь; } // Якщо ключ, який потрібно видалити, більший за ключ кореня, то він знаходиться в правому піддереві else if (k> root->key) { root->right = deleteNode(root->right, k ); повернути корінь; } // Якщо ключ збігається з ключем root, тоді цей вузол буде видалено // Вузол лише з одним дочірнім або без дочірнього if (root->left == NULL) { struct Node* temp = root->праворуч; вільний (корінь); зворотна температура; } else if (root->right == NULL) { struct Node* temp = root->left; вільний (корінь); зворотна температура; } // Вузол із двома дочірніми елементами: отримати наступника за порядком (найменший у правому піддереві) struct Node* succParent = root; struct Node* succ = root->right; while (succ->left != NULL) { succParent = succ; succ = succ->ліворуч; } // Скопіюйте вміст наступника за порядком до цього вузла root->key = succ->key; // Видалити наступника в порядку if (succParent->left == succ) succParent->left = succ->right; інакше succParent->right = succ->right; вільний (succ); повернути корінь; } // Код драйвера int main() { /* Створимо наступний BST 50 / 30 70 / / 20 40 60 80 */ struct Node* root = NULL; корінь = вставка (корінь, 50); вставити (корінь, 30); вставити (корінь, 20); вставити (корінь, 40); вставити (корінь, 70); вставити (корінь, 60); вставити (корінь, 80); printf('Оригінальний BST: '); inorder(корінь); printf('
Видалити листковий вузол: 20
'); корінь = deleteNode(корінь, 20); printf('Змінене дерево BST після видалення листового вузла:
'); inorder(корінь); printf('
Видалити вузол з одним дочірнім: 70
'); root = deleteNode(root, 70); printf('Змінене дерево BST після видалення одного дочірнього вузла:
'); inorder(корінь); printf('
Видалити вузол з обома дочірніми: 50
'); root = deleteNode(root, 50); printf('Змінене дерево BST після видалення обох дочірніх вузлів:
'); inorder(корінь); повернути 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>node.key) { node.right = insert(node.right, key); } // повертає (незмінний) покажчик вузла return node; } // Допоміжна функція для обходу за порядком BST void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(root.key + ' '); inorder(root.right); } } // За наявності бінарного дерева пошуку та ключа ця функція видаляє ключ і повертає новий кореневий вузол deleteNode(Node root, int key) { // Базовий випадок if (root == null) { return root; } // Якщо ключ, який потрібно видалити, менший за кореневий ключ, тоді він знаходиться в лівому піддереві, якщо (ключ< 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); } // Якщо ключ збігається з ключем кореня, то цей вузол буде видалено else { // Вузол лише з одним дочірнім або без дочірнього елемента if (root.left == null) { return root.right; } else if (root.right == null) { return root.left; } // Вузол із двома дочірніми елементами: отримати наступника за порядком (найменший у правому піддереві) root.key = minValue(root.right); // Видалити спадкоємця в порядку root.right = deleteNode(root.right, root.key); } повернути корінь; } int minValue(Node root) { int minv = root.key; while (root.left != null) { minv = root.left.key; корінь = root.left; } return minv; } // Код драйвера public static void main(String[] args) { BinaryTree tree = new BinaryTree(); /* Створимо наступний 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: '); tree.inorder(tree.root); System.out.println(); System.out.println('
Видалити кінцевий вузол: 20'); tree.root = tree.deleteNode(tree.root, 20); System.out.print('Змінене дерево BST після видалення листового вузла:
'); tree.inorder(tree.root); System.out.println(); System.out.println('
Видалити вузол з одним дочірнім: 70'); tree.root = tree.deleteNode(tree.root, 70); System.out.print('Змінене дерево BST після видалення одного дочірнього вузла:
'); tree.inorder(tree.root); System.out.println(); System.out.println('
Видалити вузол з обома дочірніми: 50'); tree.root = tree.deleteNode(tree.root, 50); System.out.print('Змінене дерево BST після видалення обох дочірніх вузлів:
'); 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) # повертає (незмінений) вказівник вузла return node # Допоміжна функція для виконання впорядкованого обходу BST def inorder(self, root): if root: self .inorder(root.left) print(root.key, end=' ') self.inorder(root.right) # За наявності бінарного дерева пошуку та ключа ця функція видаляє ключ і повертає новий кореневий def deleteNode (self, root, key): # Базовий випадок, якщо root дорівнює Немає: повертає root # Якщо ключ, який потрібно видалити, менший за ключ кореня, він знаходиться в лівому піддереві, якщо ключ< 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) # Якщо ключ збігається з ключем root, то цей вузол буде видалено else: # Вузол лише з одним дочірнім або без дочірнього, якщо root.left є None: return root.right elif root.right is None: return root.left # Вузол із двома дочірніми елементами: Отримати послідовник у порядку (найменший у правому піддереві) root.key = self.minValue(root.right) # Видалити спадкоємця в порядку 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 # Код драйвера if __name__ == '__main__': tree = BinaryTree() # Створимо наступний 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('Original BST:', end=' ') tree.inorder(tree.root) print() print ('
Видалити листовий вузол: 20') tree.root = tree.deleteNode(tree.root, 20) print('Змінене дерево BST після видалення листового вузла:') tree.inorder(tree.root) print() print('
Видалити вузол з одним дочірнім вузлом: 70') tree.root = tree.deleteNode(tree.root, 70) print('Змінене дерево BST після видалення одного дочірнього вузла:') дерево. inorder(tree.root) print() print('
Видалити вузол з обома дочірніми вузлами: 50') tree.root = tree.deleteNode(tree.root, 50) print('Змінене дерево BST після видалення обох дочірніх вузлів :') 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); // повернути (незмінний) покажчик вузла return node; } // Допоміжна функція для обходу за порядком BST public void Inorder(Node root) { if (root != null) { Inorder(root.left); Console.Write(root.key + ' '); Inorder(root.right); } } // За наявності бінарного дерева пошуку та ключа ця функція видаляє ключ і повертає новий кореневий public Node DeleteNode(Node root, int key) { // Базовий випадок if (root == null) return root; // Якщо ключ, який потрібно видалити, менший за кореневий ключ, тоді він знаходиться в лівому піддереві, якщо (ключ< 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, ключ); // Якщо ключ збігається з ключем кореня, то цей вузол буде видалено else { // Вузол лише з одним дочірнім елементом або без дочірнього елемента if (root.left == null) return root.right; else if (root.right == null) return root.left; // Вузол із двома дочірніми елементами: отримати наступника за порядком (найменший у правому піддереві) root.key = MinValue(root.right); // Видалити спадкоємця в порядку root.right = DeleteNode(root.right, root.key); } повернути корінь; } public int MinValue(Node root) { int minv = root.key; while (root.left != null) { minv = root.left.key; корінь = root.left; } return minv; } // Код драйвера public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); /* Давайте створимо наступний 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: '); дерево.Inorder(дерево.корінь); Console.WriteLine(); Console.WriteLine('
Видалити листковий вузол: 20'); tree.root = tree.DeleteNode(tree.root, 20); Console.Write('Змінене дерево BST після видалення листового вузла:
'); дерево.Inorder(дерево.корінь); Console.WriteLine(); Console.WriteLine('
Видалити вузол з одним дочірнім: 70'); tree.root = tree.DeleteNode(tree.root, 70); Console.Write('Змінене дерево BST після видалення одного дочірнього вузла:
'); дерево.Inorder(дерево.корінь); Console.WriteLine(); Console.WriteLine('
Видалити вузол з обома дочірніми: 50'); tree.root = tree.DeleteNode(tree.root, 50); Console.Write('Змінене дерево BST після видалення обох дочірніх вузлів:
'); дерево.Inorder(дерево.корінь); }> 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); // повернути (незмінний) покажчик вузла return node; } // Допоміжна функція для обходу за порядком BST inorder(node) { if (node !== null) { this.inorder(node.left); console.log(node.key + ' '); this.inorder(node.right); } } // За наявності бінарного дерева пошуку та ключа ця функція видаляє ключ і повертає новий кореневий deleteNode(root, key) { // Базовий випадок if (root === null) return root; // Якщо ключ, який потрібно видалити, менший за кореневий ключ, тоді він знаходиться в лівому піддереві, якщо (ключ< 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); // Якщо ключ збігається з ключем кореня, то цей вузол буде видалено else { // Вузол лише з одним дочірнім або без дочірнього if (root.left === null) return root.right; else if (root.right === null) return root.left; // Вузол із двома дочірніми елементами: отримати наступника за порядком (найменший у правому піддереві) root.key = this.minValue(root.right); // Видалити спадкоємця в порядку root.right = this.deleteNode(root.right, root.key); } повернути корінь; } minValue(node) { let minv = node.key; while (node.left !== null) { minv = node.left.key; node = node.left; } return minv; } } // Код драйвера let tree = new BinaryTree(); /* Створимо наступний 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:'); tree.inorder(tree.root); console.log('
Видалити листовий вузол: 20'); tree.root = tree.deleteNode(tree.root, 20); console.log('Змінене дерево BST після видалення листового вузла:'); tree.inorder(tree.root); console.log('
Видалити вузол з одним дочірнім: 70'); tree.root = tree.deleteNode(tree.root, 70); console.log('Змінене дерево BST після видалення одного дочірнього вузла:'); tree.inorder(tree.root); console.log('
Видалити вузол з обома дочірніми: 50'); tree.root = tree.deleteNode(tree.root, 50); console.log('Змінене дерево BST після видалення обох дочірніх вузлів:'); tree.inorder(tree.root);> Вихід
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...>
Часова складність: O(h), де h – висота BST.
Допоміжний простір: O(n).
c масив рядків
Пов'язані посилання: