lead

This paper mainly introduces how to realize the insertion, search and deletion of binary search tree~

What is a binary search tree?

Binary search tree, also known as binary sort tree, has the following properties:

• If its left subtree is not empty, the values of all nodes on the left subtree are less than the values of the root node
• If its right subtree is not empty, the value of all nodes on the right subtree is greater than the value of the root node
• Its left and right subtrees should also meet the properties of binary search tree
• The middle order traversal result of binary search tree is ordered

The following figure shows a binary search tree:

Insert operation

The so-called increase is actually to insert a node into the binary tree. The problem is how to insert it and where to insert it?

Basic idea:

1. First, the node to be inserted must be a leaf node, so find the leaf node first

2. After finding the leaf node, it is necessary to determine whether to insert to the left or right of the node

There is another case we need to consider here, that is, if the value you want to insert exists in the current binary search tree, then it is judged as insertion failure Because binary search tree cannot have two nodes with the same node value~

code

public boolean insert(int val) {
    TreeNode node = new TreeNode(val);
    if (this.root == null) {
        this.root = node;
        return true;
    }
    TreeNode cur = root;
    // Define a parent node and record the previous node of cur
    TreeNode parent = null;
    while (cur != null) {
        if (val < cur.val) {
            parent = cur;
            cur = cur.left;
        } else if (val > cur.val) {
            parent = cur;
            cur = cur.right;
        } else {
            return false;
        }
    }
    // At this time, cur is empty, indicating that the parent at this time is a leaf node
    if(parent.val < val) {
        parent.right = node;
    }else {
        parent.left = node;
    }
    return true;
}

Find operation

Idea:

1. Traverse the binary tree and find the return with the same val value
2. If the val value to be searched is smaller than the val value of the current node, go left, and if it is larger than the val value of the current node, go right
3. If it is not found after traversal, null will be returned

code

public TreeNode search(int val) {
    TreeNode cur = root;
    while (cur != null) {
        if (val < cur.val) {
            cur = cur.left;
        } else if (val > cur.val) {
            cur = cur.right;
        } else {
            return cur;
        }
    }
    return null;
}

Delete operation

Deletion is the most tedious operation in insertion, search and deletion, because you should ensure that the whole tree is still a binary search tree after deleting the target node Therefore, in general, we can consider three cases here ~ suppose that the node to be deleted is cur, and the parent node of the node to be deleted is parent

analysis:

1. cur.left == null

   

   There are three situations:

   • Cur is the root node, then root = = cur right
   • Cur is not the root node, cur = = parent Left, at this time, parent left = cur. right;
   • Cur is not the root node, cur = = parent Right, at this time, parent right = cur. right;

2. cur.right == null

   

   At this time, there are also three situations:

   • Cur is the root node, then root = = cur left
   • Cur is not the root node, cur = = parent Left, at this time, parent left = cur. right;
   • Cur is not the root node, cur = = parent Right, at this time, parent right = cur. right;

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

   

   In this case, you need to use the replacement method to delete. In essence, it is to convert the case that the left and right are empty into the above two cases

   • In the right subtree with deleted nodes, find the node with the smallest val value of the node under the middle order traversal, and fill its value to the deleted node
   • Or find the node with the largest val value of the node under the middle order traversal in its left subtree, and fill its value to the deleted node
   • Finally, delete the node with the largest (or smallest) val value, and convert it to the case of 1 and 2

code

public boolean delete(int val) {
    TreeNode cur = root;
    TreeNode parent = null;
    while (cur != null) {
        if (val < cur.val) {
            parent = cur;
            cur = cur.left;
        } else if (val > cur.val) {
            parent = cur;
            cur = cur.right;
        } else {
            // Find the node to be deleted and delete it
            deleteNode(cur, parent);
            return true;
        }
    }
    return false;
}

private void deleteNode(TreeNode cur, TreeNode parent) {
    // There are three situations:
    // 1.cur.left == null
    // 2.cur.right == null
    // 3.cur.left != null && cur.right != null
    if (cur.left == null) {
        // 1.cur.left == null
        if (cur == root) {
            root = cur.right;
        } else if (cur == parent.left) {
            parent.left = cur.right;
        } else {
            parent.right = cur.right;
        }
    } else if (cur.right == null) {
        // 2.cur.right == null
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
    } else {
        // 3.cur.left != null && cur.right != null
        TreeNode targetParent = cur;
        // The method here is to find the minimum value on the right tree of the node to be deleted, and then replace it
        TreeNode target = cur.right;
        while (target.left != null) {
            // Record the parent node of target
            targetParent = target;
            // Go straight to the left to find the minimum value~
            target = target.left;
        }
        // Overwrite the val of the node to be deleted
        cur.val = target.val;
        // Delete minimum node
        if (target == targetParent.left) {
            targetParent.left = target.right;
        } else {
            targetParent.right = target.right;
        }   
    }
}

Time complexity analysis

Best case: the binary search tree at this time is a complete binary tree, and its time complexity is O(logN)

Worst case: at this time, the binary search tree degenerates into a tree with branches, and its time complexity is O(N)