1. Concept
The binary search tree also becomes a binary sorting tree. It has the characteristic that if a node has two child nodes, it must be satisfied. The value of the left child node must be smaller than the value of the node, and the value of the right child node must be greater than the value of the node. For comparisons of non-basic types, the Comparator interface can be implemented. In this article, int type data is used for operation.
To implement a binary tree, you must start with its increase. Only by building the tree can you use other operations.
2. Construction of binary search tree
When talking about the increase of binary trees, we must first build a class representing a node. The class of the node has several attributes, the value of the node, the parent node, the left node, and the right node of the node. The code is as follows
static class Node{ Node parent; Node leftChild; Node rightChild; int val; public Node(Node parent, Node leftChild, Node rightChild,int val) { super(); this.parent = parent; this.leftChild = leftChild; this.rightChild = rightChild; this.val = val; } public Node(int val){ this(null,null,null,val); } public Node(Node node,int val){ this(node,null,null,val); } }Here we use the internal class writing method. After building the node value, we will build the entire tree. A tree must first have a root node, and then extend to the remaining child nodes. In this tree, there are also some attributes, such as the basic root node root, and the element size in the tree. If these two attributes are used, the Comparator attribute may be added, or a default implementation may be provided. The specific code is as follows
public class SearchBinaryTree { private Node root; private int size; public SearchBinaryTree() { super(); }}3. Add
When adding elements, you must consider the initialization of the root node. Generally, there are two types: when the constructor of this class is initialized, the root node root will be initialized. The second is to add the root node when the first element is added. Both of them work in theory, but usually use the second lazy loading form.
When adding elements, there are several situations that need to be considered
1. When adding, determine whether root is initialized. If it is not initialized, it will be initialized. Assign the value to the root node and add one size.
2. Because the binary tree search tree satisfies that the root node value is greater than the left node and smaller than the right node, the inserted value needs to be compared with the root node first. If it is large, search in the right subtree. If it is small, search in the left subtree. Until a child node.
The insertion implementation here can adopt two types: one, recursion, two, iterative (i.e. through while loop mode).
3.1. Recursive version insertion
public boolean add(int val){ if(root == null){ root = new Node(val); size++; return true; } Node node = getAdapterNode(root, val); Node newNode = new Node(val); if(node.val > val){ node.leftChild = newNode; newNode.parent = node; }else if(node.val < val){ node.rightChild = newNode; newNode.parent = node; }else{ // No processing for the time being} size++;19 return true; } /** * Get the parent node of the node to be inserted. The parent node satisfies one of the following states* 1. The parent node is a child node* 2. The value of the insertion node is smaller than the parent node, but the parent node does not have a left child node* 3. The value of the insertion node is larger than the parent node, but the parent node does not have a right child node* 4. The value of the insertion node is equal to the parent node. * 5. Parent node is empty* If one of the above 5 cases is satisfied, it will stop recursively. * @param node * @param val * @return */ private Node getAdapterNode(Node node,int val){ if(node == null){ return node; } // Insert into the left subtree but there is no left subtree, if(node.val > val && node.leftChild == null){ return node; } // Insert into the right subtree but there is no right subtree, also return if(node.val < val && node.rightChild == null){ return node; } // Insert into the right subtree but there is no right subtree, also return if(node.val < val && node.rightChild == null){ return node; } // Insert into the right subtree but there is no right subtree, also return if(node.val < val && node.rightChild == null){ return node; } // Insert into the right subtree but there is no right subtree, also return if(node.leftChild == null && node.rightChild == null){ return node; } if(node.val > val && node.leftChild != null){ return getAdaptarNode(node.leftChild, val); }else if(node.val < val && node.rightChild != null){ return getAdaptarNode(node.rightChild, val); }else{ return node; } }Use recursion, first find the end point of the recursion, and then turn the entire problem into a sub-problem. In the above code, the logic is roughly like this: first determine whether the root node is initialized, and if it is not initialized, it is initialized, and after completion, it returns, and then use a function to obtain the adapted node. Then insert the value.
3.2. Iterative version
public boolean put(int val){ return putVal(root,val); } private boolean putVal(Node node,int val){ if(node == null){// Initialize the root node node = new Node(val); root = node; size++; return true; } Node temp = node; Node p; int t; /** * Get the best node through do while loop iteration, */ do{ p = temp; t = temp.val-val; if(t > 0){ temp = temp.leftChild; }else if(t < 0){ temp = temp.rightChild; }else{ temp.val = val; return false; } }while(temp != null); Node newNode = new Node(p, val); if(t > 0){ p.leftChild = newNode; }else if(t < 0){ p.rightChild = newNode; } size++; return true; }The principle is actually the same as recursion, which is to obtain the best node and operate on that node.
In terms of performance, it is definitely the best iterative version, so in general, it is the iterative version to operate on the data.
4. Delete
It can be said that in the operation of the binary search tree, deletion is the most complicated, and there are relatively many situations to consider. In the conventional way, if you delete a node in the binary search tree, you will definitely think of the following four situations.
1. The node to be deleted has no left and right child nodes, as shown in the D, E, and G nodes in the figure above
2. The node to be deleted is only the left child node, such as Node B
3. The node to be deleted is only the right child node, such as the F node
4. The node to be deleted has both left child nodes and right child nodes, such as A and C nodes
For the first three situations, it can be said that it is relatively simple, while the fourth one is complicated. Let's analyze the first one
If this is the case, for example, if node D is deleted, the left child node of node B can be set to null, and if node G is deleted, the right child node of node F can be set to null. Which side should be set, and see which side the deleted node is located.
The second way to delete node B, you just need to set the left node of node A to node D and the parent node of node D to A. Which side is set depends on which side of the deleted node is located on the parent node.
The third type is the same as the second type.
The fourth type, which is a bit complicated as mentioned before, is for example, to delete the C node, set the parent node of the F node to node A, set the left node of the F node to node E, set the right node of A to node F, set the parent node of E to node F (that is, replace the F node C node), and there is another type, directly replace the E node C node. So which one should be used? If the delete node is the root node, how should I delete it?
For the fourth case, you can think of it like this: find the successor node of C or A node, delete the successor node, and set the value of the successor node to the value of C or A node. Let’s first supplement the concept of successor nodes.
The successor node of a node in the entire tree must be satisfied. The node with the smallest value in the set of nodes worth the node is the successor node. Of course, there may be no successor nodes.
However, for the fourth case, the successor node must exist and must be in its right subtree, and it also meets one of the cases where there is only one child node or no child node. The specific reason can be thought of this, because the successor node is larger than the C node, and because the left and right sub-sections of the C node must exist, it must exist in the left sub-section in the right sub-tree. For example, the successor node of C is F, and the successor node of A is E.
With the above analysis, the implementation is relatively simple, the code is as follows
public boolean delete(int val){ Node node = getNode(val); if(node == null){ return false; } Node parent = node.parent; Node leftChild = node.leftChild; Node rightChild = node.rightChild; //All the following parent nodes are empty, it means that the deleted node is the root node if(leftChild == null && rightChild == null){//No child nodes if(parent != null){ if(parent.leftChild == node){ parent.leftChild = null; }else if(parent.rightChild == node){ parent.rightChild = null; } }else{//The parent node does not exist, which means that the deleted node is the root node root = null; } node = null; return true; }else if(leftChild == null && rightChild != null){// Only the right node if(parent != null && parent.val > val){// There is a parent node, and the node position is the left side of the parent node parent.leftChild = rightChild; }else if(parent != null && parent.val < val){// There is a parent node, and the node position is the right side of the parent node parent.rightChild = rightChild; }else{ root = rightChild; } node = null; return true; }else if(leftChild != null && rightChild == null){// Only the left node if(parent != null && parent.val > val){// There is a parent node, and the node position is the left side of the parent node parent.leftChild = leftChild; }else if(parent != null && parent.val < val){// There is a parent node, and the node position is the right side of the parent node parent.rightChild = leftChild; }else{ root = leftChild; } return true; }else if(leftChild != null && rightChild != null){// Both child nodes have Node successor = getSuccessor(node);// In this case, there must be a successor node int temp = successor.val; boolean delete = delete(temp); if(delete){ node.val = temp; } successor = null; return true; } return false; } /** * Find the successor node of the node node* 1. First determine whether the node has a right subtree. If so, look for the successor node from the left subtree of the right node. If not, proceed to the next step* 2. Find the parent node of the node. If the right node of the parent node is equal to the node, continue to look for the parent node * until the parent node is Null or find the right node that is not equal to the node. * Reason, the successor node must be larger than the node. If there is a right subtree, the successor node must exist in the right subtree. This is the reason for the first step* If there is no right subtree, there may also be a grandfather node of the node (i.e. the parent node of the node, or the parent node above the parent node). * Iteratively search for it, if there is, it returns the node, and if there is no, it returns null * @param node * @return */ private Node getSuccessor(Node node){ if(node.rightChild != null){ Node rightChild = node.rightChild; while(rightChild.leftChild != null){ rightChild = rightChild.leftChild; } return rightChild; } Node parent = node.parent; while(parent != null && (node == parent.rightChild)){ node = parent; parent = parent.parent; } return parent; }For specific logic, please refer to the above analysis. I will not describe the text here.
In addition to this implementation, another implementation is provided in the introduction to the algorithm.
public boolean remove(int val){ Node node = getNode(val); if(node == null){ return false; } if(node.leftChild == null){// 1. The left node does not exist, the right node may exist, including two situations. Both nodes do not exist and only the right node exists transplant(node, node.rightChild); }else if(node.rightChild == null){//2. The left child exists, and the right node does not exist transplant(node, node.leftChild); }else{// 3. Both nodes have Node successor = getSuccessor(node);// Get the node successor node if(successor.parent != node){// The successor node exists in the right subtree of the node. transplant(successor, successor.rightChild);// Replace the successor with the right child node of the successor.rightChild = node.rightChild;// Assign the right child tree of the node node to the right node of the successor, that is, similar to the successor and the node node to the replacement position of successor.rightChild.parent = successor;// Then copy the parent reference of the received right node in the previous step} transplant(node, successor); successor.leftChild = node.leftChild; successor.leftChild.parent = successor; } return true; } /** * Replace child node with node node* @param root root node* @param node node to delete* @param child node child node child node child node child node child node child void transplant(Node node,Node child){ /** * 1. First determine whether the node has a parent node* 1. Does not exist, then replace child with root node* 2. If there is, then continue to the next step* 2. Determine that the node node is the child of the parent node (that is, determine whether the node is a right node or a left node), * After obtaining the result, replace the child node with node node, that is, if the node node is a left node, child will also be the left node after being replaced, otherwise it is the right node* 3. Set the parent node of the node node as the parent node of the child node*/ if(node.parent == null){ this.root = child; }else if(node.parent.leftChild == node){ node.parent.leftChild = child; }else if(node.parent.rightChild == node){ node.parent.rightChild = child; } if(child != null){ child.parent = node.parent; } }5. Search
Searching is also relatively simple, but in fact, it has been implemented when it is added. In actual situations, this part can be extracted from a separate method. The code is as follows
public Node getNode(int val){ Node temp = root; int t; do{ t = temp.val-val; if(t > 0){ temp = temp.leftChild; }else if(t < 0){ temp = temp.rightChild; }else{ return temp; } }while(temp != null); return null; }6. Binary search tree traversal
After understanding the properties of the binary search tree, it is clear that its intermediate order traversal is arranged in sequence from small to large. Here is the intermediate order traversal code provided here
public void print(){ print(root); } private void print(Node root){ if(root != null){ print(root.leftChild); System.out.println(root.val);// If the position is in the middle, then the order is in the middle. If it is in the front, it is in the precedent, otherwise it is a subsequent print(root.rightChild); } } Summarize
The above is the Java implementation of binary search tree function introduced by the editor. I hope it will be helpful to everyone. If you have any questions, please leave me a message. The editor will reply to everyone in time!