YouTipBinary Search Remove
## Binary Search Tree Node Deletion
Before discussing the deletion of nodes in a binary search tree, this section first introduces how to find and delete the minimum and maximum values.
Taking the minimum value as an example (the maximum value follows the same logic):
The logic for finding the minimum key value involves recursively searching down to the left child node:
...
// Returns the node containing the minimum key value in the binary search tree rooted at 'node'
private Node minimum(Node node) {
if (node.left == null)
return node;
return minimum(node.left);
}
...
To delete the minimum key value from a binary search tree, if the node has no right subtree, it can be deleted directly. If it has a right subtree, as shown in the figure:
!(#)
Deleting node 22, which has a right child, only requires replacing node 22 with the right subtree's node 33.
!(#)
The code for deleting the minimum value is as follows:
...
// Deletes the minimum node from the binary search tree rooted at 'node'
// Returns the root of the new binary search tree after deletion
private Node removeMin(Node node) {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
count--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
...
Now, let's discuss the three cases for deleting a node from a binary search tree:
**1.** Deleting a node with only a left child, such as node 58 in the figure below.
!(#)
After deleting element 58, let the left subtree directly replace the position of 58. The properties of the entire binary search tree remain unchanged.
!(#)
**2.** Deleting a node with only a right child, such as node 58 in the figure below.
!(#)
After deleting element 58, let the right subtree directly replace the position of 58. The properties of the entire binary search tree remain unchanged.
!(#)
**3.** Deleting a node with both left and right children, such as node 58 in the figure below.
!(#)
(1) Find the minimum value in the right subtree, which is node 59.
!(#)
(2) Node 59 replaces the node to be deleted, node 58.
!(#)
Based on the above rules, the core code example for deleting a node with key 'key' from the binary search tree rooted at 'node' is as follows:
**Source Code Package Download:*## src//binary/BSTRemove.java File Code:
package .binary;
import java.util.LinkedList;
/**
* Binary Search Tree Node Deletion
*/
public class BSTRemove<Key extends Comparable, Value> {
// The node in the tree is a private class; the outside world does not need to understand the specific implementation of the binary search tree node
private class Node {
private Key key;
private Value value;
private Node left, right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
left = right = null;
}
public Node(Node node) {
this.key = node.key;
this.value = node.value;
this.left = node.left;
this.right = node.right;
}
}
private Node root; // Root node
private int count; // Number of nodes in the tree
// Constructor, defaults to constructing an empty binary search tree
public BSTRemove() {
root = null;
count = 0;
}
// Returns the number of nodes in the binary search tree
public int size() {
return count;
}
// Returns whether the binary search tree is empty
public boolean isEmpty() {
return count == 0;
}
// Inserts a new (key, value) data pair into the binary search tree
public void insert(Key key, Value value) {
root = insert(root, key, value);
}
// Checks if the binary search tree contains the key 'key'
public boolean contain(Key key) {
return contain(root, key);
}
// Searches for the value corresponding to the key 'key' in the binary search tree. If the value does not exist, returns null
public Value search(Key key) {
return search(root, key);
}
// Pre-order traversal of the binary search tree
public void preOrder() {
preOrder(root);
}
// In-order traversal of the binary search tree
public void inOrder() {
inOrder(root);
}
// Post-order traversal of the binary search tree
public void postOrder() {
postOrder(root);
}
// Level-order traversal of the binary search tree
public void levelOrder() {
// We use LinkedList as our queue
LinkedList q = new LinkedList();
q.add(root);
while (!q.isEmpty()) {
Node node = q.remove();
System.out.println(node.key);
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
}
}
// Finds the minimum key value in the binary search tree
public Key minimum() {
assert count != 0;
Node minNode = minimum(root);
return minNode.key;
}
// Finds the maximum key value in the binary search tree
public Key maximum() {
assert count != 0;
Node maxNode = maximum(root);
return maxNode.key;
}
// Deletes the node containing the minimum value from the binary search tree
public void removeMin() {
if (root != null)
root = removeMin(root);
}
// Deletes the node containing the maximum value from the binary search tree
public void removeMax() {
if (root != null)
root = removeMax(root);
}
// Deletes the node with key 'key' from the binary search tree
public void remove(Key key) {
root = remove(root, key);
}
//********************
//* Auxiliary functions for the binary search tree
//********************
// Inserts the node (key, value) into the binary search tree rooted at 'node' using a recursive algorithm
// Returns the root of the binary search tree after inserting the new node
private Node insert(Node node, Key key, Value value) {
if (node == null) {
count++;
return new Node(key, value);
}
if (key.compareTo(node.key) == 0)
node.value = value;
else if (key.compareTo(node.key) node->key
node.right = insert(node.right, key, value);
return node;
}
// Checks if the binary search tree rooted at 'node' contains a node with key 'key' using a recursive algorithm
private boolean contain(Node node, Key key) {
if (node == null)
return false;
if (key.compareTo(node.key) == 0)
return true;
else if (key.compareTo(node.key) node->key
return contain(node.right, key);
}
// Searches for the value corresponding to 'key' in the binary search tree rooted at 'node' using a recursive algorithm
// If the value does not exist, returns NULL
private Value search(Node node, Key key) {
if (node == null)
return null;
if (key.compareTo(node.key) == 0)
return node.value;
else if (key.compareTo(node.key) node->key
return search(node.right, key);
}
// Performs a pre-order traversal on the binary search tree rooted at 'node' using a recursive algorithm
private void preOrder(Node node) {
if (node != null) {
System.out.println(node.key);
preOrder(node.left);
preOrder(node.right);
}
}
// Performs an in-order traversal on the binary search tree rooted at 'node' using a recursive algorithm
private void inOrder(Node node) {
if (node != null) {
inOrder(node.left);
System.out.println(node.key);
inOrder(node.right);
}
}
// Performs a post-order traversal on the binary search tree rooted at 'node' using a recursive algorithm
private void postOrder(Node node) {
if (node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.println(node.key);
}
}
// Returns the node containing the minimum key value in the binary search tree rooted at 'node'
private Node minimum(Node node) {
if (node.left == null)
return node;
return minimum(node.left);
}
// Returns the node containing the maximum key value in the binary search tree rooted at 'node'
private Node maximum(Node node) {
if (node.right == null)
return node;
return maximum(node.right);
}
// Deletes the minimum node from the binary search tree rooted at 'node'
// Returns the root of the new binary search tree after deletion
private Node removeMin(Node node) {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
count--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// Deletes the maximum node from the binary search tree rooted at 'node'
// Returns the root of the new binary search tree after deletion
private Node removeMax(Node node) {
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
count--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
// Deletes the node with key 'key' from the binary search tree rooted at 'node' using a recursive algorithm
// Returns the root of the new binary search tree after deletion
Node remove(Node node, Key key) {
if (node == null)
return null;
if (key.compareTo(node.key) 0) {
node.right = remove(node.right, key);
return node;
}
else { // key == node->key
// Case where the node to be deleted has an empty left subtree
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
count--;
return rightNode;
}
// Case where the node to be deleted has an empty right subtree
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
count--;
return leftNode;
}
// Case where the node to be deleted has both non-empty left and right subtrees
// Find the smallest node larger than the node to be deleted, i.e., the smallest node in the right subtree of the node to be deleted
// Use this node to replace the position of the node to be deleted
Node successor = new Node(minimum(node.right));
count++;
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
count--;
return successor;
}
}
}