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 socalled 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:

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

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:
 Traverse the binary tree and find the return with the same val value
 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
 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:

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;

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;

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)