define
Binary Search Tree (BST), also known as Binary sort Tree or Binary Search Tree.
Compared with ordinary binary trees, non-empty binary search trees have the following properties:
- All keys of a non-empty left subtree are less than those of its root node;
- All keys of a non-null right subtree are greater than those of its root node;
- The left and right subtrees are binary search trees.
- There are no nodes in the tree with equal keys.
As you can see, binary search trees have very distinct properties, which makes binary trees also practical.
Common operations on binary search trees
For binary search trees, in addition to the regular four traversal, there are also some key operations worth our attention.
Binary tree storage structure implementation
For binary trees, we still choose to implement the chain storage structure.
Binary tree node definition
The most important feature of binary search tree is that its elements can be compared in size. This is something to be aware of.
/** * Created by engineer on 2017/10/26. * * binary search tree definition */
public class TreeNode<T extends Comparable<T>> {
/ / data domain
private T data;
/ / the left subtree
public TreeNode<T> leftChild;
/ / right subtree
public TreeNode<T> rightChild;
public TreeNode(T data) {
this(null, data, null);
}
public TreeNode(TreeNode leftChild, T data, TreeNode rightChild) {
this.leftChild = leftChild;
this.data = data;
this.rightChild = rightChild;
}
public T getData(a) {
return data;
}
public TreeNode<T> getLeftChild(a) {
return leftChild;
}
public TreeNode<T> getRightChild(a) {
return rightChild;
}
public void setData(T data) {
this.data = data; }}Copy the codeBinary search tree insertion
With the root node, we can build a binary tree from the root node according to the properties of the binary tree.
/** * insert element ** into the tree@param value
*/
void insert(T value) {
if (value == null) {
return;
}
root = insert(root, value);
}
private TreeNode<T> insert(TreeNode<T> node, T value) {
if (node == null) {
// If the tree is empty, the root node is created
return new TreeNode<>(value);
} else {
if (compare(node, value) < 0) { // The insertion value is smaller than the root node, and the binary search tree continues in the left subtree
node.leftChild = insert(node.getLeftChild(), value);
} else if (compare(node, value) > 0) { // Insert value larger than root node, continue to create binary search tree in right subtreenode.rightChild = insert(node.getRightChild(), value); }}return node;
}
private int compare(TreeNode<T> node, T value) {
return value.compareTo(node.getData());
}Copy the codeAccording to the characteristics of binary search tree, we can easily use recursion to achieve binary tree insertion operation; So basically, you insert one node at a time, starting from the root, and you insert the smaller nodes into the left subtree, and the larger ones into the right subtree. This is exactly the same as the binary search tree definition.
We can simply test the validity of this insert method.
Test binary search tree insertion operations
Public class BinarySearchTreeTest {private static Integer[] arrays = new Integer[]{10, 8, 3, 12, 9, 4, 5, 7, 1,11, 17}; public static void main(String[] args) { BinarySearchTree<Integer> mSearchTree = new BinarySearchTree<>();for(Integer data : arrays) { mSearchTree.insert(data); } // Print three traversal sequences for binary trees msearchtree.printtree (); }}Copy the codeTree traversal is already inAbove,Detailed analysis, no further discussion here
Here we define a random array of numbers, which inserts the array in order into the tree and prints the tree according to the tree’s three traversal structures. Using this array we will build a binary search tree as shown below:
Take a look at the traversal result of the program’s output.
The first order traversal: 10 8 3 1 4 5 7 9 12 11 17 Middle order traversal: 1 3 4 5 7 8 9 10 11 12 17 The last order traversal: 17 5 4 3 9 8 11 17 12 10Copy the codeAs you can see, the traversal results are consistent with the binary tree we drew, so you can verify that the insertion method is correct.
To find the
Now that we have implemented a binary search tree by insertion, let’s look at how to find elements from the tree.
- Find maximum and minimum values
According to the characteristics of binary search tree, we know that in a binary search tree, the minimum value must be on the very left node, and the maximum value must be on the very right node. Therefore, finding the maximum value of the binary tree becomes very easy.
/** * find the maximum value **@return* /
public T findMax(a) {
if (isEmpty()) return null;
return findMax(root);
}
/** * Start at a specific node to find the maximum **@param node
* @return* /
private T findMax(TreeNode<T> node) {
TreeNode<T> temp = node;
while(temp.getRightChild() ! =null) {
temp = temp.getRightChild();
}
return temp.getData();
}
/** * find the minimum value **@return* /
public T findMin(a) {
if (isEmpty()) return null;
return findMin(root);
}
/** * Find the minimum value ** from a particular node@param node
* @return* /
private T findMin(TreeNode<T> node) {
TreeNode<T> temp = node;
while(temp.getLeftChild() ! =null) {
temp = temp.getLeftChild();
}
return temp.getData();
}Copy the codeAs you can see, the implementation of the algorithm is very simple, just keep moving back and forth to find the node that doesn’t have a subtree, which is the node at the boundary.
- Finding a specific value
How do you quickly find a node whose value is a particular element in a binary search tree? How do we implement node insertion? That’s a very simple question.
Recursive implementation, looking for a particular node
**
/** * find specific value recursive implementation **@param value
* @return* /
public TreeNode<T> find(T value) {
if (isEmpty()) {
return null;
} else {
returnfind(root, value); }}private TreeNode<T> find(TreeNode<T> node, T value) {
if (node == null) {
// Throws an exception when looking for an element that is not in the tree
throw new RuntimeException("the value must not in the tree");
}
if (compare(node, value) < 0) {
// If the value is smaller than the root node, go to the left subtree
return find(node.getLeftChild(), value);
} else if (compare(node, value) > 0) {
// If the root node is larger than the root node, search from the right subtree
return find(node.getRightChild(), value);
} else {
// Just equal to, found
return node;
// There is only one case left, that is, the element is not in the tree}}Copy the codeThe implementation of the search idea, on the whole and insert is the same; It’s just doing different things; The important thing to note here is that for the robustness of the program, we also have to consider what happens if the element we are looking for is not in the tree.
Iterative implementation, looking for specific values
With our previous experience of finding minimum and maximum values, we can also consider implementing an iterative algorithm to find a given element.
/** * find a specific value - non-recursive implementation **@param value
* @returnNode * /
public TreeNode<T> findIter(T value) {
TreeNode<T> current = root;
while(current ! =null) {
if (compare(current, value) < 0) {
current = current.getLeftChild();
} else if (compare(current, value) > 0) {
current = current.getRightChild();
} else {
returncurrent; }}// If current is null, the element is not in the tree
return null;
}Copy the codeHere is also a test to find the correct method:
System.out.printf("\nfind value %d in mSearchTree \n".12);
TreeNode mTreeNode = mSearchTree.find(12);
TreeNode mTreeNode_1 = mSearchTree.findIter(12);
System.out.println("Recursive implementation node = :" + mTreeNode + ", value=" + mTreeNode.getData());
System.out.println("Non-recursive implementation node = :" + mTreeNode_1 + ", value=" + mTreeNode_1.getData());
System.out.println("\nfind the max value in mSearchTree = " + mSearchTree.findMax());
System.out.println("find the min value in mSearchTree = " + mSearchTree.findMin());Copy the codeOutput:
find value 12 inMSearchTree recursive implementation node = : com. Avaj. Datastruct. Tree. The BST. 4 b67cf4d TreeNode @, Value = = 12 non-recursive implementation nodes: com. Avaj. Datastruct. Tree. The BST. 4 b67cf4d TreeNode @, value = 12, find the Max valuein mSearchTree = 17
find the min value in mSearchTree = 1Copy the codeWe find 12 recursively and iteratively. We find the same object twice. The value of this object is 12. The maximum and minimum values found are also correct; So the implementation of the lookup function is correct.
Delete nodes
Deleting a node from a binary search tree is probably the most complicated operation, mainly because the node that you want to delete, the location of the node that you want to delete, you still need to keep the whole tree binary, so you need to analyze different situations.
For the binary tree we created above, it’s easy to delete leaves like 1,7,11, and 17; Let its parent point to null; If you have four, five nodes that have a subtree in them, in other words, it’s a one-way list, and it’s easier to delete one node from the middle of the one-way list; And the trouble is that if we want to delete nodes 10,8,3, and 12 which have left and right subtrees, we have to replace that with a maximum from the left subtree, or a minimum from the right subtree. To summarize the operation of deleting a node:
- Leaf node: delete directly, its parent pointing to null
- Nodes that contain a child: the parent points to the parent node of the node to be deleted (equivalent to deleting an element in the middle of the list);
- Nodes containing left and right subtrees: the right subtree minimum or left subtree maximum replaces this node
Combined with the above analysis, the realization of deleting nodes from binary search tree is obtained.
/** * removes the specified node ** whose value is value from the tree@param value
*/
public void delete(T value) {
if (value == null || isEmpty()) {
return;
}
root = delete(root, value);
}
private TreeNode<T> delete(TreeNode<T> node, T value) {
// The node is empty and the element to be deleted is not in the tree
if (node == null) {
return node;
}
if (compare(node, value) < 0) { // Go to the left subtree to delete
node.leftChild = delete(node.getLeftChild(), value);
} else if (compare(node, value) > 0) { // Go to the right subtree to delete
node.rightChild = delete(node.getRightChild(), value);
} else { // Delete the current node
if(node.getLeftChild() ! =null&& node.getRightChild() ! =null) {// The node to be deleted contains the left and right subtrees
T temp = findMin(node.getRightChild()); // Get the minimum of the right subtree
node.setData(temp); // Replace the current node with the minimum right subtree value
node.rightChild = delete(node.getRightChild(), temp); // Remove the minimum node from the right subtree
} else {// The node to be deleted contains one or no subtrees
if(node.getLeftChild() ! =null) {
node = node.getLeftChild();
} else{ node = node.getRightChild(); }}}return node;
}Copy the codeWe chose to use the minimum of the right subtree because it would be easier to remove the minimum node, because it must not be a node that contains the left and right subtrees.
Again, here’s a test of deleting a node:
// Delete the node with only one subtree
mSearchTree.delete(4);
mSearchTree.printTree();
System.out.println();
// Delete the root node with left and right subtrees
mSearchTree.delete(10);
mSearchTree.printTree();Copy the codeOutput:
10 8 3 1 5 7 9 12 11 17 middle order traversal: 1 3 5 7 8 9 9 10 11 12 17 middle order traversal: 17 5 3 9 8 11 17 12 10 middle order traversal: 17 5 3 9 8 11 17 12 10 middle order traversal: 11 8 3 1 5 7 9 12 17 1 3 5 7 8 9 11 12 17 after traversal: 17 5 3 9 8 17 12 11Copy the codeAnd by comparing it to the tree that we drew at the beginning, it corresponds.
The height of the binary search tree
Finally, let’s see how to calculate the degree of a binary search tree.
public int getTreeHeight(a) {
if (isEmpty()) {
return 0;
}
return getTreeHeight(root);
}
private int getTreeHeight(TreeNode<T> node) {
if (node == null) {
return 0;
}
int leftHeight = getTreeHeight(node.getLeftChild());
int rightHeight = getTreeHeight(node.getRightChild());
int max = leftHeight > rightHeight ? leftHeight : rightHeight;
// Get the larger return in the left and right subtrees.
return max + 1;
}Copy the codeAnd let’s figure out, by the way, what the height of the tree that we created at the end of the day was after the insertion and deletion.
System.out.println("\n\nTree's height =" + mSearchTree.getTreeHeight());Copy the codeOutput:
Tree's height =5Copy the codeAs you can see, the tree has 5 levels instead of 6 because node 4 has been deleted.
Well, that’s all for binary search tree analysis! All source code addresses in the article.