Pre knowledge of hash table -- binary search tree

Binary search tree

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

  

   

Code implementation

Node static inner class

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

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

---

Insert -- insert

    public boolean insert(int key) {
        if(this.root == null) {
            this.root = new TreeNode(key);
            return true;
        }
        TreeNode cur = this.root;
        TreeNode parent = null;
        // Find the inserted father 
        while(cur != null) {
            if(cur.key < key) {
                parent = cur;
                cur = cur.right;// Go to the right 
            } else if(cur.key > key) {
                parent = cur;
                cur = cur.left;// Go to the left 
            } else {
                // Cannot insert the same element 
                return false;
            }
        }
        TreeNode node = new TreeNode(key);
        if(key > parent.key) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        return true;
    }

The illustration

---

   lookup -- search

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

The lookup function is relatively simple , It's a binary search .

---

Delete -- remove （ difficulty ）

    public boolean remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            if(cur.key > key) {
                parent = cur;
                cur = cur.left;
            } else if(cur.key < key) {
                parent = cur;
                cur = cur.right;
            } else {
                removeNode(parent, cur);
                return true;
            }
        }
        return false;
    }
    private void removeNode(TreeNode parent, TreeNode cur) {
        //1. Left is empty  2. Right is empty.  3. It's not empty. 
        if(cur.left == null) {
            if(cur == root)  {
                root = cur.right;
            } else if(cur == parent.right) {
                parent.right = cur.right;
            } else {
                parent.left = cur.right;
            }
        } else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }else if(cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {
            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            // You can find a maximum value in the left subtree of the node to be deleted to overwrite it , You can also find a minimum value in the right subtree of the node to be deleted to overwrite it , Finally, remove the scapegoat 
            while(target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.key = target.key;
            // The scapegoat for judgment is targetParent The left child is still the right child 
            if(target == targetParent.left) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }

Ideas

Discussion by situation ： Set the node to be deleted as cur , The node to be deleted is parent .

1.cur.left == null

• cur == root
• cur == parent.left
• ccur == parent.right

2.cur.right == null

• cur == root
• cur == parent.left;
• cur == parent.right

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

• Substitution method （ difficulty ）

Draw pictures to explain the substitution method ！

Case two is similar to case one

  Substitution method

  Substitution analysis

When the band deletes the element key When there are children around , Put... Directly key It is unrealistic to delete , Because you don't know key What is the following structure , Even if you know , There is no way to adjust it , So we need to use the substitution method to realize , Either way key Replace with the maximum value in the left subtree of , You can also choose key Replace with the lowest value in the right subtree of , Because only in this way can we ensure that the structure of the binary search tree is not destroyed .

---

Check insertion / Is it still a binary search tree after deletion -- In the sequence traversal

In the following figure, the result of sequence traversal is ：0,1,2,3,4,5,6,7,8,9

  Code implementation

    public List<Integer> inOrder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        List<Integer> left = inOrder(root.left);
        list.addAll(left);// Left 
        list.add(root.key);// in 
        List<Integer> right = inOrder(root.right);
        list.addAll(right);// Right 
        return list;
    }

We are doing a binary search tree CURD In operation , You can determine whether it is correct by calling the debugging and printing of the sequence traversal ！

That's all for this blog , See you next time ！！！