Terms:
A Binary Tree is a special type of Tree in which each node has at most two children. The two children are called left children and the other right children
A Binary Search Tree is a Binary Tree in which, for each node x, the values of all descendants of the left subtree are always less than the value of X, and the values of all descendants of the right subtree are always greater than the value of X
A binary search tree
1. Basic implementation:
In general, BST records data as key-value pairs. For simplicity, this article uses string as the type of the key and Value as the type of the Value (Value is a generic type specified when the tree is created). If you’re interested, look at Algorithms, Fourth Edition.
public class BST<Value> {
private Node root;
private class Node{
private String key;
private Value value;
private Node left;
private Node right;
Node(String key,Value value){this.key=key;this.value=value;}
}
/* For some methods of binary search tree, see below */
// Add a node
public void add(String key,Value value){}
// Get values based on keys
public Value get(String key){return 0; }// Get the node with the smallest key
public Node min(a){return null; }// Get the node with the largest key
public Node max(a){return null; }// Delete a node
public void delete(String key){}
// Middle order traversal of binary tree
public Iterable<String> inorderTraverse(a){return null;}
}
Copy the codeSelect * from key;
Find records by key. If the tree contains the key, the lookup hit, returns the value of the key; If not, the search is not hit and null is returned
// Get values based on keys
public Value get(String key){
return get(root,key);
}
private Value get(Node x,String key){
// Find the key in the tree with node X as the root
Return the value of the key if it can be found, or null if it cannot be found
if(x==null) return null; // If the current node is null, null is returned
int cmp=key.compareTo(x.key); // Compare the key of the current node with that of the node to be found
if(cmp>0) return get(x.right,key); // Continue the search in the right subtree of the current node
else if(cmp<0) return get(x.left,key); // Continue the search in the left subtree of the current node
else return x.value; // If the two keys are equal, the search is hit
}
Copy the codeInsert key pair:
Give a key-value pair. If the key is not in the tree, create a new node and hang it on the empty link at the end of the search. If the key exists in the tree, the corresponding value is updated
// Insert a new node
public void add(String key,Value value){
root=add(root,key,value);
}
private Node add(Node x,String key,Value value){
// Insert node in tree with x node as root
if(x==null) return new Node(key,value); // if x is empty, the leaf node of the tree has been reached
// Create a new key node and hang it on an empty link
int cmp=key.compareTo(x.key); // Compare the node to be inserted with the key of node X
if(cmp>0) x.right=add(x.right,key,value); // Insert nodes in the right subtree of x
else if(cmp<0) x.left=add(x.left,key,value); // Insert a node in the left subtree of x
else x.value=value; // The tree already has a node corresponding to the key
return x; // Return a reference to node x;
}
Copy the codeObtain the node with the smallest key:
If the left link of the root node is empty, the smallest node in the tree is the root node
If the left link of the root node is not empty, then the smallest node in the left subtree of the root node is the smallest node in the whole tree
So we can recursively find the smallest node
The algorithm for obtaining the maximum node is similar, except for the right subtree of the recursive node
// Get the node with the smallest key
public Node min(a){
return min(root);
}
private Node min(Node x){
if(x.left==null) return x;
return min(x.left);
}
Copy the codeDelete the node with the smallest key:
// Delete the node with the smallest key
public void deleteMin(a){
if(root==null) return;
root=deleteMin(root);
}
private Node deleteMin(Node x){
if(x.left==null) x=x.right; // If the left child of x is empty, x is the smallest node to be deleted
// Assign the x reference (the left link of the parent node of X) to the right child node of X
// The original node is garbage collected because there is no reference to it
else x.left=deleteMin(x.left);
return x;
}
Copy the code6. Delete any node:
The algorithm for deleting nodes in a binary tree based on keys is complex, and the basic steps are as follows:
- Find the node you want to delete and point to it using the temporary variable t
- Find the smallest node in the right subtree of node T and point to that node using the temporary variable x
- Use the deleteMin method to delete the smallest node in the t right subtree and restore the right subtree
- The left link of x goes to the left subtree of T, and the right link of x goes to the right subtree of T
- Connect x to the parent of T
// Delete a node
public void delete(String key){
root=delete(root,key);
}
private Node delete(Node x,String key){
if(x==null) return null; // The node whose key is key is not found
int cmp=key.compareTo(x.key);
if(cmp>0) x.right=delete(x.right,key); // Remove the node from the left node of x
else if(cmp<0) x.left=delete(x.left,key); // Remove the node from the right node of x
else{
if(x.right==null) return x.left;
if(x.left==null) return x.right;
Node t=x;
x=min(t.right);
x.right=deleteMin(t.right); // Delete the smallest node in the right subtree of t and restore the right subtree
x.left=t.left;
}
return x;
}
Copy the code7. Perform middle-order traversal on the binary search tree
A middle-order traversal of a binary lookup tree yields a collection of nodes ordered by key
Code that iterates recursively is not complex
// Middle order traversal of binary tree
public List<Node> inorderTraverse(a){
List<Node> list=new ArrayList<>();
inorderTraverse(root,list);
return list;
}
private void inorderTraverse(Node x,List<Node> list){
if(x==null) return;
inorderTraverse(x.left,list);
list.add(x);
inorderTraverse(x.right,list);
}
Copy the code8. Print the binary lookup tree in the console
public void print(a){
System.out.println("* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *");
print(root,0);
System.out.println("* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *");
}
private void print(Node x,int floor){
if(x==null) return ;
print(x.left,floor+1);
for (int i = 0; i < floor; i++) {
System.out.print("--");
}
System.out.println(x.key+""+x.value);
print(x.right,floor+1);
}
Copy the codeTest cases
In the example, the key is of type String and the value is of type Integer. The test case accepts adding data on the console in the form of $add String. String is the key, and the corresponding value is the order in which the strings are added, $del string for delete, $show for print, and $exit for exit
public static void main(String[] args) {
BST<Integer> sibst = new BST<>();
int i=1;
String str;
boolean flag=true;
Scanner in = new Scanner(System.in);
String[] words;
while(flag){
str=in.nextLine();
if(str.equals("")) continue;
words = str.split("");
switch (words[0]) {case "$exit": {
flag=false;
break;
}
case "$add":{
sibst.add(words[1],i++);
break;
}
case "$del":{
sibst.delete(words[1]);
break;
}
case "$show":{
sibst.print();
break;
}
default:{
System.out.println("Error command"); }}}}Copy the code10. Complete code
BST.java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class BST<Value> {
private Node root;
private class Node{
private String key;
private Value value;
private Node left;
private Node right;
Node(String key,Value value){
this.key=key;
this.value=value; }}// Add a node
public void add(String key,Value value){
root=add(root,key,value);
}
public Node add(Node x,String key,Value value){
// Insert node in tree with x node as root
if(x==null) return new Node(key,value); // if x is empty, the leaf node of the tree has been reached
// Create a new key node and hang it on an empty link
int cmp=key.compareTo(x.key); // Compare the node to be inserted with the key of node X
if(cmp>0) x.right=add(x.right,key,value); // Insert nodes in the right subtree of x
else if(cmp<0) x.left=add(x.left,key,value); // Insert a node in the left subtree of x
else x.value=value; // The tree already has a node corresponding to the key
return x; // Update node x;
}
// Get values based on keys
public Value get(String key){
return get(root,key);
}
private Value get(Node x,String key){
// Find the key in the tree with node X as the root
Return the value of the key if it can be found, or null if it cannot be found
if(x==null) return null; // If the current node is null, null is returned
int cmp=key.compareTo(x.key); // Compare the key of the current node with that of the node to be found
if(cmp>0) return get(x.right,key); // Continue the search in the right subtree of the current node
else if(cmp<0) return get(x.left,key); // Continue the search in the right subtree of the current node
else return x.value; // If the two keys are equal, the search is hit
}
// Get the node with the smallest key
public Node min(a){
return min(root);
}
private Node min(Node x){
if(x.left==null) return x;
return min(x.left);
}
// Delete the node with the smallest key
public void deleteMin(a){
if(root==null) return;
root=deleteMin(root);
}
private Node deleteMin(Node x){
if(x.left==null) x=x.right;
else x.left=deleteMin(x.left);
return x;
}
// Get the node with the largest key
public Node max(a){
return null;
}
// Delete a node
public void delete(String key){
root=delete(root,key);
}
private Node delete(Node x,String key){
if(x==null) return null; // The node whose key is key is not found
int cmp=key.compareTo(x.key);
if(cmp>0) x.right=delete(x.right,key); // Remove the node from the left node of x
else if(cmp<0) x.left=delete(x.left,key); // Remove the node from the right node of x
else{
if(x.right==null) return x.left;
if(x.left==null) return x.right;
Node t=x;
x=min(t.right);
x.right=deleteMin(t.right);
x.left=t.left;
}
return x;
}
// Middle order traversal of binary tree
public List<Node> inorderTraverse(a){
List<Node> list=new ArrayList<>();
inorderTraverse(root,list);
return list;
}
private void inorderTraverse(Node x,List<Node> list){
if(x==null) return;
inorderTraverse(x.left,list);
list.add(x);
inorderTraverse(x.right,list);
}
public void print(a){
System.out.println("* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *");
print(root,0);
System.out.println("* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *");
}
private void print(Node x,int floor){
if(x==null) return ;
print(x.left,floor+1);
for (int i = 0; i < floor; i++) {
System.out.print("--");
}
System.out.println(x.key+""+x.value);
print(x.right,floor+1);
}
public static void main(String[] args) {
BST<Integer> sibst = new BST<>();
int i=0;
String str;
boolean flag=true;
Scanner in = new Scanner(System.in);
String[] words;
while(flag){
str=in.nextLine();
if(str.equals("")) continue;
words = str.split("");
switch (words[0]) {case "$exit": {
flag=false;
break;
}
case "$add":{
sibst.add(words[1],i++);
break;
}
case "$del":{
sibst.delete(words[1]);
break;
}
case "$show":{
sibst.print();
break;
}
default:{
System.out.println("Error command");
}
}
}
}
}
Copy the code