Deleting nodes in binary search tree

The deletion of binary search tree is cumbersome , But calm down and believe that it will soon be absorbed ！ It is mainly divided into two steps ： First, find the node to be deleted , Then delete this node .

We use it cur Variable search , use parent Variable representation curr The parent node of

Search for nodes to be deleted

Search is not the focus of this article , Let's go straight to the code

public boolean delete(int key) {
    
        // wirte code here, There are mainly three situations 
        Node parent = null;
        Node cur = root;//cur Be responsible for finding the node that needs to be deleted 
        while (cur != null) {
    
            if (cur.key < key) {
    
                parent = cur;
                cur = cur.right;
            } else if (cur.key > key) {
    
                parent = cur;
                cur = cur.left;
            } else {
    
            	//△ Come here , We found the node to be deleted , namely cur
                deleteNode(parent, cur);
                //deleteNode The way is to delete cur node 
                return true;
            }
        }
        return false;
    }

Be careful ： To the code above triangle It's about , We The node to be deleted is found cur

Text ( Delete cur node )

We have three situations ：(cur The node is the node to be deleted ,parent yes cur The parent node of , It will not be repeated below )

1. cur.left = null;
2. cur.right = null;
3. cur.left != null && cur.right != null;

situation 1：cur.left = null

This time, the situation is divided into 3 In this case

1. cur yes The root node
2. cur yes parent The left child
3. cur yes parent The right child

① cur Root node

In this case , Let's go straight to root = root.right that will do

② cur by parent The left child

Pictured , We let parent.left = cur.right that will do

③ cur by parent The right child

Pictured , We let parent.right = cur.right that will do

situation 2：cur.right = null

• situation 2 And circumstances 1 The idea is basically the same , Let's repeat and consolidate

1. cur yes The root node
2. cur yes parent The left child
3. cur yes parent The right child

① cur Root node

Empathy , just root = root.left that will do

② cur by parent The left child

Pictured , We let parent.left = cur.left

③ cur by parent The right child

Pictured , We let parent.right = cur.left

situation 3：cur.left != null && cur.right != null

The core idea ： stay cur Find the node with the lowest value in the right subtree of , Then assign the node value to cur , Then delete the smallest node

• So there are two steps ：① look for cur Right subtree minimum node , And assign the minimum value to cur ② Delete the smallest node

step ①

First define target = cur.right, let targetParent by target The parent node of
Final ： Give Way target Point to cur The smallest node of the right subtree , Give Way targetParent Point to target My parents

following ↓ The code is to make target Point to cur Right subtree The minimum node

	Node target = cur.right;// find cur The smallest node in the right subtree , Replace cur node , And delete the smallest node 
	Node targetParent = cur; //target Parent node of node 
	while (target.left != null) {
      // Find the smallest node of the right subtree 
	    targetParent = target;
	    target = target.left;
	}

And then assign a value ：cur.key = target.key;, Pictured

step ②

Here we are , Our task is to delete target The node , At this time, it can be divided into two situations , It's also easier to understand

1. target == targetParent.left
2. tartget == targetParent.right

situation 1 ： Only targetParent.left = target.right

situation 2： Only targetParent.right = target.right

complete ！

Delete cur Node code

private void deleteNode(Node parent, Node cur) {
    
        // thus ,cur Point to the node to be deleted 
        if (cur.left == null) {
      // situation 1, If the left child is empty 
            if (cur == root) {
    
                root = cur.right;
            } else if (parent.left == cur) {
    
                parent.left = cur.right;
            } else {
    
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
      // situation 2, If the right child is empty 
            if (cur == root) {
    
                root = cur.left;
            } else if (parent.left == cur) {
    
                parent.left = cur.left;
            } else {
    
                parent.right = cur.left;
            }
        } else {
      // situation 3, If the left and right children are not empty 
            Node target = cur.right;// find cur The smallest node in the right subtree , Replace cur Node values , And delete the smallest node 
            Node targetParent = cur; //target Parent node of node 
            while (target.left != null) {
      // Find the smallest node of the right subtree 
                targetParent = target;
                target = target.left;
            }
            cur.key = target.key; // Cover cur value 

            if (target == targetParent.left) {
    
                targetParent.left = target.right;
            } else {
    
                targetParent.right = target.right;
            }
        }
    }

Full code

public boolean delete(int key) {
    
        // wirte code here, There are mainly three situations 
        Node parent = null;
        Node cur = root;//cur Be responsible for finding the node that needs to be deleted 
        while (cur != null) {
    
            if (cur.key < key) {
    
                parent = cur;
                cur = cur.right;
            } else if (cur.key > key) {
    
                parent = cur;
                cur = cur.left;
            } else {
    
                deleteNode(parent, cur);
                return true;
            }
        }
        return false;
    }

    private void deleteNode(Node parent, Node cur) {
    
        // thus ,cur Point to the node to be deleted 
        if (cur.left == null) {
      // If the left child is empty 
            if (cur == root) {
    
                root = cur.right;
            } else if (parent.left == cur) {
    
                parent.left = cur.right;
            } else {
    
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
      // If the right child is empty 
            if (cur == root) {
    
                root = cur.left;
            } else if (parent.left == cur) {
    
                parent.left = cur.left;
            } else {
    
                parent.right = cur.left;
            }
        } else {
      // If the left and right children are not empty 
            Node target = cur.right;// find cur The smallest node in the right subtree , Replace cur node , And delete the smallest node 
            Node targetParent = cur; //target Parent node of node 
            while (target.left != null) {
      // Find the smallest node of the right subtree 
                targetParent = target;
                target = target.left;
            }
            cur.key = target.key; // Cover 

            if (target == targetParent.left) {
    
                targetParent.left = target.right;
            } else {
    
                targetParent.right = target.right;
            }
        }
    }