binary treeIt is a very important type of data structure that isset upof a kind, but each node of theThere can be no more than two child nodes, which can be 0, 1, or 2 children, with 0 children representing no children. A common binary tree structure is shown below:
Each node has no more than two children, where 3, 4, and 5 have no children, 2 has one child, and 0 and 1 both have two children.
basic concept
root node: The factual node of the tree, which has no parent.
leaf node: Nodes that have no children are called leaf nodes.
Node depth: The distance from the root node to that node is called the depth, as in the above figure: the depth of node 3 is 2 and the depth of node 1 is 1.
Node height: The distance from this node to the leaf node with the longest distance.
binary lookup tree
One of the most important applications of the binary tree is in the query application, many of the index structure is a binary lookup tree, as well as to the HashMap also used to the red-black tree, red-black tree is also a binary lookup tree. A binary lookup tree is aNature of importanceThat is, any node that has a node in its left subtree that is smaller than that node and a node in its right subtree that is larger than that node. Our example diagram at the beginning is not a binary lookup tree; it does not fulfill the properties we just described. Let's look at the following example diagram:
This is a binary lookup tree that has any node whose children are smaller than that node and nodes in the right subtree that are larger than that node. So that we are looking for data, we can start from the root node to find, if the value of the search is less than the node, go to the left subtree to find, if it is greater than the node, go to the right subtree to find, if it is equal to, then it goes without saying, directly return to it. This kind of can greatly improve our finding efficiency, its time complexity is O(logN).
hand-crafted binary lookup tree
First we have to abstract thenodal categoryEach node can have a left child node, and right child node, of course, the node to store a value, the value of the value of the type we do not do not limit, it can be a digital type, can be a string, can also be their own definition of the class, but here we need to add a prerequisite, that is, the value of the value is comparable, because the two nodes compared to determine the location of the node value of the type of the node to realize theComparableInterface. Well, fulfilling the above conditions, we can abstract the class of binary tree nodes as follows:
public class BinaryNode<T extends Comparable<T>> {
//Node data
@Setter@Getter
private T element;
//left child node (math.)
@Setter@Getter
private BinaryNode<T> left;
//right child node (math.)
@Setter@Getter
private BinaryNode<T> right;
//constructor
public BinaryNode(T element) {
this(element,null,null);
}
//constructor
public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
if (element == null) {
throw new RuntimeException("A binary tree node element cannot be empty");
}
= element;
= left;
= right;
}
}
We define the class of a binary tree node asBinaryNode, let's pay attention to the later generalization, which has to implement theComparableInterface. Then we define the node dataelementleft child nodeleftand right child nodesrightand use the@Setter@Getterannotation to implement its set and get methods. The next step is to define two constructor methods, one that passes only the node's elements, and the other that passes the node's elements and the left and right subtrees. The node's elements cannot be null, and if they are null then an exception is thrown.
Then, we then define the binary lookup tree class, the class includes some of the basic operation methods of the binary lookup tree, these basic operation methods we will talk about later, first look at the definition of the basic elements, as follows:
public class BinarySearchTree<T extends Comparable<T>> {
//root node
private BinaryNode<T> root;
public BinarySearchTree() {
= null;
}
//Turning a tree into an empty tree
public void makeEmpty() {
= null;
}
//Determine if the tree is empty
public boolean isEmpty() {
return == null;
}
}
The class name is defined as:BinarySearchTree, again, let's note the generalization here, it's the same as theBinaryNodeis the same as the generalization of the type we pass to theBinaryNode. The class defines the root node of the treeroot, and the constructor method, which simply defines an empty tree with an empty root node. Then there are two more basic tree manipulation methodsmakeEmptycap (a poem)isEmpty, turning the tree into an empty tree and determining whether the tree is empty.
- Now it's time to write some tree manipulation methods, and the first thing we're going to write is the
containsmethod, it will determine whether the tree contains an element, such as the above example, we determine whether the tree contains the element 3. The implementation is as follows:
/**
* Whether the binary tree contains an element
*
* @param element Elements inspected
* @return true or false
*/
public boolean contains(T element) {
return contains(root, element);
}
/**
* Whether the binary tree contains an element
*
* @param tree Whole tree or left and right sub-trees
* @param element Elements inspected
* @return true or false
*/
private boolean contains(BinaryNode<T> tree, T element) {
if (tree == null) {
return false;
}
int compareResult = (());
if (compareResult > 0) {
return contains((), element);
}
if (compareResult < 0) {
return contains((), element);
}
return true;
}
Here we define twocontainsmethod, the firstcontainsmethod calls the secondcontainsmethod, the secondcontainsmethods are private and cannot be accessed externally. After calling the secondcontainsmethod, we pass in root, which is the whole tree to look up. In the secondcontainsmethod, we first determine whether the tree is empty, if it is empty, certainly will not contain the element we want to find, then directly return false. then we use the elements found and the current node's elements for comparison, here we use thecompareTomethod, which isComparablemethods defined in the interface, which is what we're trying to achieve when we define the genericComparableThe reason for the interface. The result of the comparison is greater than 0, which means that the found value is greater than the current node value, and we recursively call thecontainsmethod, passing in the right subtree and the value of the lookup; the comparison result is less than 0, indicating that the value of the lookup is less than the value of the current node, we also recursively call thecontainsmethod, which passes in the left subtree and the value of the lookup for the lookup. Finally, if the comparison result is equal to 0, it means that the value of the lookup is the same as the value of the current node, and we return true.
containsmethod is an appetizer of sorts, where recursion is used, which gives us a primer on how binary trees are written.
- The next thing we're going to write is
findMincap (a poem)findMaxmethods, respectively, to find the minimum and maximum values in the tree. Since our tree is a binary lookup tree, the value of the left subtree is going to be less than the current node and the value of the right subtree is going to be greater than the current node, so the value of the leftmost node is the minimum value, and the rightmost value is the maximum value. Let's implement this in code.
/**
* Find the smallest element of a binary tree
*
* @return
*/
public T findMin() {
if (isEmpty()) throw new RuntimeException("The binary tree is empty");
return findMin(root);
}
private T findMin(BinaryNode<T> tree) {
if (() != null) {
return findMin(());
}
return ();
}
/**
* Find the largest element of a binary tree
*
* @return
*/
public T findMax() {
if (isEmpty()) throw new RuntimeException("The binary tree is empty");
return findMax(root);
}
private T findMax(BinaryNode<T> tree) {
while (() != null) {
tree = ();
}
return ();
}
Let's start withfindMinmethod, which first determines whether the tree is empty; an empty tree has no minimum or maximum value, so we throw an exception here. Then we pass the whole tree into the secondfindMinmethod in the secondfindMinmethod, we have been to find the left child node, if the left child node is not empty, we recursively go back to the search, until the node's left child node is empty, then the current node is the leftmost node of the whole tree, then its value is the smallest, we return on it.
Let's look at it again.findMaxmethod, andfindMinThe method is the same, first determining whether the tree is empty, and then throwing an exception if it is. We're going to focus on the secondfindMaxmethod, in this method, instead of using recursion to find the rightmost node, we have used a while loop to find the rightmost node. Here we have used two different methods to implement thefindMincap (a poem)findMaxOne uses recursion and the other uses a while loop. In fact, these two approaches are also interchangeable, and methods that can be used with recursion can also be implemented with a while loop, and vice versa.
- Next we'll look at a very important method for binary lookup trees, which is the
insertInsertion method. When we add a node to the binary lookup tree, and the current node to do a comparison, if less than the current node value, then inserted in the left side, if greater than the right side of the insertion, here we do not discuss the case of equal. Specific code is as follows:
/**
* inserted element
*
* @param element
*/
public void insert(T element) {
if (root == null) {
root = new BinaryNode<>(element);
return;
}
insert(root, element);
}
private void insert(BinaryNode<T> tree, T element) {
int compareResult = (());
if (compareResult > 0) {
if (() == null) {
(new BinaryNode<>(element));
} else {
insert((), element);
}
}
if (compareResult < 0) {
if (() == null) {
(new BinaryNode<>(element));
} else {
insert((), element);
}
}
}
In the process of inserting nodes, we first determine whether the root node is empty, if it is empty, that is, an empty tree, we directly insert the elements to the root node can be. If the root node is not empty, we go to the second insert method, in the second insert method, we first insert the value and the current node to do a comparison, compare the results if greater than 0, the value of the inserted value than the current node is larger than the current node, so we have to insert the right side, if the current node of the right node of the node is empty, we directly insert on it; if the right node is not empty, but also with the If the right child node is not empty, we have to compare it with the right child node, here we use the recursive method to achieve a clearer logic. Similarly, if the result of the comparison is less than 0, we can do the operation of the left node, no more details here.
- Above we did the insertion of nodes, and finally the deletion of nodes
remove. To delete a node, first we have to find the node and after finding the node, we have to process the node in different cases as follows:
- Deleting a node with no children: we delete the node directly, that is, we set the node to null;
- Deleting a node with only left or right child nodes: In this case of only one child node, we can just change the node to be deleted to its only child node. This is equivalent to overwriting the current node with a child node;
- Delete the node has two children: this is the most complex case, to solve this problem, we still have to use the characteristics of the binary lookup tree, that is, the current node's left subtree of the value of the current node are smaller than the current node, the right subtree of the value of the current node than the value of the current node. So we remove the current node, which node to replace the current node? Here we can find the largest value in the left subtree, or from the right subtree to find the smallest value, instead of the current node to be deleted. After this replacement, we can still ensure that the value of the left subtree is smaller than the current value, and the value of the right subtree is larger than the current value. Then we replace the value, that is, the maximum value of the left subtree, or the minimum value of the right subtree, in the left or right subtree can be deleted. The logic of this paragraph is more rounded, partners can read a few times to understand. Specific implementation is as follows:
/**
* Delete element
* @param element
*/
public void remove(T element) {
remove(root, element);
}
private void remove(BinaryNode<T> tree, T element) {
if (tree == null) {
return;
}
int compareResult = (());
if (compareResult > 0) {
remove((), element);
return;
}
if (compareResult < 0) {
remove((), element);
return;
}
if (() != null && () != null) {
(findMin(()));
remove((), ());
} else {
tree = () != null ? () : ();
}
}
The first remove method does not say, we focus on the second. Methods come in, whether the node is empty, is empty means that the empty tree, or to delete the node is not found, then directly return to it. Then use the deleted elements and the current node for comparison, if greater than 0, we use the recursive method in the right subtree to continue to implement the deletion method. Similarly, if less than 0, the left subtree recursion. Then the following is equal to the case of 0, that is, to find the node to be deleted. We first deal with the most complex case, that is, the deletion of the node of the left and right child nodes exist, we use the above logic, using the right subtree of the smallest node to cover the current node, and then in the right subtree, the value of the deletion, we also recursively call the remove method. Of course, you can also use the maximum value in the left subtree here, guys realize it yourself. Finally is to deal with no child nodes and only one child node, these two cases in the code can be merged, if the left child node is not empty, use the left child node to cover off the current node, otherwise use the right child node to cover. If the right child node is also empty, that is, there is no child node, then the current node also becomes empty.
concern
This is the end of the basic binary lookup tree operation. This leads to the question, if we sequentially insert 1, 2, 3, 4, 5 into a tree, what will be the shape of the tree? This is not difficult to imagine, as follows:
There is no difference between this and a chained table. The performance of the lookup is the same as that of a chained table, and is not improved. This leads to the next article: balanced binary tree, guys, stay tuned~~~