[template summary] - binary search tree BST - Basics

Template Title Links

• BST lookup - Leetcode 270. Closest BST Value
• BST Insert - Leetcode 701. Insert Node in BST
• BST Delete - Leetcode 450. Delete Node in BST

Binary search tree -BST summary

BST It's a kind of binary tree , It has the structural properties of binary tree ： only one Root node , Each node can have at most two child nodes .BST The nature of itself ： The value of the left son of each node must be smaller than him , The value of the right son must be higher than him . This property also makes BST The output result of the middle order traversal of is a strictly increasing sequence . Strictly speaking ,BST Elements with the same value are not saved in , If there are duplicate elements, you can add them at each node count Property to count .

BST Basic inquiry template

• Find an element

according to BST Size relationship between left and right child nodes , You can directly use dichotomy for numerical queries , If the current value is smaller than the search value , Then look to the left , On the contrary, look to the right .

The code is as follows ：

class Solution {
    double min = Double.MAX_VALUE;
    int res = -1;
    public int closestValue(TreeNode root, double target) {
        search(root, target);
        return res;
    }
    
    private void search(TreeNode root, double target) {
        // > target The first number of 
        if(root==null) return;
        
        if(Math.abs(root.val-target)<min) {
            min = Math.abs(root.val-target);
            res = root.val;
        }
        
        if(root.val>target) search(root.left, target);
        search(root.right, target);
        
        
    }

}

Time complexity ：,  If BST The structure is relatively balanced ( Maximum height difference <=1) That is, balance BST Under the circumstances , The worst case scenario is possible BST The structure is very unbalanced , That is, all nodes form a similar linked list structure , At this time, the time will be ; Spatial complexity ： That is, the depth of recursion . 

•    BST Insert node

The idea of inserting nodes is easy to understand , We first find the position of leaf nodes where the values to be inserted can be inserted according to the size relationship , And establish new nodes and BST Just connect it

Insert footprint , source ： Leetcode Solution

 

The code is as follows ： 

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode res = insert(root, val);
        return res;
    }
    
    private TreeNode insert(TreeNode root, int val){
        //  Divide and conquer 
        if(root==null) return new TreeNode(val);
        
        if(root.val<val) root.right = insert(root.right, val);
        else if(root.val>val) root.left = insert(root.left, val);
        
        return root;
    }
}

• Delete node  

Deleting a node is the most complicated of the basic queries , Because when deleting an element , For maintenance BST Ordered property of , You need to find a node to replace the location of the deleted node , And ensure that it will still be BST.

When deleting nodes again , There are three possibilities ：

1. The deleted node is a leaf node ： In this case, delete the node directly
2. Deleting a node only has left or right sons ： In this case, directly connect the left or right son of the deleted node
3. Deleting a node has left and right sons ： This situation is the most complicated , These two kinds of nodes are usually used as replacement nodes : The largest point in the left subtree , perhaps The smallest point in the right subtree -  That is, delete the point Forerunner (predecessor) and The subsequent nodes (successor). These two points are usually leaf nodes or only left or right sons ( Because they are the leftmost and right nodes on the subtree )  So replace the node to the position where the node is deleted , Directly connect its left or right subtree ( If any ).
   1. The largest point of the left subtree ： That is, the rightmost point of the left subtree
   2. The smallest point of the right subtree ： That is, the leftmost point of the right subtree

Schematic diagram of subsequent node replacement ： source -  Leetcode Solution

 

Schematic diagram of precursor node replacement ： source -  Leetcode Solution

The code is as follows ：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode res = delete(root, key);
        
        return res;
    }
    
    private TreeNode delete(TreeNode root, int key) {
        if(root==null) return null;
        
        if(root.val<key) root.right = delete(root.right, key);
        else if(root.val>key) root.left = delete(root.left, key);
        else {
            // if root is leaf, directly remove
            if(root.left==null && root.right==null) {
                return null;
            } else if(root.left!=null && root.right!=null) {
                // find predecessor or successor to replace remove node
                // predecessor -  The maximum on the left 
                TreeNode left = root.left;
                if(left.right==null) {
                    // no right node current node is predecessor
                    root.val = left.val;
                    root.left = left.left;
                } else {
                    //  To the right, find the rightmost, that is, the largest node and the largest node parent
                    //  Here we use a fast and slow needle to find the corresponding position 
                    TreeNode fast = left.right;
                    TreeNode slow = left;
                    
                    while(fast.right!=null) {
                        fast = fast.right;
                        slow = slow.right;
                    }
                    // fast  Find the far right ,slow Is the previous node 
                    root.val = fast.val;
                    slow.right = fast.left; // remove predecessor
                    
                }
                return root;
                
            } else {
                // one side is not leaf
                if(root.left!=null) return root.left;
                if(root.right!=null) return root.right;
            }
        }
        
        return root;
    }
}

Time complexity ： If it is balance BST So that is , The worst ：; Spatial complexity ：  Recursion depth .