Binary search trees (Java) delete a node Each Node object has the following inst
ID: 3910564 • Letter: B
Question
Binary search trees (Java) delete a node
Each Node object has the following instance variables:
left: a reference to its left child
right: a reference to its right child
parent: a reference to its parent
key: the key stored in the node
value: the value associated with the key
The BST object has just two instance variables:
The overall strategy for removing a node z from a binary search tree has three basic cases but, as we shall see, one of the cases is a bit tricky.
If z has no children, then we simply remove it by modifying its parent to replace z with the sentinel as its child.
If z has just one child, then we elevate that child to take z's position in the tree by modifying z's parent to replace z by z's child.
If z has two children, then we find z's successor y—which must be in z's right subtree—and have y take z's position in the tree. The rest of z's original right subtree becomes y's new right subtree, and z's left subtree becomes y's new left subtree. This case is the tricky one because, as we shall see, it matters whether y is z's right child.
If z has no left child (part (a) of the figure), then we replace z by its right child r, which may or may not be the sentinel. When z's right child is the sentinel, this case deals with the situation in which z has no children. When z's right child is not the sentinel, this case handles the situation in which z has just one child, which is its right child.
If z has just one child, which is its left child l (part (b) of the figure), then we replace z by its left child.
Otherwise, z has both a left child l and a right child r. We find z's successor y, which lies in z's right subtree and has no left child but could have a right child x. We want to splice y out of its current location and have it replace z in the tree.
If y is z's right child (part (c)), then we replace z by y, leaving y's right child x alone.
Otherwise, y lies within z's right subtree but is not z's right child (part (d)). In this case, we first replace y by its own right child x, and then we replace z by y.
Please include as many comments as possible to the source code shown below. For example, for the following method I will add some comments to give clarity to the source code.
//Node method
public Node(int item)
{
key = item; //Set key equal to the item given
left = right = null; //Set the left child and the right child equal to null
}
// This method mainly calls deleteRec() for deleting the record with the key
void deleteKey(int key)
{
root = deleteRec(root, key);
}
--------------------------------------------------------------------------------------------------------------------------------
// Java program to demonstrate delete operation in binary search tree
class BinarySearchTree
{
/* Class containing left and right child of current node and key value*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree()
{
root = null;
}
// This method mainly calls deleteRec()
void deleteKey(int key)
{
root = deleteRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node deleteRec(Node root, int key)
{
/* Base Case: If the tree is empty */
if (root == null) return root;
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(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;
}
// This method mainly calls insertRec()
void insert(int key)
{
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key)
{
/* If the tree is empty, return a new node */
if (root == null)
{
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder()
{
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root)
{
if (root != null)
{
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
// Driver Program to test above functions
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal of the given tree");
tree.inorder();
System.out.println(" Delete 20");
tree.deleteKey(20);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 30");
tree.deleteKey(30);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 50");
tree.deleteKey(50);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
}
}
--------------------------------------------------------------------------------------------------------------------------------
// Java program to demonstrate delete operation in binary search tree
class BinarySearchTree
{
/* Class containing left and right child of current node and key value*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree()
{
root = null;
}
// This method mainly calls deleteRec()
void deleteKey(int key)
{
root = deleteRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node deleteRec(Node root, int key)
{
/* Base Case: If the tree is empty */
if (root == null) return root;
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(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;
}
// This method mainly calls insertRec()
void insert(int key)
{
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key)
{
/* If the tree is empty, return a new node */
if (root == null)
{
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder()
{
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root)
{
if (root != null)
{
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
// Driver Program to test above functions
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal of the given tree");
tree.inorder();
System.out.println(" Delete 20");
tree.deleteKey(20);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 30");
tree.deleteKey(30);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 50");
tree.deleteKey(50);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
}
}
sentinelr 1 sentinel sentinel x 1 sentinel r sentinelExplanation / Answer
package datastructure;
// Java program to demonstrate delete operation in binary search tree
// Defines a class BinarySearchTree
class BinarySearchTree
{
// Class Node definition
class Node
{
// Instance variable to store key value
int key;
// Node class object to point to left and right child of current node
Node left, right;
// Parameterized constructor definition
public Node(int item)
{
// Assigns the parameter value to instance variable as node key value
key = item;
// Initializes node left and right child to null
left = right = null;
}// End of parameterized constructor
}// End of class Node
// Declares a object of the class Node as root of BST
Node root;
// Default constructor definition
BinarySearchTree()
{
// Initializes root node to null
root = null;
}// End of default constructor
// This method mainly calls deleteRec() to delete a record
// Takes key value as parameter
void deleteKey(int key)
{
// Calls the helper method deleteRec() to delete a record
// Passes root node and key value as parameter
root = deleteRec(root, key);
}// End of method
/*
* A recursive method to delete a node from BST
* Parameter:
* root -> root node reference of BST
* key -> key value of the node to delete
* Return: Returns the deleted node
*/
Node deleteRec(Node root, int key)
{
// Base Case: If the tree is empty
// Returns the root node if the tree is empty by checking if root is null
if (root == null)
return root;
// Otherwise, recur down the tree
// Checks if the parameter key value is less than the root key value
if (key < root.key)
// Recursively calls the method for left child
root.left = deleteRec(root.left, key);
// Otherwise checks if the parameter key value is greater than the root key value
else if (key > root.key)
// Recursively calls the method for right child
root.right = deleteRec(root.right, key);
// Otherwise if key is same as root's key, then this is the node to be deleted
else
{
// Checks if root left is null then Node with only one child or no child
if (root.left == null)
// Returns root right child reference
return root.right;
// Otherwise checks if root right is null
else if (root.right == null)
// Returns root right child
return root.left;
// Node with two children: Get the in-order successor (smallest in the right subtree)
// Calls the method minValue() to find out the smallest node from right child
root.key = minValue(root.right);
// Delete the in-order successor
// by recursively calling the right child
root.right = deleteRec(root.right, root.key);
}// End of else
// Returns the new root
return root;
}// End of method
// Method to find and return the smallest value
// Takes root of the tree as parameter
int minValue(Node root)
{
// Initially stores root key value as the minimum value
int minv = root.key;
// Loops till end of the left child of the BST
while (root.left != null)
{
// Stores the current node left child key value as minimum
minv = root.left.key;
// Updates the root to its left child
root = root.left;
}// End of while loop
// Returns the minimum value
return minv;
}// End of method
// This method mainly calls insertRec() takes key value as parameter
void insert(int key)
{
// Calls the insertRec() helper method to insert a node in BST
root = insertRec(root, key);
}// End of method
/*
* A recursive function to insert a new key in BST
* Parameter:
* root -> root node of the BST
* key -> key value of the node to insert
* Return: returns the new root
*/
Node insertRec(Node root, int key)
{
// Checks if the tree is empty, then return a new node
if (root == null)
{
// Calls the parameterized constructor to create a new node
// with key value as parameter and assigns it to root
root = new Node(key);
// Returns the root
return root;
}// End of if condition
// Otherwise, recur down the tree
// Checks if the parameter key value is less than the current node key value
if (key < root.key)
// Recursively calls the insertRec() method for left child
root.left = insertRec(root.left, key);
// Otherwise, checks if the parameter key value is greater than the current node key value
else if (key > root.key)
// Recursively calls the insertRec() method for right child
root.right = insertRec(root.right, key);
// return the (unchanged) node pointer
return root;
}// End of method
// This method mainly calls InorderRec()
void inorder()
{
// Calls the helper method for in-order traversal
inorderRec(root);
}// End of method
// A utility function to do in-order traversal of BST
void inorderRec(Node root)
{
// Checks if root is not null
if (root != null)
{
// Recursively call the method for left child
inorderRec(root.left);
// Displays the key value
System.out.print(root.key + " ");
// Recursively call the method for right child
inorderRec(root.right);
}// End of if condition
}// End of method
// Driver Program to test above functions
public static void main(String[] args)
{
// Creates an object of the class BinarySearchTree
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
// Calls the method to insert node
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal of the given tree");
// Calls the method to display in-order traversal
tree.inorder();
System.out.println(" Delete 20");
// Calls the method to delete node having key value as 20
tree.deleteKey(20);
System.out.println("Inorder traversal of the modified tree");
// Calls the method to display in-order traversal
tree.inorder();
System.out.println(" Delete 30");
// Calls the method to delete node having key value as 30
tree.deleteKey(30);
System.out.println("Inorder traversal of the modified tree");
// Calls the method to display in-order traversal
tree.inorder();
System.out.println(" Delete 50");
// Calls the method to delete node having key value as 50
tree.deleteKey(50);
System.out.println("Inorder traversal of the modified tree");
// Calls the method to display in-order traversal
tree.inorder();
}// End of the method main()
}// End of class
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.