Dado un árbol de búsqueda binaria y un Node del árbol de búsqueda binaria, la tarea es eliminar el Node del árbol de búsqueda binaria de forma iterativa.
Estos son los tres casos que surgen al realizar una operación de eliminación en un BST:
1. Caso 1: el Node a eliminar es un Node hoja. Elimine directamente el Node del árbol.
10 10
/ \ delete(5) / \
7 15 ---------> 7 15
/ \ / \ \ / \
5 8 11 18 8 11 18
2. Caso 2: El Node a eliminar es un Node interno con dos hijos. Copie el contenido del sucesor en orden del Node a eliminar y elimine el sucesor en orden. El sucesor en orden se puede encontrar encontrando el elemento mínimo en el subárbol derecho del Node.
enordenSucesor(10) = 11.
10 11
/ \ delete(10) / \
7 15 ---------> 7 15
/ \ / \ / \ \
5 8 11 18 5 8 18
3. Caso 3: el Node que se eliminará es un Node interno con un hijo. Para este caso, elimine el Node y mueva su hijo hacia arriba para que tome su lugar.
10 10
/ \ delete(15) / \
7 15 ---------> 7 11
/ \ / / \
5 8 11 5 8
La intuición detrás de eliminar el sucesor en orden en el Caso 2 es que el sucesor en orden de un Node con dos hijos siempre será mayor que todos los elementos en el subárbol izquierdo del Node, ya que es el Node más pequeño en el subárbol derecho. El árbol del Node y el sucesor en orden del Node siempre serán más pequeños que todos los demás Nodes en el subárbol derecho del Node.
Esto preserva la propiedad BST de que todos los Nodes en el subárbol izquierdo de un Node dado son más pequeños que el Node dado y todos los Nodes en el subárbol derecho del Node dado son más grandes que el Node dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to delete
// a node in the BST
#include <bits/stdc++.h>
using namespace std;
// Structure of the node
typedef struct treeNode {
int data;
struct treeNode* left;
struct treeNode* right;
} treeNode;
// Utility function to print
// the inorder traversal of the BST.
void inorder(treeNode* root)
{
if (root != NULL) {
inorder(root->left);
cout << root->data << ' ';
inorder(root->right);
}
}
// Utility function to insert
// nodes into our BST
treeNode* insert(treeNode* root, int key)
{
// Check if tree is empty
if (root == NULL) {
treeNode* temp;
temp = (treeNode*)malloc(sizeof(treeNode));
temp->data = key;
temp->left = NULL;
temp->right = NULL;
return temp;
}
if (key < root->data) {
// if the key to be inserted
// is lesser than the root,
// insert into the left subtree,
// and recursively call
// the insert function with the
// root->left as the new root.
root->left = insert(root->left, key);
}
else {
// if the key to be inserted
// is greater than the root,
// insert into the right subtree,
// and recursively call
// the insert function with the
// root->right as the new root.
root->right = insert(root->right, key);
}
return root;
}
// Iterative Function to delete
// 'key' from the BST.
treeNode* deleteIterative(treeNode* root, int key)
{
treeNode* curr = root;
treeNode* prev = NULL;
// Check if the key is actually
// present in the BST.
// the variable prev points to
// the parent of the key to be deleted.
while (curr != NULL && curr->data != key) {
prev = curr;
if (key < curr->data)
curr = curr->left;
else
curr = curr->right;
}
if (curr == NULL) {
cout << "Key " << key << " not found in the"
<< " provided BST.\n";
return root;
}
// Check if the node to be
// deleted has atmost one child.
if (curr->left == NULL || curr->right == NULL) {
// newCurr will replace
// the node to be deleted.
treeNode* newCurr;
// if the left child does not exist.
if (curr->left == NULL)
newCurr = curr->right;
else
newCurr = curr->left;
// check if the node to
// be deleted is the root.
if (prev == NULL)
return newCurr;
// check if the node to be deleted
// is prev's left or right child
// and then replace this with newCurr
if (curr == prev->left)
prev->left = newCurr;
else
prev->right = newCurr;
// free memory of the
// node to be deleted.
free(curr);
}
// node to be deleted has
// two children.
else {
treeNode* p = NULL;
treeNode* temp;
// Compute the inorder successor
temp = curr->right;
while (temp->left != NULL) {
p = temp;
temp = temp->left;
}
// check if the parent of the inorder
// successor is the curr or not(i.e. curr=
// the node which has the same data as
// the given data by the user to be
// deleted). if it isn't, then make the
// the left child of its parent equal to
// the inorder successor'd right child.
if (p != NULL)
p->left = temp->right;
// if the inorder successor was the
// curr (i.e. curr = the node which has the
// same data as the given data by the
// user to be deleted), then make the
// right child of the node to be
// deleted equal to the right child of
// the inorder successor.
else
curr->right = temp->right;
curr->data = temp->data;
free(temp);
}
return root;
}
// Driver Code
int main()
{
/*
10
/ \
7 15
/ \ / \
5 8 11 18
*/
treeNode* root = NULL;
root = insert(root, 10);
root = insert(root, 7);
root = insert(root, 5);
root = insert(root, 8);
root = insert(root, 15);
root = insert(root, 11);
root = insert(root, 18);
cout << "Inorder traversal "
<< "of original BST:\n";
inorder(root);
cout << '\n';
// delete node with data value 11 (leaf)
root = deleteIterative(root, 11);
cout << "\nDeletion of 11\n";
cout << "Inorder traversal post deletion:\n";
inorder(root);
cout << '\n';
// delete node with data value 15
// (internal node with one child)
root = deleteIterative(root, 15);
cout << "\nDeletion of 15\n";
cout << "Inorder traversal post deletion:\n";
inorder(root);
cout << '\n';
// delete node with data value 10
// (root, two children)
root = deleteIterative(root, 10);
cout << "\nDeletion of 10\n";
cout << "Inorder traversal post deletion:\n";
inorder(root);
cout << '\n';
return 0;
}
Java
// Java implementation to delete
// a node in the BST
class GFG {
// Structure of the node
static class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int data) { this.data = data; }
}
// Utility function to print
// the inorder traversal of the BST.
static void inorder(TreeNode root)
{
if (root != null) {
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}
// Utility function to insert
// nodes into our BST
static TreeNode insert(TreeNode root, int key)
{
// Check if tree is empty
if (root == null) {
TreeNode temp = new TreeNode(key);
return temp;
}
if (key < root.data) {
// if the key to be inserted
// is lesser than the root,
// insert into the left subtree,
// and recursively call
// the insert function with the
// root.left as the new root.
root.left = insert(root.left, key);
}
else {
// if the key to be inserted
// is greater than the root,
// insert into the right subtree,
// and recursively call
// the insert function with the
// root.right as the new root.
root.right = insert(root.right, key);
}
return root;
}
// Iterative Function to delete
// 'key' from the BST.
static TreeNode deleteIterative(TreeNode root, int key)
{
TreeNode curr = root;
TreeNode prev = null;
// Check if the key is actually
// present in the BST.
// the variable prev points to
// the parent of the key to be deleted.
while (curr != null && curr.data != key) {
prev = curr;
if (key < curr.data)
curr = curr.left;
else
curr = curr.right;
}
if (curr == null) {
System.out.println("Key " + key
+ " not found in the"
+ " provided BST.");
return root;
}
// Check if the node to be
// deleted has atmost one child.
if (curr.left == null || curr.right == null) {
// newCurr will replace
// the node to be deleted.
TreeNode newCurr;
// if the left child does not exist.
if (curr.left == null)
newCurr = curr.right;
else
newCurr = curr.left;
// check if the node to
// be deleted is the root.
if (prev == null)
return newCurr;
// check if the node to be deleted
// is prev's left or right child
// and then replace this with newCurr
if (curr == prev.left)
prev.left = newCurr;
else
prev.right = newCurr;
}
// node to be deleted has
// two children.
else {
TreeNode p = null;
TreeNode temp;
// Compute the inorder successor
temp = curr.right;
while (temp.left != null) {
p = temp;
temp = temp.left;
}
// check if the parent of the inorder
// successor is the curr or not(i.e. curr=
// the node which has the same data as
// the given data by the user to be
// deleted). if it isn't, then make the
// the left child of its parent equal to
// the inorder successor'd right child.
if (p != null)
p.left = temp.right;
// if the inorder successor was the
// curr (i.e. curr = the node which has the
// same data as the given data by the
// user to be deleted), then make the
// right child of the node to be
// deleted equal to the right child of
// the inorder successor.
else
curr.right = temp.right;
curr.data = temp.data;
}
return root;
}
// Driver Code
public static void main(String[] args)
{
/*
10
/ \
7 15
/ \ / \
5 8 11 18
*/
TreeNode root = null;
root = insert(root, 10);
root = insert(root, 7);
root = insert(root, 5);
root = insert(root, 8);
root = insert(root, 15);
root = insert(root, 11);
root = insert(root, 18);
System.out.println(
"Inorder traversal of original BST.");
inorder(root);
System.out.println("\n");
// delete node with data value 11 (leaf)
root = deleteIterative(root, 11);
System.out.println("Deletion of 11");
System.out.println(
"Inorder traversal post deletion:");
inorder(root);
System.out.println("\n");
// delete node with data value 15
// (internal node with one child)
root = deleteIterative(root, 15);
System.out.println("Deletion of 15");
System.out.println(
"Inorder traversal post deletion:");
inorder(root);
System.out.println("\n");
// delete node with data value 10
// (root, two children)
root = deleteIterative(root, 10);
System.out.println("Deletion of 10");
System.out.println(
"Inorder traversal post deletion:");
inorder(root);
System.out.println("\n");
}
}
// This code is contributed by Lovely Jain
Python3
# Python implementation to delete
# a node in the Binary Search Tree
# Class for a node of BST.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Utility function to print
# the inorder traversal of the BST
def inorder(root):
if root != None:
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
# Utility function to insert
# nodes into our BST
def insert(root, key):
# check if tree is empty
if root == None:
temp = Node(key)
return temp
if key < root.data:
"""
if the key to be inserted is
lesser than the root,
insert into the left subtree,
and recursively call
the insert function with
the root.left as the new root.
"""
root.left = insert(root.left, key)
else:
"""
if the key to be inserted is
greater than the root,
insert into the right subtree,
and recursively call
the insert function with the
root->right as the new root.
"""
root.right = insert(root.right, key)
return root
# Iterative approach to
# delete 'key' from the BST.
def deleteIterative(root, key):
curr = root
prev = None
# First check if the key is
# actually present in the BST.
# the variable prev points to the
# parent of the key to be deleted
while(curr != None and curr.data != key):
prev = curr
if curr.data < key:
curr = curr.right
else:
curr = curr.left
if curr == None:
print("Key % d not found in\
the provided BST." % key)
return root
# Check if the node to be
# deleted has atmost one child
if curr.left == None or\
curr.right == None:
# newCurr will replace
# the node to be deleted.
newCurr = None
# if the left child does not exist.
if curr.left == None:
newCurr = curr.right
else:
newCurr = curr.left
# check if the node to
# be deleted is the root.
if prev == None:
return newCurr
# Check if the node to be
# deleted is prev's left or
# right child and then
# replace this with newCurr
if curr == prev.left:
prev.left = newCurr
else:
prev.right = newCurr
curr = None
# node to be deleted
# has two children.
else:
p = None
temp = None
# Compute the inorder
# successor of curr.
temp = curr.right
while(temp.left != None):
p = temp
temp = temp.left
# check if the parent of the
# inorder successor is the root or not.
# if it isn't, then make the left
# child of its parent equal to the
# inorder successor's right child.
if p != None:
p.left = temp.right
else:
# if the inorder successor was
# the root, then make the right child
# of the node to be deleted equal
# to the right child of the inorder
# successor.
curr.right = temp.right
curr.data = temp.data
temp = None
return root
# Function to create the BST
# and call the Delete Function
def main():
"""
10
/ \
7 15
/ \ / \
5 8 11 18
"""
root = None
root = insert(root, 10)
root = insert(root, 7)
root = insert(root, 5)
root = insert(root, 8)
root = insert(root, 15)
root = insert(root, 11)
root = insert(root, 18)
print("Inorder traversal of original BST:")
inorder(root)
print("\n")
# delete node with data value 11 (leaf)
root = deleteIterative(root, 11)
print("Deletion of 11")
print("Inorder traversal post deletion:")
inorder(root)
print("\n")
# delete node with data value 15
# (internal node with one child)
root = deleteIterative(root, 15)
print("Deletion of 15")
print("Inorder traversal post deletion:")
inorder(root)
print("\n")
# delete node with data value 10
# (root, two children)
root = deleteIterative(root, 10)
print("Deletion of 10")
print("Inorder traversal post deletion:")
inorder(root)
print()
# Driver Code
if __name__ == "__main__":
main()
Producción:
Inorder traversal of original BST: 5 7 8 10 11 15 18 Deletion of 11 Inorder traversal post deletion: 5 7 8 10 15 18 Deletion of 15 Inorder traversal post deletion: 5 7 8 10 18 Deletion of 10 Inorder traversal post deletion: 5 7 8 18
Publicación traducida automáticamente
Artículo escrito por madhavjivrajani y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA