Binary search tree node deletion

Before introducing deletion of nodes in a binary search tree, this section first explains how to find the minimum and maximum values, and how to delete the minimum and maximum values.

Taking the minimum value as an example (the maximum value is analogous):

Code logic for finding the minimum key value: recursively search down the left child node:

...
// 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);
}
...

To delete the minimum key value in a binary search tree, if the node has no right subtree, delete it directly; if a right subtree exists, as shown in the figure:

Deleting node 22: it has a right child, so just replace node 22 with node 33 from the right subtree.

This deletion of the minimum value is expressed in code:

...
// Remove the minimum node from the binary search tree rooted at node
// Return the root of the new binary search tree after removing the node
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 node deletion in a binary search tree, which falls into the following three cases:

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

Delete element 58, and let the left subtree directly take 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.

Delete element 58, and let the right subtree directly take 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 58 to be deleted.

Based on the above rules, the core code example for deleting the node with key value key in the binary search tree rooted at node is:

Source code package download:Download

src/example/binary/BSTRemove.java file code:

package example.binary;

import java.util.LinkedList;

/**
* Binary search tree node deletion
*/
public class BSTRemove<Key extends Comparable<Key>, Value> {
// The nodes in the tree are a private class; the outside world does not need to know the specific implementation of the 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, constructs an empty binary search tree by default
public BSTRemove() {
root = null;
count = 0;
}

// Return the number of nodes in the binary search tree
public int size() {
return count;
}

// Return whether the binary search tree is empty
public boolean isEmpty() {
return count == 0;
}

// Insert a new (key, value) data pair into the binary search tree
public void insert(Key key, Value value){
root = insert(root, key, value);
}

// Check whether the key exists in the binary search tree
public boolean contain(Key key){
return contain(root, key);
}

// Search the binary search tree for the value corresponding to the key. If the value does not exist, return null
public Value search(Key key){
return search( root , key );
}

// Preorder traversal of the binary search tree
public void preOrder(){
preOrder(root);
}

// Inorder traversal of the binary search tree
public void inOrder(){
inOrder(root);
}

// Postorder 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 in the binary search tree
public Key minimum(){
assert count != 0;
Node minNode = minimum( root );
return minNode.key;
}

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

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

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

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

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

// Insert node (key, value) into the binary search tree rooted at node, using 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 // key > node->key
node.right = insert( node.right, key, value);

return node;
}

// Check whether the binary search tree rooted at node contains a node with key value key, using 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 );
}

// Find the value corresponding to key in the binary search tree rooted at node, recursive algorithm
// Return NULL if the value does not exist
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 preorder traversal on the binary search tree rooted at node, recursive algorithm
private void preOrder(Node node){

if( node != null ){
System.out.println(node.key);
preOrder(node.left);
preOrder(node.right);
}
}

// Perform inorder traversal on the binary search tree rooted at node, recursive algorithm
private void inOrder(Node node){

if( node != null ){
inOrder(node.left);
System.out.println(node.key);
inOrder(node.right);
}
}

// Perform postorder traversal on the binary search tree rooted at node, 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 minimum node from the binary search tree rooted at node
// Return the root of the new binary search tree after removing the node
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 removing the node
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;
}

// Delete the node with key value key from the binary search tree rooted at node, recursive algorithm
// Return the root of the new binary search tree after removing the node
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

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

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

// The case where both the left and right subtrees of the node to be deleted are not empty

// Find the smallest node larger than the node to be deleted, i.e., the minimum node in the right subtree of the node to be deleted
// Replace the node to be deleted with this node
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;
}
}
}

other extensions