Detailed analysis of binary search tree data structure implementation process (Java implementation)
These reviews
- Detailed analysis of dynamic array data structure implementation process (Java implementation)
- Detailed analysis of stack and queue data structure implementation process (Java implementation)
- Detailed analysis of linked list data structure implementation process (Java implementation)
- Detailed analysis of recursion properties in linked lists (Java implementation)
Introduction to Tree Structure
- In linear data structures, data is stored in a row. A tree structure is non-linear, storing data in a structure organized by branching relationships, just like a tree in nature. As shown below:
- It can be seen from the figure that the tree structure has a sense of hierarchy, and each point can have multiple branches. This organizational structure is very advantageous. Simply speaking, the tree structure itself is a natural organizational structure.
- This kind of organization structure is very common in daily life, such as folders on computer disks, organizational structure of people in companies, family tree, etc., as shown in the following figures:
- In addition to organizing data, using a tree structure to store data can be very efficient in some cases. We can design efficient tree structures suitable for various special situations.
- For example, to find a piece of data, if you don’t know the specific location in a linear structure, you need to find it one by one in a pile of data; As for the tree structure, because of the branch form of the tree structure, each data can be stored in different branches. When searching, we can quickly find the data we want according to these branches.
- For example, different folders on the disk store different files. When we are looking for a file, we can find the file we want according to the folder name.
- The above is a simple introduction of some characteristics of the tree structure, and then began to analyze the basic knowledge of binary search tree in the tree structure and some common operations to achieve this data structure.
The basics of binary search trees
Basic concepts of binary trees
- Before you understand binary search trees, you need to understand the basic concepts of binary search trees, because binary search trees are based on binary trees. In fact, binary tree is the most common tree structure and the most basic structure in tree structure.
- Binary trees, like linked lists, are dynamic data structures. Users do not need to worry about capacity, and designers do not need to manually design a way to scale capacity dynamically.
- At the same time, the binary tree is also composed of one node at a time, and for each node, in addition to storing data, there need to be two child nodes, pointing to the left node and the right node of the node (also known as the left child and the right child).
- In addition, binary trees also have the following characteristics:
- A binary tree has a unique root node.
- A binary tree has a maximum of two children per node.
- Nodes in a binary tree that have no children are called leaf nodes.
- Each node in a binary tree has at most one parent node.
- Binary trees have a natural recursive structure:
- The left subtree of each node is also a binary tree. (The left node of each node is the root node of the left subtree)
- The right subtree of each node is also a binary tree. (The right node of each node is the root node of the right subtree)
- Binary trees are not necessarily full:
- A node is also a binary tree. (Left and right children are empty)
- NULL is also a binary tree.
- The above features can be summarized as follows:
- Some common forms of binary trees
- An empty binary tree
Basic concept of binary search tree
- After understanding the above basic concepts of binary tree, then for binary search tree do not need to understand the above concepts, because a binary search tree is a binary tree, but it has some of its own characteristics.
- For binary search trees, it has the following properties:
- The value of each node in a binary search tree is greater than the value of all nodes in its left subtree.
- The value of each node in a binary search tree is less than the value of all nodes in its right subtree.
- Each subtree of a binary search tree is also a binary search tree.
- Binary search trees must store elements that are comparable.
- Binary search tree icon
Binary search tree basic structure code implementation
-
To sum up the above basic concepts, the code for the basic structure of binary search tree can be designed as follows:
/** * Binary search tree data structure implementation class * support comparability generics **@authorSnow's looking for mei *@date2020/3/2-23:05 * / public class BST<E extends Comparable<E>> { /** * binary search tree node */ private class Node { /** * The element stored in the node */ public E element; /** * left node (left child) */ public Node left; /** * Right node (right child) */ public Node right; /** * The node class constructor constructs a node with no left or right children@paramElement The element stored in a node */ public Node(E element) { this.element = element; this.left = null; this.right = null; }}/** * Binary search tree root */ private Node root; /** * Number of nodes in binary search tree */ private int size; The binary search tree class constructor constructs an empty binary search tree */ public BST(a) { this.root = null; this.size = 0; } /** * Get the number of nodes in the binary search tree *@returnReturns the number of nodes in the current binary search tree */ public int size(a) { return size; } /** * Check whether the current binary search tree is empty *@returnReturns true, indicating that the current binary search tree is empty. Returns false to indicate that the current binary search tree is not empty */ public boolean isEmpty(a) { // Check whether size is 0 return size == 0; }}Copy the code
Binary search tree common basic operation implementation
Add operation
Add operation preliminary implementation
-
The operation of adding binary search tree can be divided into the following two situations (the GIF is used here for simplicity) :
- Add a new element to an empty tree:
- Add a new element to the tree when it already exists:
- Add a new element to an empty tree:
-
This is the process of adding elements. Note that in the binary search tree implementation, there are no duplicate elements. If the added element already exists, it will be ignored.
-
If duplicate elements are required, the left subtree is less than or equal to the parent node, and the right subtree is greater than or equal to the parent node.
-
The code implementation can be either non-recursive or recursive, and for non-recursive, the implementation steps are actually more like a linked list; But in a tree structure, recursive implementation is easier than non-recursive, so we use recursive implementation here.
-
But there are limits to using recursion. For example, in the worst case of adding elements, the binary search tree will form a linked list (only adding left or right nodes). In this case, if you keep adding elements, the recursion will get higher and higher, and the memory will burst. This is also important to understand.
-
From the above diagram, the following steps can be summarized (recursive implementation) :
- Before adding elements, check whether the current binary search tree is empty. If empty, add the element to the root node; If not empty, the element is added recursively to the tree, starting at the root node.
- Recursive termination condition:
- The added element is already in the tree. (Contains no duplicate elements)
- If the added element is added to the left node of a node and the left node of the current node is empty, the element is added to the left node of the current node and returned.
- If the added element is added to the right node of a node and the right node of the current node is empty, the element is added to the right node of the current node and returned.
- If the above termination conditions are not met, recursively add elements:
- If the added element is smaller than the element of the current node, it is added to the left subtree of the current node.
- If the added element is larger than the element of the current node, add it to the right subtree of the current node.
-
The above steps are realized in code form as follows:
/** * add a new element element * to the binary search tree@paramElement adds a new element */ public void add(E element) { // Determine whether the binary search tree is empty if (root == null) { // If the binary search tree is empty, add the new element to the root node root = new Node(element); size++; } else { // The binary search tree is not empty, and new elements are added recursively from the root nodeadd(root, element); }}/** * Adds element element * recursive function * to binary search tree whose root node is node@paramNode adds the root node * of the binary search tree for the element@paramElement The added element */ private void add(Node node, E element) { // Termination conditions if (node.element.equals(element)) { // The added element already exists return; } else if (element.compareTo(node.element) < 0 && node.left == null) { // When the element is added to the left node of a node (the left node of the node is empty) node.left = new Node(element); size++; return; } else if (element.compareTo(node.element) > 0 && node.right == null) { // When the added element is added to the right node of a node (the right node of the node is empty) node.right = new Node(element); size++; return; } // Add elements recursively if the terminating condition is not met if (element.compareTo(node.element) < 0) { // Smaller than the current node, added to the left subtree add(node.left, element); } else { // It is larger than the current node and added to the right subtreeadd(node.right, element); }}Copy the code
Add operational improvements
- In the above implementation of the add operation, there are two rounds of comparison when adding new elements, the first round is for the termination condition and the second round is for the termination condition that is not met, which makes the termination condition seem bloated.
- For binary trees, null can also be a binary tree. So can act as a recursive design to add elements to the left or right of a node or add elements as the tree is empty, when this node is empty (null), just at this time will be the new one node will return to this node elements added and give a layer of the binary search tree nodes of left or right to receive or give root root node to receive, The node returned is a binary search tree and also the root node of the tree. The equal elements are not processed, and finally the root node is returned to the upper node or root node to receive.
- There is no need to determine whether the binary search tree is empty during the initial call to the add operation, just use root to receive the call result.
- The above process is represented by a GIF as follows:
-
The code is improved as follows:
/** * add a new element element * to the binary search tree@paramElement adds a new element */ public void add(E element) { root = add(root, element); } /** * Adds element element * recursive function * to binary search tree whose root node is node@paramNode adds the root node * of the binary search tree for the element@paramElement The added element *@returnReturns the root of the binary search tree */ after the new node is inserted private Node add(Node node, E element) { // Termination conditions if (node == null) { // When recursing to an empty node,new a root node adds an element to the node and returns it to the left or right node of the binary search tree at the next level or to the root node size++; return new Node(element); } // Add elements recursively if the terminating condition is not met if (element.compareTo(node.element) < 0) { // Smaller than the current node, adds to the left subtree, and receives results using the left node of the current node node.left = add(node.left, element); } else if (element.compareTo(node.element) > 0) { // Larger than the current node, add to the right subtree, and use the right node of the current node to receive the result node.right = add(node.right, element); } // Finally return the original node to the upper-layer left node or right node or root node return node; } Copy the code
Query operation
-
For binary search tree queries, we implement a CONTAINS method to determine whether the element we are looking for exists in the binary search tree, returning true if it does, and false if it does not.
-
The implementation steps for this operation are as follows (recursive implementation) :
- First check whether the current recursion to the root node is empty, if it is empty, the current recursion to the tree has no elements, return false.
- It then checks whether the element in the current recursion to the root node is the element to look for, and returns true if it is, otherwise subsequent checks are made.
- For the rest of the judgment is to determine whether the element to be searched is greater than or less than the root node to which the current recursion occurs. If the value is greater, the search will continue in the right subtree, and if the value is less than, the search will continue in the left subtree, and then continue the operations in steps 1, 2 and 3 above until the result appears.
-
The code for this operation is as follows:
/** * Check whether the binary search tree contains element element *@paramElement Specifies the element to search for@returnContains element element returns true; Otherwise return false */ public boolean contains(E element) { // Search the entire tree return contains(root, element); } /** * Check whether the binary search tree root node contains element element * recursive function *@paramThe root of the binary search tree that node looks up@paramElement Specifies the element to search for@returnContains element element returns true; Otherwise return false */ private boolean contains(Node node, E element) { if (node == null) { // Return false if the root node of the binary search tree is empty return false; } if (element.compareTo(node.element) == 0) { // The current recursion to the root element is element, containing, returns true return true; } else if (element.compareTo(node.element) < 0) { // If element is smaller than the element in the current root node, look in the left subtree return contains(node.left, element); } else { // If element is larger than the current root element, look in the right subtree returncontains(node.right, element); }}Copy the code
Traversal operation
- For traversal, this operation is quite common. In binary search trees, traversal is to visit all nodes once. In the previous linear structure, traversal is extremely easy; just use loops. But it’s not much harder to traverse in a tree than it is in a linear structure, and it’s easier. In the tree structure, there are so many traversal: pre-order traversal, in order traversal, after order traversal, order traversal, the following is a simple realization of the binary search tree in these traversal.
The former sequence traversal
- Recursion is also used to perform the preceding traversal of binary search tree. In the case of a pre-traversal, the order of traversal is to visit the current node, then the left subtree of the node, then the right subtree of the node, and the same process is repeated in the subtree. Return when a node is null. The process can be graphically represented as follows:
-
The above process is realized in code form as follows:
/** * a binary search tree traversal */ public void preOrder(a) { // Start with the root node preOrder(root); } /** * recursively traverses a binary search tree rooted in node@paramNode the root node of the binary search tree traversed by the preceding order */ private void preOrder(Node node) { // Termination conditions if (node == null) { // Return to the empty node return; } // Access node operations (here simply print the elements stored in the node) System.out.println("element: " + node.element); // Traverses the left subtree of the current node preOrder(node.left); // Traverses the right subtree of the current node preOrder(node.right); } Copy the code -
Once you’ve implemented the code, do a little test to verify that it’s correct. Here’s the test code:
/** * 测试 BST */ public static void main(String[] args) { BST<Integer> bst = new BST<>(); int[] nums = {8.4.9.10.5.3}; for (int num : nums) { bst.add(num); } // Binary search tree // ///////////////// 8 / / / / / / / / / / 9 / / / / 4 // / \ \ // // 5 ///////////////// // preorder traversal bst.preOrder(); } Copy the code -
The test results are as follows, which can be seen that the results comply with the rules of the preceding traversal, which verifies the correctness of the code:
-
Once you’ve implemented pre-traversal, you can use pre-traversal to rewrite the toString method for the BST class to print out the binary search tree for observation.
-
The implementation code is as follows:
/** * Rewrite toString to print binary search tree */ @Override public String toString(a) { StringBuilder result = new StringBuilder(); generateBSTString(root, 0, result); return result.toString(); } /** * generates a binary search tree string * with node as the root node and depth starting from depth@paramNode Root node *@paramThe depth depth *@paramResult Generated result */ private void generateBSTString(Node node, int depth, StringBuilder result) { if (node == null) { result.append(generateDepthString(depth) + "null\n"); return; } result.append(generateDepthString(depth) + node.element + "\n"); result.append("left : "); generateBSTString(node.left, depth + 1, result); result.append("right: "); generateBSTString(node.right, depth + 1, result); } /** * Prints the current depth based on the current depth -- quantity *@paramDepth Current depth *@returnReturns the -- string */ for the current depth private String generateDepthString(int depth) { StringBuilder result = new StringBuilder(); for (int i = 0; i < depth; i++) { result.append("--"); } return result.toString(); } Copy the code -
Test this as well:
/** * 测试 BST */ public static void main(String[] args) { BST<Integer> bst = new BST<>(); int[] nums = {8.4.9.10.5.3}; for (int num : nums) { bst.add(num); } // Binary search tree // ///////////////// 8 / / / / / / / / / / 9 / / / / 4 // / \ \ // // 5 ///////////////// // preorder traversal bst.preOrder(); System.out.println("\n==========\n"); System.out.println(bst); } Copy the code -
The running effect is as follows, it can be seen that all nodes of the same layer print the correct depth, and the traversal order also meets the rules of the preceding traversal:
- At this point, the completion of the pre-order traversal, for the following in-order traversal and post-order traversal in essence and the implementation of the pre-order traversal is not much different, but the node access order changes.
In the sequence traversal
- For middle-order traversal, the order of traversal is to visit the left subtree of the current node, then that node, then the right subtree of that node, and the same process is repeated in the subtree. Return when a node is null. The process can be graphically represented as follows:
-
The above process is realized in code form as follows:
/** * middle order traversal of binary search tree */ public void inOrder(a) { inOrder(root); } /** * a binary search tree with node as root * recursive function *@paramThe root of the sequential traversal binary search tree in node */ private void inOrder(Node node) { // Termination conditions if (node == null) { // Return to the empty node return; } // Traverses the left subtree of the current node inOrder(node.left); // Access node operations (here simply print the elements stored in the node) System.out.println("element: " + node.element); // Traverses the right subtree of the current node inOrder(node.right); } Copy the code -
Also call this method to test, the running result is as follows, it can be seen that the output order conforms to the rules of order traversal, verify the correctness of the code:
- The result also shows a characteristic of middle-order traversal: the output result is sorted. The reason is that the left subtree of the binary search tree is smaller than the parent node, and the right subtree is larger than the parent node. The order of middle-order traversal is exactly that the left subtree is visited first, then the parent node, and then the right subtree. So the output results are printed in ascending order.
After the sequence traversal
- For back-order traversal, the sequence of traversal is to visit the left subtree of the current node, then the right subtree of the node, then the node, and the same process is repeated in the subtree. Return when a node is null. The process can be graphically represented as follows:
-
The above process is realized in code form as follows:
/** * backorder traversal of binary search tree */ public void postOrder(a) { postOrder(root); } /** * recursively traverses the binary search tree rooted in node@paramNode is the root of the binary search tree traversed backwards by */ private void postOrder(Node node) { // Termination conditions if (node == null) { // Return to the empty node return; } // Traverses the left subtree of the current node postOrder(node.left); // Traverses the right subtree of the current node postOrder(node.right); // Access node operations (here simply print the elements stored in the node) System.out.println("element: " + node.element); } Copy the code -
Also call this method to test, the running result is as follows, it can be seen that the output order conforms to the rules of order traversal, verify the correctness of the code:
- It can also be seen from the results that the back-order traversal starts from the child nodes to the parent node in a back-to-front order. This feature is also suitable for the application of freeing memory for binary search trees. When you want to free up memory for a model that conforms to binary search tree characteristics, you can use the binary search tree backward traversal to do so.
Non-recursive implementation of pre -, middle – and post-order traversal
- After realizing the recursive way of pre-middle and post-order traversal, we can use the non-recursive way to implement these three traversal again and again to deepen the understanding of binary search tree.
- In the learning of recursion, we can know that the recursive call function will be pushed into the system stack to record the execution order, and when the execution is finished, the stack will go back to the place where the function was called last time to continue to perform the remaining operations.
- Therefore, for the non-recursive implementation, we can use the stack data structure to manually simulate the system stack to achieve the binary search tree before, middle and post order traversal. The next step is to implement the three non-recursive ways of traversal.
A non-recursive implementation of preordered traversal
- For the process of using stack to help simulate the system stack to realize the preorder traversal, a GIF is used to represent it as follows:
-
For the above process, due to the last-in, first-out feature of the stack and the rule of pre-order traversal, after traversing a node and pushing it off the stack, the right node of the node is first pushed and then the left node is pushed. In this way, the rule of pre-order traversal can be satisfied after the subsequent traversal of the node.
-
The above process code is as follows:
/** * a non-recursive pre-traversal of a binary search tree */ public void preOrderNotRecursive(a) { // If the tree is empty, it is not traversed. There are no elements to traverse if (root == null) { return; } // Use a stack to simulate the system stack to implement the sequential traversal Stack<Node> stack = new Stack<>(); // Start with the root node stack.push(root); // When the stack is not empty, the following process is iterated over the binary search tree while(! stack.isEmpty()) {// The node currently traversed Node currentNode = stack.pop(); System.out.println("element: " + currentNode.element); // If the left and right nodes of the current traversal node are not empty, the right node is pushed in the order of the left node if(currentNode.right ! =null) { stack.push(currentNode.right); } if(currentNode.left ! =null) { stack.push(currentNode.left); }}}Copy the code -
When implemented, the recursive method before the call is compared with the non-recursive method to see if the two results are the same:
- It can be seen from the result that the non-recursive implementation is correct. Compared to the steps of recursive implementation, the non-recursive implementation is relatively complex, but through such an implementation can also strengthen the understanding of binary search tree before the order traversal, or quite beneficial, and then continue to achieve the order traversal and post-order traversal of the non-recursive way.
Non-recursive implementation of sequential traversal
-
For the non-recursive implementation of middle-order traversal, a stack is also used to simulate the recursion process of the system stack to achieve, first of all, an internal class is used to encapsulate the current instruction (continue to simulate recursion, print nodes) and the node to simulate the current recursion, in order to simulate the sequential traversal in the implementation of stack recursion.
-
The specific implementation of this inner class is as follows, where S stands for instruction; if S is go, it means to continue simulating recursion; if S is print, it means to print the current node information.
/** * encapsulates instructions and recursive node information when emulating the system stack */ private class Command { / / s: instruction // go: continue to simulate recursion // print: displays the current node information private String s; // The node to which the current simulation recurses private Node node; public Command(String s, Node node){ this.s = s; this.node = node; }}Copy the code -
When such an inner class is encapsulated, non-recursive middle-order traversal is easier to achieve, and the specific process is as follows:
- At the beginning, the root node and the instruction go are pushed to indicate that the simulation recursion continues from the root node.
- Then the loop begins, repeating the contents of the loop as long as the stack is not empty:
- First, we get the current top information from the top of the stack.
- Then check whether the instruction in the information at the top of the stack is print. If print is used to print the node information, otherwise do the following operations.
- If the instruction is go, the right subtree of the current node and the instruction go are pushed first. (The same as the previous non-recursive front-order traversal, due to the last in first out feature of the stack, need to reverse the stack, after the stack to comply with the middle-order traversal)
- Then the current node and the instruction print are added to the stack. When the next node is removed from the stack, it can be determined that the print instruction prints this node.
- Finally, the left subtree of the current node and the instruction go are pushed into the stack. In this way, the first one to be pushed out of the stack is the left node, then the parent node of the left node, and then the right node, satisfying the rules of middle-order traversal.
- In this way, repeat the above process, you can simulate the system stack recursion to achieve binary search tree traversal, the above process is illustrated as follows:
-
The specific code is as follows:
/** * non-recursive middle order traversal of binary search tree */ public void inOrderNotRecursive(a) { // If the tree is empty, it is not traversed. There are no elements to traverse if (root == null) { return; } // Use a stack to simulate sequential traversal in the system stack Stack<Command> stack = new Stack<>(); // Initially push the root node and the instruction go onto the stack stack.push(new Command("go", root)); // When the stack is not empty, the following process is iterated through the binary search tree in order while(! stack.isEmpty()) {// Push the top information out of the stack, judge the instructions in the stack to do the corresponding operation Command command = stack.pop(); if ("print".equals(command.s)) { System.out.println("element: " + command.node.element); } else { if(command.node.right ! =null) { stack.push(new Command("go", command.node.right)); } stack.push(new Command("print", command.node)); if(command.node.left ! =null) { stack.push(new Command("go", command.node.left)); }}}}Copy the code -
Again, this was tested to verify that it was written correctly, with the following results:
- From the test results, it can be seen that the traversal result is in line with the expected, and the result of the recursive method is consistent with the previous implementation, which verifies the correctness of the code. In the realization of the non-recursive way of the order traversal, after the order traversal is also easy to come, the principle is similar, then the realization of the post-order traversal of the non-recursive way.
Non-recursive implementation of post-order traversal
-
The non-recursive implementation of post-order traversal also uses Command to encapsulate stack information. The specific implementation process is as follows:
- At the beginning, the root node and the instruction go are pushed to indicate that the simulation recursion continues from the root node.
- Then the loop begins, repeating the contents of the loop as long as the stack is not empty:
- First, we get the current top information from the top of the stack.
- Then check whether the instruction in the information at the top of the stack is print. If print is used to print the node information, otherwise do the following operations.
- If the instruction is go, the current node and the instruction print are pushed on the stack first. When the next node is off the stack, it can be judged that the print instruction prints this node. (The same as the previous non-recursive forward traversal, due to the last in, first out feature of the stack, the need to reverse the stack, after the stack to comply with the order traversal)
- It then pushes the right subtree of the current node and the instruction go.
- Finally, the left subtree of the current node and the instruction go are pushed into the stack. In this way, the first one to be pushed out of the stack is the parent node of the left node, then the right node, and then the left and right nodes, satisfying the rules of post-order traversal.
- In this way, repeat the above process, you can simulate the recursion of the system stack to achieve the binary search tree after the order traversal, the above process is illustrated as follows:
-
The specific code is as follows:
/** * a non-recursive back-order traversal of a binary search tree */ public void postOrderNotRecursive(a) { // If the tree is empty, it is not traversed. There are no elements to traverse if (root == null) { return; } // Use a stack to simulate the sequential traversal of the system stack Stack<Command> stack = new Stack<>(); // Initially push the root node and the instruction go onto the stack stack.push(new Command("go", root)); // When the stack is not empty, the following process is iterated through the binary search tree while(! stack.isEmpty()) {// Push the top information out of the stack, judge the instructions in the stack to do the corresponding operation Command command = stack.pop(); if ("print".equals(command.s)) { System.out.println("element: " + command.node.element); } else { stack.push(new Command("print", command.node)); if(command.node.right ! =null) { stack.push(new Command("go", command.node.right)); } if(command.node.left ! =null) { stack.push(new Command("go", command.node.left)); }}}}Copy the code -
Again, this was tested to verify that it was written correctly, with the following results:
- From the test results, it can be seen that the traversal result is in line with the expected, and the result of the recursive method is consistent with the previous implementation, which verifies the correctness of the code. At this point, will be before, in, after the order traversal of the non-recursive way to achieve a again, using the simulation of the system stack, so also deepen the understanding of these three traversal and the understanding of recursion, then to achieve the binary search tree in the last traversal layer traversal.
Sequence traversal
- In the implementation process of the previous three traversal modes, it can be found that these three traversal modes always go to the lowest node first and then return up, which is depth-first traversal.
- For sequential traversal, it is traversed layer by layer from left to right, which is also known as breadth-first traversal.
- This traversal is usually implemented in a non-recursive manner, and can be implemented with the help of a queue data structure.
- For the implementation process, when a node joins and leaves the queue, this node will be traversed. At the same time, when this node leaves the queue, due to the first-in, first-out feature of the queue and the rules of sequential traversal, the left and right nodes of this node will join the queue in the order of left node and right node. At this time, when the node at the head of the queue leaves the queue, Then the left and right nodes of the outgoing nodes are added to the queue in the order of the left node and the right node. In this way, the sequence traversal operation of binary search tree is completed. This process is shown in the figure below:
-
The above process code is as follows:
/** * order traversal of binary search tree */ public void levelOrder(a) { // Implement sequence traversal with a queue Queue<Node> queue = new LinkedList<>(); // Start with the root node queue.add(root); // When the queue is not empty, the following process is iterated through the binary search tree while(! queue.isEmpty()) {// The node currently traversed Node currentNode = queue.remove(); System.out.println(currentNode.element); // If the left and right nodes of the current traversal are not empty, join the queue in the order of the left node and the right node if(currentNode.left ! =null) { queue.add(currentNode.left); } if(currentNode.right ! =null) { queue.add(currentNode.right); }}}Copy the code -
Call this method to verify that it is correct:
- It can be seen from the result that the order of traversal conforms to the expectation, which verifies the correctness of the code. At this point, several traversal ways of binary search tree are realized, and then the final deletion operation is realized.
Delete operation
Delete the maximum and minimum elements
- To delete, first to delete from a binary search tree of the maximum and the minimum to start, because, according to the characteristics of the binary search tree, the leftmost node is the minimum value of the entire tree, most the right side of the node is the maximum of the whole tree, so the two operations are relatively easy to implement, after first realized the two operations at the same time, It is also useful for subsequent deletion of any element. Here are a few sample graphs of maximum and minimum values:
-
Before deleting the binary search tree, implement two functions to find the smallest and largest elements of the binary search tree for deletion, as follows:
/** * find the smallest element of the binary search tree *@returnReturns the smallest element of the current binary search tree */ public E minimum(a) { // Check whether the current binary search tree is empty if (size == 0) { throw new IllegalArgumentException("Minimum failed. Current BST is empty!"); } return minimum(root).element; } /** * returns the minimum value of the binary search tree rooted in node *@paramNode finds the root of the binary search tree * for the minimum value@returnReturns the smallest element of the current binary search tree */ private Node minimum(Node node) { // When the left of a node is empty, it is the leftmost node in the tree if (node.left == null) { return node; } // Otherwise continue to look in the left subtree return minimum(node.left); } /** * find the largest element of the binary search tree *@returnReturns the largest element of the current binary search tree */ public E maximum(a) { // Check whether the current binary search tree is empty if (size == 0) { throw new IllegalArgumentException("Maximum failed. Current BST is empty!"); } return maximum(root).element; } /** * returns the node with the maximum value of the binary search tree rooted in node *@paramNode looks for the root of the maximum binary search tree *@returnReturns the largest element of the current binary search tree */ private Node maximum(Node node) { // When the right of a node is empty, the node is the rightmost node in the tree if (node.right == null) { return node; } // Otherwise continue to look in the right subtree return maximum(node.right); } Copy the code -
After the above functions are implemented, you are ready to delete.
-
First, delete the minimum value. There are two cases for deleting the minimum value: the deleted node is a leaf node, and the deleted node has a right subtree.
-
For leaf nodes, simply delete them. For a node with a right subtree, the deletion logic is also very simple. The current node is separated from the tree, and then the right subtree of the node is connected to its original position. For a leaf node, both the left and right nodes are null, so the same logic can be used to delete a leaf node, except that the node’s original location is null.
-
The above process is illustrated as follows:
-
The code implementation is as follows:
/** * removes the node with the minimum value in the binary search tree and returns the minimum value * removed@returnReturns the element */ in the deleted node public E removeMin(a) { // Receive the minimum value in the current binary search tree, ready to return after deletion E delElement = minimum(); // Delete operation root = removeMin(root); // Returns the minimum value to delete return delElement; } /** * Delete the smallest node * in the binary search tree with node as root@paramNode removes the root node * of the binary search tree for the smallest node@returnReturns the root of the new binary search tree after the node is deleted, that is, the root of the right subtree of the deleted node */ private Node removeMin(Node node) { // If the left node of a recursive node is empty, this node is the smallest node, and the operation is deleted if (node.left == null) { // Record the right subtree of the deleted node Node rightNode = node.right; // Detach node from its right subtree node.right = null; size--; // Return the right subtree of the node to the upper node, and the node and the upper node are separated return rightNode; } // If the left node is not empty, continue recursively to the left subtree, using the left node of the current root node to receive node.left = removeMin(node.left); // Finally return the current root node to complete the deletion return node; } Copy the code -
Once the smallest element is removed, it is much easier to remove the largest element. The logic of deletion is generally the same, that is, the left subtree of the deleted node is connected to the original location of the node. The deletion process is illustrated as follows:
-
The code implementation is as follows:
/** * Removes the node with the maximum value in the binary search tree and returns the maximum value *@returnReturns the element */ in the deleted node public E removeMax(a) { // Accept the maximum value in the binary search tree, ready to return after deletion E delElement = maximum(); // Delete operation root = removeMax(root); // Returns the minimum value to delete return delElement; } /** * Delete the largest node * of the binary search tree root node@paramNode removes the root node * of the binary search tree for the largest node@returnReturns the root of the new binary search tree after the node is deleted, that is, the root of the left subtree of the deleted node */ private Node removeMax(Node node) { // If the right node of a recursion node is empty, this node is the largest node, delete the operation if (node.right == null) { // Record the left subtree of the deleted node Node leftNode = node.left; // Detachnode from its left subtree node.left = null; size--; // Return the left subtree of the node to be received by the upper node return leftNode; } // If the right node is not empty, continue recursively through the right subtree, using the right node of the current root node to receive node.right = removeMax(node.right); // Finally return the current root node to complete the deletion return node; } Copy the code -
Once you’ve done both, test them out.
-
The test logic is as follows: Generate 1000 random numbers [0, 10000] to add to the binary search tree, and then use these two operations respectively to add the deleted elements to an ArrayList, which is then checked to see if the elements are in descending order or descending order. If the verification is successful, the above operation code is correct.
-
The test code is shown below:
private static void testRemoveMin(a) { // Test deleting the smallest node BST<Integer> bst = new BST<>(); Random random = new Random(); int n = 1000; for (int i = 0; i < n; i++) { bst.add(random.nextInt(10000)); } ArrayList<Integer> nums = new ArrayList<>(); while(! bst.isEmpty()) { nums.add(bst.removeMin()); }// Verify that nums are sorted in ascending order for (int i = 1; i < nums.size(); i++) { if (nums.get(i - 1) > nums.get(i)) { // If one number is larger than the next, the implementation of the deletion of the smallest node is wrong throw new IllegalArgumentException("removeMin error!"); }}// Run this command System.out.println("removeMin test completed."); } private static void testRemoveMax(a) { // Test deleting the largest node BST<Integer> bst = new BST<>(); Random random = new Random(); int n = 1000; for (int i = 0; i < n; i++) { bst.add(random.nextInt(10000)); } ArrayList<Integer> nums = new ArrayList<>(); while(! bst.isEmpty()) { nums.add(bst.removeMax()); }// Verify that nums are sorted in descending order for (int i = 1; i < nums.size(); i++) { if (nums.get(i - 1) < nums.get(i)) { // If one of the numbers is smaller than the next, the operation to delete the largest node is not implemented correctly throw new IllegalArgumentException("removeMax error!"); }}// Run this command System.out.println("removeMax test completed."); } Copy the code -
The results
- From the result, we can see that the above two deletion operations are correct, and then we can implement the deletion of any element.
Delete any element
-
For the deletion of any element in binary search tree, there are also several cases: deletion of nodes with only left children, deletion of nodes with only right children, deletion of nodes with both left and right children.
-
For the first two cases: Delete only the left child node, delete, only the right child node, in front of the specific steps and actually remove maximum node and remove minimum node is similar, also will delete the node left subtree or right sub tree in the nodes of the original position, the original node to break away from a binary search tree, so for the deletion of the two cases, The implementation is basically the same as before.
-
In the case of deleting nodes with children on both sides, the previous method cannot be used. In this case, the Hibbard Deketion principle proposed by Hibbard can be used to delete the nodes.
-
The steps are as follows:
- The node to be deleted is first recorded as D, and then the smallest node in the subtree is found from the right subtree of D and recorded with S, which is the successor node of D.
- Then delete the smallest node, that is, S, from the right subtree of D, and assign the root of the right subtree after deleting S to the right node of S. So s goes from the smallest position in the right subtree to the root.
- And then we assign the left subtree of D to the left subtree of S.
- Finally, detach D from the binary search tree and connect S to d. At this point, d is removed from the tree.
-
In simple terms, the nodes of the right subtree of D are all greater than D, and the smallest node is the node behind it. At this point, if s is placed at the position of D, the left subtree of this NODE of S still satisfies the feature that is smaller than it, and the right subtree satisfies the feature that is greater than it. Now you can delete the d.
-
Similarly, we can also find its precursor in the left subtree of D, that is, the largest node in the left subtree, record it with P, and then place p at the position of D according to the principle of operation S above, so as to achieve the effect of deleting D. So instead of doing this find the precursor, do the find the successor s to delete d.
-
For the above deleted steps, they are shown as follows:
- Example of deleting a node with only the left child:
- Example of deleting a node with only the right child:
- Example For deleting nodes that are owned by both the left and right children:
- Example of deleting a node with only the left child:
-
The code implementation is as follows:
/** * Removes the element * from the binary search tree@paramElement The element */ to be removed from the binary search tree public void remove(E element) { root = remove(root, element); } /** * Delete the node whose value is element in the binary search tree root node * recursive function *@paramNode removes the root of the binary search tree * for the element@paramElement The element to be deleted@returnReturns the root */ of the new binary search tree after the node is deleted private Node remove(Node node, E element) { if (node == null) { // If the root node is empty and there are no elements to delete, return null return null; } if (element.compareTo(node.element) < 0) { // If the element to be deleted is smaller than the element of the current root node, continue looking for element in the left subtree to delete and receive the result using the left node of the current root node node.left = remove(node.left, element); // After the deletion, the current root node is returned to the upper-layer node return node; } else if (element.compareTo(node.element) > 0) { // If the element to be deleted is larger than the element of the current root node, continue looking for element in the right subtree to delete and use the right node of the current root node to receive the result node.right = remove(node.right, element); // After the deletion, the current root node is returned to the upper-layer node return node; } else { // Delete the element in the root node // Only the right subtree is currently deleted if (node.left == null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } // Only the left subtree is currently deleted if (node.right == null) { Node leftNode = node.left; node.left = null; size--; return leftNode; } // The subtrees left and right of the node to be deleted are not empty // Find the smallest node of the size of the currently deleted node, that is, the smallest node of the subtree of the deleted node // Replace the location of the deleted node with the minimum node Node successor = minimum(node.right); // Move the smallest node of the right subtree to the root of the right subtree successor.right = removeMin(node.right); // Assign the left subtree of the smallest node to the left subtree of the deleted node successor.left = node.left; // Detach the node from the binary search tree node.left = node.right = null; Succeeded // go back to the upper nodes to succeed the nodes and delete the nodes returnsuccessor; }}Copy the code -
After the implementation, also test this to verify the code is correct, the test code is as follows:
/**
* 测试 BST
*/
public static void main(String[] args) {
BST<Integer> bst = new BST<>();
int[] nums = {8.4.9.10.5.3};
for (int num : nums) {
bst.add(num);
}
System.out.println("Before deleting:");
System.out.println(bst);
// Binary search tree //
/////////////////
8 / / / /
/ / / / / /
9 / / / / 4
// / \ \ //
// 5
/////////////////
// Delete the node where 4 resides
bst.remove(4);
// Delete binary search tree //
//////////////////
8 / / / / /
/ / / / / / /
/ / 5 9 / / /
/ / / / / / /
10 / / / / / 3
//////////////////
System.out.println("After deletion:");
System.out.println(bst);
// sequence traversal
// bst.levelOrder();
// preorder traversal
// bst.preOrder();
// System.out.println("\n==========\n");
// non-recursive preorder traversal
// bst.preOrederNotRecursive();
// middle order traversal
// bst.inOrder();
// System.out.println("\n==========\n");
// after the sequence traversal
// bst.postOrder();
// System.out.println(bst);
// Verify that the minimal node is deleted successfully
// testRemoveMin();
// Verify that the maximum node is deleted successfully
// testRemoveMax();
}
Copy the code- The results
- From the results of the run, you can see that it is in line with expectations, and verify that the code was written correctly. At this point, the binary search tree of these operations are completed.
If there is insufficient writing, please forgive me, please give more advice.
My personal blog website:www.xilikeli.cnWelcome to visit (#.#)
And welcome to mineMaking the home page, my personal blog has been open source, interested partners can dot star, thank you (#.#)