Red black tree is a very important data structure. We can often see it in development, such as TreeMap in JDK, TreeSet and HashMap in JDK8. Red black tree is used in their underlying implementation. In order to master this data structure, we decided to start from binary sorting tree, and then gradually derive to AVL tree, 23 tree, and finally to red black tree. This is the first part of this series: binary sorting tree.

Binary Sort Tree (BST) is also called binary search tree. It is either an empty tree or a binary tree with the following properties: for a node,
 If its left subtree is not empty, the values of all nodes on the left subtree are smaller than its own values;
 If its right subtree is not empty, the value of all nodes on the right subtree is greater than its own value;
 Its left and right subtrees are also binary sorting trees.
As you can see, it is defined recursively.
/ / Map
As shown above, this tree is a binary sorting tree. The value of the root node is 62. It can be seen that the node values of the left subtree of the root node are smaller than 62, and the node values of the right subtree are larger than 62. Similarly, for 58, 88 All of them satisfy this property.

Why binary sort tree is needed
The purpose of building a binary sort tree is not to sort, but to improve the efficiency of searching, inserting and deleting. Binary search tree is actually a combination of the flexibility of inserting linked list and the efficiency of searching ordered array. For searching ordered array, we all know that there is binary search, and the search of binary sort tree and binary search have the same magic.

Add binary sort tree:
public class BST { private Node root; public void add(int val) { Node node = new Node(val); if (root == null) { root = node; } else { root.add(node); } } public void infixOrder() { if (root != null) { root.infixOrder(); } } static class Node { private int val; private Node left, right; public Node(int val) { this.val = val; } @Override public String toString() { return "Node{" + "val=" + val + '}'; } public Node getLeft() { return left; } public Node getRight() { return right; } private void add(Node node) { // If the value of the node to be inserted is smaller than that of the current node, the node needs to be placed in the left subtree of the current node if (node.val < this.val) { // If the left sub node of the current node already exists, add it along the sub tree whose left sub node is the root node if (this.left != null) { this.left.add(node); } else { this.left = node; } } else { // Similarly, when the value of the node to be inserted is greater than the value of the current node, place it to the right if (this.right != null) { this.right.add(node); } else { this.right = node; } } } // Sequential traversal private void infixOrder() { if (this.left != null) { this.left.infixOrder(); } System.out.println(this); if (this.right != null) { right.infixOrder(); } } } } public class Test { public static void main(String[] args) { BST bst = new BST(); int[] arr = {7, 3, 10, 12, 5, 1, 9, 2}; for (int value : arr) { bst.add(value); } bst.infixOrder(); } }

Class Node:
A Node object represents a Node in the tree, where infixOrder() implements the middle order traversal of the tree through recursion. The key is to understand the add method. The comments in the code have explained the logic. Now we analyze the add operation in the Test class Test and draw the formation process of this binary search tree step by step:
 "7": if the root node is empty, 7 will be taken as the root node directly
/ / Map
 "3": smaller than 7, and the left child node of "7" is empty, then "3" is directly regarded as the left child node of "7"
/ / Map
 "10": larger than 7, and the right child of "7" node is empty, then "10" is directly regarded as the right child of "7"
/ / Map
 "12": larger than 7, and the right sub node of "7" is not empty at this time. Then proceed from the right sub node 10, and continue to compare. Since 12 is larger than 10, and the right sub node of 10 is empty, then directly regard 12 as the right sub node of 10
/ / Map
By analogy, a tree is finally formed:
/ / Map
The results of middle order traversal of this tree are as follows:
/ / Map
It can be seen that the results are already in the order of small to large.


Search of binary sort tree
As we mentioned earlier, the purpose of building a binary sort tree is not to sort, but to improve the efficiency of search and deletion. Let's implement search.
In the BST class, add:
public Node search(int val) { if (root != null) { return root.search(val); } return null; }
Add in the Node class:
private Node search(int val) { if (val == this.val) { return this; } if (val < this.val) { if (this.left != null) { return this.left.search(val); } } else { if (this.right != null) { return this.right.search(val); } } return null; }
Let's test a wave of search methods:
public static void main(String[] args) { BST bst = new BST(); int[] arr = {7, 3, 10, 12, 5, 1, 9, 2}; for (int value : arr) { bst.add(value); } bst.infixOrder(); System.out.println(""); BST.Node node = bst.search(10); System.out.println("left = " + node.getLeft() + ", right = " + node.getRight()); }
The output results are as follows:
/ / Map

Deletion of binary search tree
Analysis:
 If the leaf node is deleted, it is very simple. We just need to set its parent node left or right to null.
 If the node to be deleted has only left sub tree: if the node to be deleted (targetNode) is the left sub node of its parent node, that is, parentNode.left == targetNode, then we need to set parentNode.left = targetNode.left; If the node to be deleted is the right child of its parent node, i.e. parentNode.right == targetNode, then we need to set parentNode.right = target.left.
 If the node to be deleted has only the right subtree: the same as the left subtree, you only need to change targetNode.left to targetNode.right
 If the node to be deleted has left and right subtrees at the same time: in this case, there are two strategies
 Find the node corresponding to the maximum value in the left subtree, replace the value of the node to be deleted with the maximum value, and delete the original node corresponding to the maximum value
 Find the node corresponding to the minimum value in the right subtree, replace the value of the node to be deleted with the minimum value, and delete the original node corresponding to the minimum value
From the above analysis, we can see that it is necessary to know the parent Node of a Node, so we first add the searchParent method to the Node class:
private Node searchParent(int val) { // Parent found if ((this.left != null && this.left.val == val)  (this.right != null && this.right.val == val)) { return this; } if (val < this.val) { if (this.left != null) { return this.left.searchParent(val); } } else { if (this.right != null) { return this.right.searchParent(val); } } return null; }
Add the delete method to the BST class:
public void delete(int val) { if (root == null) { return; } Node targetNode = search(val); if (targetNode == null) { return; } Node parentNode = searchParent(targetNode.val); // The current binary sort tree has only one root node if (root.left == null && root.right == null) { root = null; } else { // If the node to be deleted is a leaf node if (targetNode.left == null && targetNode.right == null) { // The node to be deleted is the left child of the parent node if (parentNode.left == targetNode) { parentNode.left = null; } // The node to be deleted is the right child of the parent node if (parentNode.right == targetNode) { parentNode.right = null; } } // If the node to be deleted has two subtrees else if (targetNode.left != null && targetNode.right != null) { // Maximum value of left subtree or minimum value of right subtree targetNode.val = delRightSubMin(targetNode.right); } else { // Left subtree only if (targetNode.left != null) { if (parentNode == null) { root = targetNode.left; return; } if (targetNode == parentNode.left) { parentNode.left = targetNode.left; } else if (targetNode == parentNode.right) { parentNode.right = targetNode.left; } } else { if (parentNode == null) { root = targetNode.right; return; } if (targetNode == parentNode.left) { parentNode.left = targetNode.right; } else if (targetNode == parentNode.right) { parentNode.right = targetNode.right; } } } } } public int delRightSubMin(Node node) { Node tmpNode = node; while (tmpNode.right != null) { tmpNode = tmpNode.right; } delete(tmpNode.val); return tmpNode.val; } public Node searchParent(int value) { if (root == null) { return null; } return root.searchParent(value); }

summary
The advantage of binary search tree is efficient search and deletion. In a sense, the efficiency of deletion is also due to the efficiency of search, because we need to quickly locate the elements to be deleted. How many searches does it take to locate the specified element in the worst case (that is, at most)? It is not difficult to analyze. In the worst case, the element is the leaf node. In this case, the number of searches is actually related to the height of the binary tree.