Original link: Part3: binary trees and bsts
This article is the third part of the "Testing Data Structure" series, discussed, is the common data structure that is not included in the .NET Framework base library: binary tree. Like the array of linear arrangements, we can imagine the binary tree to store data in two dimensions. One of the special binary trees, we call a binary search tree, referred to as BST, and its data search capability is more optimized than a general array.
Directory: Introduction Data Understanding in Trees Two-forked Tree Use BSTS to Improve Data Search Time Reality World Binary Search Tree
Introduction:
In the first part of this series, we tell what is the data structure, how to evaluate their performance, and how to handle specific algorithms based on their performance to select specific data structures. In addition, we review the basics of the data structure, understand the most commonly used data structure - arrays and ArrayList associated with them. In the second part, we told the two brothers of ArrayList - stacks and queues. The way they store data is very similar to ArrayList, but they have been restricted by accessing data. We also discussed a hash table that can be used as its index in any object, not the ordinal number used.
ArrayList, stack, queue and hash table can be considered an array structure from the form of storing data. This means that these four data structures will be limited by array boundaries. Recall the first part, the array stores data in memory. When the array capacity reaches the maximum value, it is necessary to explicitly change its capacity, while the line search time will increase.
This section, we tell a new data structure - binary tree. It stores data in a non-linear manner. After that, we will also introduce a more distinctive binary-binary search tree (BST). BST specifies some rules of each element item in the tree. These rules ensure that BSTS can search for data with a performance of linear search time.
Arrange data in the tree
If we have seen a family tree, or a company's organizational map, then in fact, you have understood the arrangement of data in the tree. The tree consists of a collection of many nodes, which have many associated data and "children". The child node is the node directly under the node. The parent node is located above the node directly. The root of the tree is a single node that does not include a parent node.
Figure 1 shows the organizational structure of the company staff.
Figure one
In the example, the root of the tree is BOB Smith, which is the company's CEO. This node is the root node because there is no father on it. Bob Smith nodes have a child Tina Jones, president of the company. Its parent node is BOB Smith. Tina Jones has three children: Jisun Lee, CIO Frank Mitchell, CFO Davis Johnson, the father of these three nodes of these three nodes is Tina Jones node.
All trees have the following common features: 1, only one root; 2, in addition to the root node, all other nodes and only one parent node; 3, there is no ring structure. Starting from any of the nodes, there is no path to the start node. It is the first two characteristics to ensure that there is no ring structure.
For data with hierarchical relationships, the tree is very useful. Later, we will say that when we have a skill to arrange data with a hierarchy, searching for each element will be significantly reduced. Prior to this, we first need to discuss a special tree: binary tree.
Understand the binary tree
The binary tree is a special tree because all of its nodes can only have two child nodes. And, for the nodes specified in the binary tree, the first child node must point to the left child, the second node points to the right child. As shown in Figure 2: Figure 2
The binary tree (a) has 8 nodes, and the node 1 is root. The left child of node 1 is node 2, and the right child is node 3. Note that the node does not require simultaneous children and right children. For example, in the binary tree (a), the node 4 has only one right child. Even, the node can also have children. Such as the bifurcation (B), nodes 4, 5, 6 have no children. Nodes without children are called leaf nodes. Nodes with children are called internal nodes. As shown in Figure 2, nodes 6, 8 in the binary tree (a) are leaf nodes, nodes 1, 2, 3, 4, 5, 7 are internal nodes.
Unfortunately, .NET Framework does not include binary tree, in order to better understand the binary tree, we need to create this class.
Step 1: Create a node Node
The node Node is abstractly representative of a node in the tree. Recognizing that the node in the binary tree should include two contents: 1, data; 2, child node: 0, 1, 2;
The data stored in node depends on your actual needs. As an array can store integers, strings, and other types of instances, the node should be the case. So we should set the data types stored by the node class to Object.
Note: You can create strong types of node classes in the C # 2.0 version, which is better than using the Object type. To learn more about using generic information, please read JuVal Lowy's article: an Introduction to C # generics.
Below is the code of the node class:
Public class node {private object data; private node limited;
#region constructors public node (): this (null) {} PUBLIC NODE (Object Data): This (Data, Null, Null) {} public node (Object Data) {this.data = DATA THIS.LEFT = Left; this.right = right;} #ENDREGON
#Region Public Properties Public Object Value {Get {Return Data;}}
Public node left;} set {left = value;}}
Public node right {get {Right = value;}} #ENDREGON}
Note that class node has three private members: 1, data, type Object: data stored in node; 2, Left, Node type: point to Node left child; 3, Right, Node type: point to Node's right child; 4, Other parts of the class are constructor and public fields to access these three private member variables. Note that LEFT and Right private variables are Node types, that is, the instance of the Node class is included in the member of the Node class. Create a binary tree binarytree
Create a BinaryTree class after creating the Node class. The BinaryTree class contains a private field - Root - it is the Node type, which represents the root of the binary tree. This private field is exposed in a public field.
The BinaryTree class has only one public method clear (), which is used to clear all the elements in the tree. The CLEAR () method simply simply sets the root node to NULL. The code is as follows: public class binarytree {private node root
Public binarytree () {root = NULL;}
#Region Public Methods Public Virtual Void Clear () {root = null;} #ENDREGON
#Region Public Properties Public Node Root {Get {Return Root;} set {root = value;}} #ENDREGON}
The following code demonstrates how to use the BinaryTree class to generate the same data structure as the binary tree (a) shown in Figure 2: binarytree btree = new binarytree (); btree.root = new node (1); btree.Root.Left = New node (2); btree.Root.right = new node (3);
Btree.Root.Left.Left = new node (4); btree.Root.right.right = new node (5);
Btree.Root.Lell.right = new node (6); btree.Root.right.right.right = new node (7);
Btree.Root.right.right.right.right = new node (8);
Note that after we create an instance of a BinaryTree class, create a root node (root). We must have an instance of the new node Node for the corresponding left and right children. For example, add node 4, it is the left node of the left node of the root node, our code is: btree.Root.Lell.Left = new node (4);
Recall the array elements we mentioned in the first part, enabling in a continuous memory block, so the positioning time is constant. Therefore, the number of elements that access the specific elements is not related to the number of elements of the array.
However, the binary tree is not continuously stored in memory, as shown in Figure 3. In fact, an example of a BinaryTree class points to the root node class instance. The root node class instance points to its left and right children's node instances, respectively, and so on. The key is that different Node instances that make up the binary tree are dispersed in the CLR hosted stack. They don't have to be continuously stored as array elements. Figure 3 If we want to access specific nodes in the binary tree, we need to search for each node of the binary tree. It cannot be accessed directly according to the specified node as the array. Searching the binary tree is throwing linear time, the worst case is to query all nodes. That is, when the number of binary tree nodes increases, the number of steps to find any node will also increase accordingly.
Therefore, if the positioning time of the binary tree is linear, the query time is also linear, and how do you say that the binary tree is better than the array? Because the query time of the array is also linear, the positioning time is constant? Yes, the general binary tree does not provide better performance than arrays. However, when we have tips to arrange the elements in the binary tree, we can improve the query time (of course, the positioning time will be improved).
Improve data search time with BSTS
The binary search tree is a special binary tree that improves the efficiency of the binary tree data search. The binary search tree has the following attributes: For any of the node n, the value of each post-generation node under the left sub-tree is less than the value of the node N; and the value of each of the prototypes under the top right is greater than the node N Value.
The subtree of the so-called node N can see it as a tree with node N is the root node. Therefore, all nodes of the subtree are the descendants of node N, while the root of the subtree is the node N itself. Figure 4 demonstrates the concept of the subtree and the properties of the binary search tree. Figure four
Figure 5 shows two examples of the binary tree. Right, Binary Tree (B) is a binary search tree (BST) because it meets the properties of the binary search tree. The binary tree (a) is not a binary search tree. Because the node 10 of the node 10 is smaller than the node 10, it appears in the right sub-tree of node 10. Similarly, the right child of node 8 is less than node 8, but appears in its right sub-tree. Regardless of which position, it does not meet the attributes of the binary search tree, it is not a binary search tree. For example, the right child of node 9 can only contain a node (8 and 4) having a value of less than node 9. Figure 5
From the properties of the binary search tree, the data stored by the BST nodes must be compared to the additional nodes. The two nodes are given, the BST must be able to determine that the value of the two nodes is less than, greater than or equal.
Now, I want to find a particular node for BST. For example, the binary search tree (b) in Figure 5, we have to find node 10. BST and the general binary tree are only one root node. So what is the best solution for the node 10 exists in the tree? Is there a better way to search the whole tree?
If the node 10 exists in the tree, we start from the root. It can be seen that the value of the root node is 7, which is less than the node value we have to find. Therefore, once the node 10 exists, there is inevitable a right tree. So you should jump to node 11 to continue searching. At this time, the node 10 is smaller than the value of the node 11, inevitably present in the left subtree of the node 11. Move to the left child of node 11, at this time we have found the target node, positioned here.
If we are looking for nodes do not exist in the tree, will there be a problem? For example, we look for node 9. The above operation is repeated until the node 10 is reached, and it is greater than the node 9, then if the node 9 is present, it is inevitably in the left subtree of node 10. However, we see that the node 10 does not have left children, so the node 9 does not exist in the tree. OK, our search algorithm is as follows. Assume that we are looking for node N, which pointing to the root node of BST. The algorithm constantly compares the size of the value until the node is found, or it is a null value. Every step we have to handle two nodes: node c in the tree, the node n to be found, and compare the values of C and N. The initialization value of C is the value of the root node of the BST. The following steps are then performed: 1. If the C value is NULL, N is not in the BST; 2, compare the value of C and N; 3, if the value is the same, the specified node N; 4, if the value is less than C, Then if n is present, it is inevitably in the left subtree of C. Therefore, return to the first step, the left child of C is used as C; 5, if the value of n is greater than C, then if n is present, it is inevitable in the right sub-tree in C. So returning to the first step, the right child of C is used as C;
Analysis BST search algorithm
Look for nodes by BST, ideally, the number of nodes we need to check can be halved. As the BST tree of Figure 6, 15 nodes are included. The search algorithm is started from the root node. The first time we determine that we move to the left subtree or the right man tree. For any case, once this step is performed, the number of nodes we need to access is half, from 15 to 7. Similarly, the next step is also reduced by half, down from 7 to 3, and so on. Figure 6
An important concept here is that every step of the algorithm will reduce the number of nodes accessed by half in an ideal state. Compare the search algorithm of the array. When searching for arrays, you want to search all elements, each element search once. That is, the array of N elements is searched. From the first element, we have to access the N-1 element. There is a binary search tree with n nodes. After accessing the root node, only the N / 2 nodes are only needed.
Searching the binary tree is similar to the search sort array. For example, you have to find a John King in the phone. You can start looking up from the middle of the phone, that is, starting from the last name of M. According to the alphabetical order, K is before m, then you can fold the portion before M. At this time, it may be a letter H. Because K is after H, then the h to m is partially folded. This time you found a letter K, you can see if there is James King in the phone.
Searching with BST is similar. The midpoint of the BST is the root node. Then browse from top to bottom, browse your left child or right child. Each step will save half search time. According to this feature, this algorithm has a time complexity of LOG2N and is abbreviated as LOG N. Recall the mathematical problems we discussed in the first part, log2n = Y, equivalent to 2Y = n. That is, the number of nodes increases N, and the search time is only slowly increased to the log2n. Figure 7 shows the difference between the growth rate of LOG2N and linear growth. The algorithm running time of the time complexity of log2N is the straight line below. Figure 7
It can be seen that this logarithmic curve is almost horizontal, and as the N value increases, the curve grows slowly. For example, search for an array with 1000 elements, you need to query 1000 elements, and search for a BST tree with 1000 elements, only 10 nodes are required (log10 1024 = 10).
In the analysis of the BST search algorithm, I continuously repeat "ideally" this word. This is because the actual search time of BST relies on the topology of the node, that is, the layout relationship between nodes. Each step comparison operation can be halved in each step in Figure 6. However, let's take a look at the BST tree shown in Figure Eight, and its topology is assigned with the array of arrays. Figure 8 Search Figure 8 BST tree, still consumes linear time, because each comparison is a node, not like Figure 6.
Therefore, the time to search for BST is to depend on its topology. In the best case, it takes time to log2 n, and the worst case consumes linear time. In the next section, we will see that the topology of the BST is related to the order of the insertion nodes. Therefore, the order in which the node will directly affect the time consumption of the BST search algorithm.
Insert node into BST
We already know how to query a specific node in BST, but we should also master a way to insert a new node. Insert a node to the binary search tree, cannot be arbitrarily, must follow the characteristics of the binary search tree.
Usually we inserted new nodes are as a leaf node. The only problem is how to find a suitable node to make the parent node of this new node. Similar to the search algorithm, we should first compare the node C and the new node n to be inserted. We also need to track the parent nodes of node C. In the initial state, the C node is the root node of the tree, and the parent node is NULL. Locate a new parent node to follow the algorithm: 1. If c points to NULL, the C node is the parent node of N. If the value of n is less than the parent point value, then n is a new left child for the parent node, otherwise the right child; (the translation: original for IF c is a null Reference, the parent Will Be the Parent of n .. if n's value is Less Than Parent's Value, THEN N WILL BE Parent's New Left Child; Otherwise N Will Be Parent's New Right Child. This is if the value of C is empty, the current parent node is the parent node of N. The author thinks it seems wrong. Because if the C value is empty, the BST tree is empty, there is no node, and it should be the special case mentioned later. If it is to point c point null. Then, C is the leaf node, then the newly inserted node should be used as The child of C. That is, C is the parent node of N, which is not the parent node of C as N as the parent node of N. 2, the value of N and C; 3, if c is equal to N, it is used to try into one The same node. At this point, the node is discarded directly or throws an exception. (Note that the value of the node in the BST must be unique.) 4, if n is less than C, then n must be in the left subtree of C. Let the parent node equal to C, C equal to the left child of C, returned to the first step. 5. If n is greater than c, then n must be in the right subtree of C. Let the parent node equal to C, C equal to the right child of C, returned to the first step. When the appropriate leaf node is found, the algorithm ends. Place the new node into the BST to make it a child node for the parent node. There is a special case in the insertion algorithm needs to be considered. If there is no root node in the BST tree, the parent node is empty, then adding a new node is ignored as a child of the parent node. And in this case, the root node of BST must be assigned to a new node.
Figure 9 describes the BST insertion algorithm: Figure Nine BST insertion algorithm and search algorithm time complexity: the best case is log2 N, the worst case is linear. The reason is the same because it is consistent with the strategy to position for the inserted node.
The node insertion order determines that the topology of the BST has been inserted from the newly inserted node. The order inserted will directly affect the topology of BST itself. For example, we insert nodes: 1, 2, 3, 4, 5, 6. When the node 1 is inserted, the root node is used. Then insert 2 as a right child, insert 3 as a right child, 4 as the right child of 3, and so on. Result BST is formed as shown eighta.
If we have the order in which the insertions 1, 2, 3, 4, 5, 6, and the BST tree will extend wider and look more like the structure shown in Figure 6. The desired insertion order is: 4, 2, 5, 2, 3, 6. This will be 4 as a root node, 2 as a left child, 5 as the right child, 1 and 3, respectively, respectively, respectively, left children and right children. And 6 as the right child of 5.
Since the BST's topology will affect the time complexity of the search, insert, and delete (next to introduce), in an ascending or descending order (or approximate ascended order), the data is greatly destroyed the efficiency of the BST. The discussion will be discussed in detail later.
Remove nodes from BST
Removing nodes from BST and more difficult to insert nodes. Because of the deletion of a non-leaf node, other nodes must be selected to fill the breakage of the tree caused by deleting the node. If you do not select a node to fill this break, the binary search tree violates its characteristics. For example, the binary search tree in Figure 6. If the node 150 is deleted, some nodes need to fill the break caused by deletion. If we are arbitrarily selected, such as selecting 92, then violate the BST characteristics, because the nodes 95 and 111 appear in the left subtree of 92, and their value is greater than 92.
The first step in the delete node algorithm is to locate the node to be deleted. This can use the search algorithm described earlier, so the run time is log2 n. The following should be selected to replace the location of the deletion node, which requires three cases that need to be considered, in the following Figure 10, illustration.
Situation 1: If the deleted node does not have the right child, then choose its left child to replace the original node. The characteristics of the binary search tree ensure that the left subtree of the deleted node must in line with the characteristics of the binary search tree. Therefore, the value of the left subtree is either larger, either smaller than the value of the parent node of the deleted node, depending on the deleted node is the left child or the right child. Therefore, it is a characteristic that is fully compliant with the binary search tree with the left subtree of the deleted node is deleted.
Case 2: If the right child of the deleted node does not have left children, then this right child is used to replace the deleted node. Because the right child of the deleted node is greater than all nodes of the left subtree being removed. At the same time, it is also greater than or less than the parent node of the deleted node, which is also depends on the left child or the right child. Therefore, with the right child to replace the characteristics of the deleted node and meet the binary search tree.
Situation 3: Finally, if the right child of the deleted node has the left child, you need to replace it with the lower left node of the left subtree of the deleted node right, that is, we use the right child with the deleted node. The node of the minimum value is replaced. Note: We have to realize that in BST, the minimum node is always on the left, and the maximum node is always at the far right. Because the replacement selected a minimum number of nodes in the right subtree being removed, this node ensures that the node must be larger than all nodes of the left subtree being removed, but also ensures that it replaces the position of the deleted node, it All node values of the right subtree are greater than it. So this selection strategy is in line with the characteristics of the binary search tree.
Figure 10 describes the replacement options for three cases
Figure 10
Like search, insert algorithm, the runtime of the deletion algorithm is related to the topology of the BST. Ideally, the time complexity is log2 N, the worst case, is consumed by linear time. BST node traversal
For linear continuous array elements, the one-way iterative method is employed. Starting from the first element, sequentially iterates each element. The BST has three common traversal methods: 1, preorder traversal 2, inorder traversal 3, back sequence traversal)
Of course, these three traversal work is almost similar. They are all starting from the root node and then access their child nodes. The difference is that the sequence of access nodes itself and its sub-nodes are different from all over. To help understand, let's take a look at the BST tree shown in Figure 11. (Note Figure 6 and Figure 11 of the BST tree is identical. Figure 11
Pre-sequence traversal
The preference traversal starts from the current node (node c), then accesses his left child, and then access the right child. If the root node C from the BST tree, the algorithm is as follows: 1. Access C. (Here, you should refer to the value of the output node, add the node to ArrayList, or else elsewhere. This depends on the purpose of the BST.) 2, repeat the first step for C. 3, for C The right child repeats the first step;
The first step of the envisage algorithm printed the value of C. Take the BST tree shown in Figure 11 as an example, what is the value output by the pre-sequence traversal? Yes, we first output the value of the root node in the first step. Then perform the first step and output 50 on the left child of the root. Because the second step is to perform the first step repeatedly, it is accessed to the left child of the left child of the root node, and output 20. So repeated until the leftmost bottom layer of the tree. When the node 5 is reached, its value is output. Since there is no left, right child, we return to the node 20 and perform the third step. At this time, the first step of the node 20 is repeatedly executed, ie the output 25.25 does not have a child node, and returns to 20. But we have finished three steps to 20, so returns to node 50. The third step is performed again, that is, the first step is repeated to the right of 50. This process continues until all nodes of the trees are traversed. Finally, the results of the output traverses are as follows: 90, 50, 20, 5, 25, 75, 66, 80, 150, 95, 92, 111, 175, 166, 200
It can be understood that this algorithm is really a bit confused. Perhaps let's take a look at the code of the algorithm to clarify the idea. The following code is the preordraversal () method of the BST class, which is built behind the article. Note that this method calls an instance of the Node class as an output parameter. The output node is the node C mentioned in the algorithm step. Performance preamble is to call the PreordRraversal () method from the root node of the BST.
protected virtual string PreorderTraversal (Node current, string separator) {if (current = null!) {StringBuilder sb = new StringBuilder (); sb.Append (current.Value.ToString ()); sb.Append (separator);
Sb.Append (Current.Left, Separator); Sb.Append (current.right, separator); return sb.tostring ();} else returnction.empty;} (translation: actually this method It is a recursive call) Pay attention to the results traversed in the string, and this string is created via StringBuilder. First put the value of the current node into the string, then access the left and right children of the current node, put the result in the string.
Singular traversal
The secondary traversal is to start accessing from the left child of the current node, and then access the current node, and finally the right node. Assuming the root node of the BST tree is C, the algorithm is as follows: 1. Access the left child of C. (Here, you refer to the value of the output node, add the node to ArrayList, or else elsewhere. This depends on the purpose of the BST.) 2, repeat the first step to C; 3, the right child of C first step.
The code and preordraversal () method of the inordertraversal () method are similar, just before adding the current node value to the operation of StringBuilder, first check the method itself, and passes the left child of the current node as a parameter.
protected virtual string InorderTraversal (Node current, string separator) {if (! current = null) {StringBuilder sb = new StringBuilder (); sb.Append (InorderTraversal (current.Left, separator));
Sb.append (current.value.tostring ()); sb.append (separator);
Sb.Append (Current.right, Separator); Return Sb.Tostring ();} else returnction.empty;}
The BST tree shown in Figure 11 performs order traversal, the output is as follows: 5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200
It can be seen that the result is just ascended.
Rear sequence traversal
The sequence traversal first starts from the left child of the current node, and then the right child, and finally the current node itself. Assuming the root node of the BST tree is C, the algorithm is as follows: 1. Access the left child of C. (Here, you refer to the value of the output node, add the node to ArrayList, or elsewhere. This depends on the purpose of the BST.) 2, repeat the first step for C. 3, repeat of C first step;
The results of the BST Tree shown in Figure 11 are: 5, 25, 20, 66, 80, 75, 50, 92, 111, 95, 166, 200, 175, 150, 90)
Note: The downloads provided herein include the full source code for the BST and BinaryTree classes, as well as test applications for Windows Forms for the BST class. It is especially useful to pass the Windows application, you can see the results of the BST, order, and sequential traversal output.
These three traversal runtimes are linear. Because each traversal will access each node of the tree, and it is just a good access to each node. Therefore, the number of nodes of the BST tree is increased, and the time traversed will be multiplied. Implement BST class
Although Java's SDK includes a BST class (called TreeMap), but .NET Framework base library does not include this class. So we must create themselves. Like the binary tree, first create a Node class. We cannot use the Node class in the ordinary binary tree to simply reuse, as the node of the BST tree is comparable. Therefore, it is not only required node data to be Object type, but also requires data to implement the type type of IComparable interface.
In addition, the BST node needs to implement interface Icloneable because we must allow developers to clone Clone Clone Clone Clone Clon Clone (ie, depth copy). Make the Node Class Cable, then we can reach the purpose of clone the entire BST by returning the clone of the root node. The NODE class is as follows:
Public class node: iCloneable {Private ICMPARABLABLABLE DATA; Private Node Left, Right;
#Region Constructionors Public Node (): This (null) {} PUBLIC Node (iComparable Data): This (Data, Null, Null) {} public node (iComparable Data) {this.data = data; THIS.LEFT = Left; this.right = right;} #ENDREGON
#REGON PUBLIC METHODS PUBLIC Object Clone () {Node Clone = New Node (); if (Data Icloneable) Clone.Value = (iCloneable) ((iCloneable) DATA) .clone (); else clone.Value = data;
IF (Left! = null) clone.LEFT = (Node) Left.clone (); if (right! = null) clone.right = (node) Right.clone ();
Return clone;} #ENDREGION
#Region Public Properties Public iComparable Value {Get {Return Data;}}
Public node left;} set {left = value;}}
Public node right {get {Right = value;}} #ENDREGON}
Note that the BST's Node class is similar to the Node class of the binary tree. The only difference is that the type of data is the IComparable rather than the object type, and its Node class implements the ICLoneable interface, so the clone () method can be called. Now put the center of gravity into the BST class, it implements a binary search tree. In the following sections, we will introduce each of the main methods of this class. As for the complete code of the class, you can click Download the BinaryTrees.msi Sample File to download the source code, and test the Windows application for the BST class.
Search node
The reason why BST is important is that it provides a search algorithm time complexity than a linear time. Therefore, it is very meaningful to understand the Search () method. The Search () method receives an input parameter for an iComparable type, and a private method searchhelper () will also call the root node of BST and all search data.
Searchhelper () recursively call the tree. If the specified value is not found, return a null value, otherwise return the target node. The return result of the search () method is empty, indicating that the data to be found is not in the BST, otherwise the node equal to the DATA value is directed.
Public Virtual Node Search (iComparable Data) {Return Searchhelper (root, data);
Protected Virtual Node SearchHelper (Node Current, iComparable Data) {if (current == null) Return Null; // Node Was Not Found else {int result = current.value.comPareto (data); if (Result == 0) / / They is equal - We found the data return current; Else IF (Result> 0) {// Current.Value> N.Value // Therefore, if The Data EXISTS IT IN CURRENT'S LEFT SUBTREE RETURN SearchHelper (Current.Left, Data);} else // Result <0 {// Current.Value Add nodes to BST Unlike the BinaryTree class created in front, the BST class does not provide a method of direct access to roots. Nodes to BST can be added to the ADD () method of BST. Add () receives an instance class object that implements the IComparable interface as the value of the new node. Then look up the parent node of the new node in a way. (Recalling the content of the new leaf node mentioned earlier) Once the parent node is found, the size of the new node and the parent point value is compared to determine the new node as the left child of the parent node or the right child. Public Virtual Void Add (iComparable Data) {//first, create a new node n = new node (data); int result; // now, insert n rto the tree // trace Down the Tree Until We hit a null node Current = root, parent = null; while (current! = null) {result = current.value.comPareto (n.value); if (result == 0) // they is equal - Inserting a duplicate - do nothing return; Else if (Result> 0) {// Current.Value> N.Value // Therefore, N Must Be Added To Current's Left Subtree Parent = CURRENT; CURRENT = CURRENT.LEFT;} else IF (Result <0) {//// Current.Value // ok, at this point we have reached the end of the tree count ; if (parent == null) /// Tree Was Empty root = n; else {result = parent.value.compareto (n.value); if (Result> 0) // Parent.Value> n.value // therefore, n must beaded to pient's left subtree parent.Left = N; Else IF (Result <0) // Parent.Value The Search () method is to recursively on BST from top to bottom, and the add () method is using a simple loop. There are two ways to collect, but the recursive recursive in performance is more effective than using the While cycle. So we should recognize that the BST method can use these two methods - recursive or loops - any of them. (Individuals think that the recursive algorithm is more easy to understand.) Note: When the user tries to insert a duplicate node, the processing method of the add () method is to abandon the insertion operation, and you can modify the code as needed to throw an exception. Deleting a node from the BST in all operations of the BST, is the most complicated. Complexity lies that deleting a node must select a suitable node to replace breakage caused by deleting nodes. Note Selecting the alternative node must comply with the characteristics of the binary search tree. In the previous "Remove Node" section in the BST, we mentioned that the selection node has three cases of the deleted node, which has been summarized in Figure 10. Let's take a look at how the Delete () method is to determine these three situations. Public void delete (iComparable Data) {// Find N in the tree // Trace Down The Tree Until We Hit n node current = root, parent = null; int result = current.value.compareto (data); while (Result! = 0 && current! = Null) {if (Result> 0) {// Current.Value> N.Value // therefore, n must be added to current's left subtree parent = current; current = current.Left;} else (Result <0) {// Current.Value Result = current.value.compareto (data); // if current == null, Then We did not find the item to delete if (current == null) throw new exception ("item to be deleted does not exist in the bst."); // at this Point Current Is The Node To Delete, And Parent Is Its Parent Count -; // Case 1: IF Current Has No Right Child, Ten Current's Left Child Becomes The // Node Pointed to by The Parent IF (Current .Right == null) {if (parent == null) root = current.Left; else {result = parent.value.compareto (current.value); if (Result> 0) // Parent.Value> Current //// therefore, the parent's left subtree is now current's left subtree parent.Left = current.Left; else if (result <0) // parent.Value . S leftmost node else {// we need to find the right node's leftmost child Node leftmost = current.Right.Left, lmParent = current.Right; while (! Leftmost.Left = null) {lmParent = leftmost; leftmost = leftmost.Left;} // the parent's left subtree becomes the leftmost's right subtree lmParent.Left = leftmost.Right; // assign leftmost's left and right to current's left and right leftmost.Left = current.Left; leftmost.Right = Current.right; IF (parent == null) root = leftmost; else {result = parent.value.comPareto (current.value); if (Result> 0) // Parent.Value> Current // Therefore, The Parent's Left Subtree Is Now Current's right subtree parent.Left = leftmost; else if (result <0) // parent.Value Note: When you do not find the node that specifies the deleted, the delete () method throws an exception. Other BST methods and properties There are other BST methods and properties that are not introduced herein. We can download the complete source code included in this article to carefully analyze the BST class. The rest of the method includes: clear (): Dishes all nodes of the BST. Clon (): Clone BST (Create a depth copy). Contains: Returns a Boolean value to determine if there is a node that is specified by the specified data in the BST. GetEnumerator (): Enumerate the BST node with the neutral overhead algorithm and returns the number of enumerated. This method allows BST to cycle itself through the Foreach. Preordertraversal () / inordertraversal () / PostOrDertraversal (): In the "Traverse BST Node" section, it has been introduced. TOSTRING (): Use the BST-specific traversal algorithm to return the representation result of the character. Count: Public read-only properties returns the number of nodes of BST. The real world's binary search tree two-search tree is ideal for insertion, search, and delete operations in time complexity below linear time, and this time complexity is related to the topology of BST. In the "Insert Node to BST" section, we mention that the topology is related to the order of the insertion nodes. If the inserted data is ordered, or approximately orderly, it will cause the BST tree to become a deep and narrow, not a shallow and wide tree. In many reality, the data is in an ordered or approximate state. The problem with the BST tree is easy to become uneven. Balanced binary tree refers to the ratio of width and depth is optimized. In this series of articles, a special BST class is self-balanced. That is, whether it is to add a new node or delete an existing node, BST will automatically adjust its topology to maintain the best equilibrium. The most ideal equilibrium state is the insertion, search, and deletion time complexity is also log2 n in worst case. I mentioned the BST class called Treemap in Java SDK. This class is actually derived from a BST tree that is self-balanced - red-black tree. In the next part of this series, we will introduce this self-balanced BST tree, including a red-haired tree. Focusing on a data structure that becomes Skiplist. This structure reflects the performance of self-balanced binary trees, and does not need to be reconstructed. Let's get here, enjoy the fun of programming!
