❮ Merge Sort Heap Shift Down ❯

Binary Search Tree Node Deletion

Before discussing the deletion of nodes in a binary search tree, this section will first cover how to find the minimum and maximum values, as well as how to delete the minimum and maximum values.

Taking the minimum value as an example (the process for the maximum value is similar):

The logic for finding the minimum key value involves recursively searching down the left child node:

...
// Returns the node with 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 the binary search tree, if the node does not have a right subtree, it can be deleted directly. If a right subtree exists, as shown in the figure:

Deleting node 22, which has a right child, involves replacing node 22 with its right subtree node 33.

This process of deleting the minimum value is represented in code as:

...
// Deletes the node with the minimum key from the binary search tree rooted at node
// Returns the root of the new binary search tree after the 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, discussing the deletion of nodes in a binary search tree involves the following three cases:

1. Deleting a node with only a left child, such as node 58 in the diagram.

Deleting element 58 involves replacing it with its left subtree directly, maintaining the properties of the binary search tree.

2. Deleting a node with only a right child, such as node 58 in the diagram.

Deleting element 58 involves replacing it with its right subtree directly, maintaining the properties of the binary search tree.

3. Deleting a node with both left and right children, such as node 58 in the diagram.

(1) Find the minimum value in the right subtree, which is node 59.

(2) Replace the node to be deleted, node 58, with node 59.

Summarizing the above rules, the core code for deleting a node with a key value of key from a binary search tree rooted at node is as follows:

Source Code Download: Download

src/tutorialpro/binary/BSTRemove.java File Code:

package tutorialpro.binary;

import java.util.LinkedList;

/**
 * Binary Search Tree Node Deletion
 */
public class BSTRemove&lt;Key extends Comparable<Key>, Value>  {
    // Nodes in the tree are private classes, external parties do not need to know the specific implementation of binary search tree nodes
    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, default to 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);
}

// Check if the binary search tree contains the key
public boolean contain(Key key) {
    return contain(root, key);
}

// Search for the value corresponding to the key in the binary search tree. If the value does not exist, return 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<Node> q = new LinkedList<Node>();
    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);
    }
}

// Find the minimum key value in the binary search tree
public Key minimum() {
    assert count != 0;
    Node minNode = minimum(root);
    return minNode.key;
}

// Find the maximum key value in the binary search tree
public Key maximum() {
    assert count != 0;
    Node maxNode = maximum(root);
    return maxNode.key;
}

// Remove the node with the minimum value from the binary search tree
public void removeMin() {
    if (root != null)
        root = removeMin(root);
}

// Remove the node with the maximum value from the binary search tree
public void removeMax() {
    if (root != null)
        root = removeMax(root);
}

// Remove the node with the key value from the binary search tree
public void remove(Key key) {
    root = remove(root, key);
}

//********************
//* Helper functions for the binary search tree
//********************

// Insert a node (key, value) into the binary search tree rooted at node using a recursive algorithm
// Return 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) < 0)
        node.left = insert(node.left, key, value);
    else
        node.right = insert(node.right, key, value);
    return node;
}

node.left = insert(node.left, key, value);
else // key > node.key
    node.right = insert(node.right, key, value);

return node;
}

// Check if the binary search tree rooted at node contains a node with the 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) < 0)
        return contain(node.left, key);
    else // key > node.key
        return contain(node.right, key);
}

// Search for the value corresponding to the key in the binary search tree rooted at node, using a recursive algorithm
// If the value does not exist, return 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) < 0)
        return search(node.left, key);
    else // key > node.key
        return search(node.right, key);
}

// Perform a pre-order traversal of 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);
    }
}

// Perform an in-order traversal of 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);
    }
}

// Perform a post-order traversal of 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);
    }
}

// Return the node with 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);
}

// Return the node with 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);
}

// Remove the node with the minimum key from the binary search tree rooted at node
// Return the root of the new binary search tree after the node is removed

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;
}

// Remove the maximum node from the binary search tree rooted at node
// Return the root of the new binary search tree after the node is removed
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;
}

// Remove the node with key value 'key' from the binary search tree rooted at node, using a recursive algorithm
// Return the root of the new binary search tree after the node is removed
Node remove(Node node, Key key) {
    if (node == null)
        return null;

    if (key.compareTo(node.key) < 0) {
        node.left = remove(node.left, key);
        return node;
    } else if (key.compareTo(node.key) > 0) {
        node.right = remove(node.right, key);
        return node;
    } else { // key == node.key
        // Case where the left subtree of the node to be deleted is empty
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            count--;
            return rightNode;
        }

        // Case where the right subtree of the node to be deleted is empty
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            count--;
            return leftNode;
        }

        // Case where both left and right subtrees of the node to be deleted are non-empty
        // Find the smallest node larger than the node to be deleted, which is the minimum node in the right subtree
        // 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;
    }
}

❮ Merge Sort Heap Shift Down ❯