️ Preface ️

This article —— Binary search tree is both a pair of previous articles 【 Trees and binary trees 】 Some supplements to , Also for follow-up articles TreeMap and TreeSet Bedding of interface introduction .

Blog home page ：【 Warm the sun like the wind 】
The high-quality goods Java special column 【JavaSE】、【 Prepare for blue bridge 】、【JavaEE The first step 】、【MySQL】、【 data structure 】
Welcome to thumb up Collection Leave a comment Private letters must be answered

This paper is written by 【 Warm the sun like the wind 】 original , First appeared in CSDN

Bloggers will continue to update their learning records and gain , If you have any questions, you can leave a message in the comment area

The source code involved in the blog and the daily practice code of the blogger have been uploaded Code cloud (gitee)、GitHub

Here I would like to recommend some websites that bloggers often use to brush questions 【 Cattle from 】, The finger of the sword Offer The column is a high-frequency list of written interview questions , Let's brush it up ！

---

Binary search tree

1. Concept

Binary search tree is also called binary sort tree , It could be an empty tree , Or a binary tree with the following properties ：

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

As shown in the figure below, it is a binary search tree

First, complete the basic construction of binary search tree through code ：

public class BinarySearchTree {
    
    static class TreeNode {
    
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
    
            this.val = val;
        }
    }
    public TreeNode root;
}

2. Search operation

Find key values in the search tree , Because of the characteristics of binary search tree , So you can compare the key value with the root node value , If it is smaller than the root node , Go to the left sub tree to find , On the contrary, go to the right subtree to find .

	public TreeNode search(int key) {
    
        TreeNode cur=root;
        while (cur!=null) {
    
            if(cur.val<key) {
    
                cur=cur.right;
            }else if(cur.val>key) {
    
                cur=cur.left;
            }else {
    
                return cur;
            }
        }
        // If you go here, you won't find the keyword 
        return null;
    }

3. The insert

The insertion operation still follows the characteristics of binary search tree , Compare with the root node value , If it is smaller than it, insert it into the left subtree , If it is larger than it, insert it into the right subtree , You can find , Finally, they are inserted into the leaf node . Because the insertion operation requires that the previous node has a reference to the insertion node , So you need to use two nodes .

 	public boolean insert(int key) {
    
        TreeNode node=new TreeNode(key);
        // Empty tree direct insertion 
        if(root==null) {
    
            root=node;
            return true;
        }
        TreeNode cur=root;
        TreeNode parent=null;// Used to store the reference of the previous node 
        while (cur!=null) {
    
            if(cur.val<key) {
    
                parent=cur;
                cur=cur.right;
            }else if(cur.val>key) {
    
                parent=cur;
                cur=cur.left;
            }else {
    
                // There are the same elements   Cannot insert successfully 
                return false;
            }
        }
        // Code goes here ,cur==null, According to the previous node parent Of val Comparison , Determine whether to insert the left or right of the node 
        if(parent.val<key) {
    
            parent.right=node;
        }else {
    
            parent.left=node;
        }
        return true;
    }

4. Delete operation

The deletion of binary search tree is very complex , First, you need to find the node to delete , But this node may have left and right subtrees , So you can't just delete it , You need to determine the specific deletion method according to the situation , as follows ：

Set the node to be deleted as cur, The parent node of the node to be deleted is parent
1.cur.left == null

• cur yes root, be root = cur.right
• cur No root,cur yes parent.left, be parent.left = cur.right
• cur No root,cur yes parent.right, be parent.right = cur.right

2.cur.right == null

• cur yes root, be root = cur.left
• cur No root,cur yes parent.left, be parent.left = cur.left
• cur No root,cur yes parent.right, be parent.right = cur.left

3.cur.left != null && cur.right != null
You need to use substitution to delete , That is to say Find the minimum value in its right subtree （ It must have no left tree ）【 Or find the maximum value in its left subtree , It must have no right tree 】, Fill the deleted node with its value , Then deal with the deletion of this node （ Handle the node and the situation 1 identical , There is no left subtree ）

Code implementation ：

    /** *  Delete the keyword as key The node of  * @param key */
    public void remove(int key) {
    
        // Find the node first 
        TreeNode cur=root;
        TreeNode parent=null;
        while (cur!=null) {
    
            if(cur.val<key) {
    
                parent=cur;
                cur=cur.right;
            }else if(cur.val>key) {
    
                parent=cur;
                cur=cur.left;
            }else {
    
                // The code goes here to indicate that the node to be deleted is found 
                removeNode(cur,parent);
            }
        }
    }

    /** *  To delete  * @param cur  The node to be deleted  * @param parent  Delete the parent of the node  */
    private void removeNode(TreeNode cur,TreeNode parent) {
    
        if(cur.left==null) {
    
            if(cur==root) {
    
                root=root.right;
            }else if(cur==parent.left) {
    
                parent.left=cur.right;
            }else {
    
                parent.right=cur.right;
            }
        }else if(cur.right==null) {
    
            if(cur==root) {
    
                root=root.left;
            }else if(cur==parent.left) {
    
                parent.left=cur.left;
            }else {
    
                parent.right=cur.left;
            }
        }else {
    
            TreeNode targetParent=cur;// Record the previous node of the node used for replacement 
            TreeNode target=cur.right;// Record the nodes used for replacement 
            // Find the minimum value in the right subtree , Just go straight to the left , The node at the end is the minimum 
            while (target.left!=null) {
    
                targetParent=target;
                target=target.left;
            }
            // Find the node to replace , Complete replacement of values , Then deal with deleting the replacement node 
            cur.val=target.val;
            // At this time, the node must have no left subtree , The deletion method is the same as the previous one without left subtree 
            if(targetParent.left==target) {
    
                targetParent.left=target.right;
            }else {
    
                targetParent.right=target.right;
            }
        }
    }

5. Performance analysis

The insertion and deletion operations of binary search tree need progressiveness search , Search efficiency represents the performance of each operation in binary search tree , According to different insertion order , The resulting binary tree structure may also be different .
Best case ：
Get a complete binary tree
The time complexity of the search is O（$lo{g}_{2}N$）

Worst case scenario ：
Get a single branch tree
The time complexity of the search is O(N)

TreeMap and TreeSet ( These two interfaces are introduced in the following article ) namely java Using search tree to achieve Map and Set; In fact, it uses red and black trees , The red black tree is an approximately balanced binary search tree , That is, based on the binary search tree + Color and red black tree property verification , The content of red black tree will be explained later .

---

️ Last words ️
Summing up difficulties , hope uu Don't be stingy with your (＾Ｕ＾)ノ~ＹＯ！！ If there is a problem , Welcome comments and corrections in the comment area