Binary Search Tree (Binary Search Tree) is an algorithm that combines the flexibility of linked list insertion with the efficiency of ordered array search. The following is the pure code for implementing various methods of BST.
Binary search tree (BST) definition
Binary sorting tree is either an empty tree, or It is a binary tree with the following properties:
If the left subtree is not empty, then the values of all nodes on the left subtree are Less than or equal to The value of its root node
If the right subtree is not empty, then right subtree The values of all nodes on are greater than or equal to the value of its root node
The left and right subtrees are also Respectively for the binary sorting tree
basic node implementation
public class BST<K extends Comparable<K>, V> {
private Node root;
private class Node {
private K key;
private V value;
private Node left;
private Node right;
private int N;
public Node(K key, V value, int N) {
this.key = key;
this.value = value;
this.N = N;
}
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null)
return 0;
else
return x.N;
}
}Copy after login
find the key to get the value—— get
public V get(K key) {
return get(root, key);
}
private V get(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp == 0)
return root.value;
else if (comp < 0)
return get(root.left, key);
else
return get(root.right, key);
}Copy after login
Modify value/insert new value——put
public void put(K key, V value) {
root = put(root, key, value);
}
private Node put(Node root, K key, V value) {
if (root == null)
return new Node(key, value, 1);
int comp = key.compareTo(root.key);
if (comp == 0)
root.value = value;
else if (comp < 0)
root.left = put(root.left, key, value);
else
root.right = put(root.right, key, value);
root.N = size(root.left) + size(root.right) + 1;
return root;
}Copy after login
Maximum value/Minimum value——min/max
public K min() {
return min(root).key;
}
private Node min(Node root) {
if (root.left == null)
return root;
return min(root.left);
}Copy after login
public K max() {
return max(root).key;
}
private Node max(Node root2) {
if (root.right == null)
return root;
return max(root.right);
}Copy after login
Round up/down——floor/ceiling
public K floor(K key) {
Node x = floor(root, key);
if (x == null)
return null;
return x.key;
}
private Node floor(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp < 0)
return floor(root.left, key);
else if (comp > 0 && root.right != null
&& key.compareTo(min(root.right).key) >= 0)
return floor(root.right, key);
else
return root;
}Copy after login
public K ceiling(K key) {
Node x = ceiling(root, key);
if (x == null)
return null;
return x.key;
}
private Node ceiling(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp > 0)
return ceiling(root.right, key);
else if (comp < 0 && root.left != null
&& key.compareTo(max(root.left).key) >= 0)
return ceiling(root.left, key);
else
return root;
}Copy after login
Select——select
public K select(int k) {
//找出BST中序号为k的键
return select(root, k);
}
private K select(Node root, int k) {
if (root == null)
return null;
int comp = k - size(root.left);
if (comp < 0)
return select(root.left, k);
else if (comp > 0)
return select(root.right, k - (size(root.left) + 1));
else
return root.key;
}Copy after login
Rank——rank
public int rank(K key) {
//找出BST中键为key的序号是多少
return rank(root, key);
}
private int rank(Node root, K key) {
if (root == null)
return 0;
int comp = key.compareTo(root.key);
if (comp == 0)
return size(root.left);
else if (comp < 0)
return rank(root.left, key);
else
return 1 + size(root.left) + rank(root.right, key);
}Copy after login
Delete minimum/maximum key——deleteMin/deleteMax
public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node root) {
if (root.left == null)
return root.right;
root.left = deleteMin(root.left);
root.N = size(root.left) + size(root.right) + 1;
return root;
}Copy after login
public void deleteMax() {
root = deleteMax(root);
}
private Node deleteMax(Node root) {
if (root.right == null)
return root.left;
root.right = deleteMax(root.right);
root.N = size(root.left) + size(root.right) + 1;
return root;
}Copy after login
Delete any key——delete
public void delete(K key) {
root = delete(root, key);
}
private Node delete(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp == 0) {
if (root.right == null)
return root = root.left;
if (root.left == null)
return root = root.right;
Node t = root;
root = min(t.right);
root.left = t.left;
root.right = deleteMin(t.right);
} else if (comp < 0)
root.left = delete(root.left, key);
else
root.right = delete(root.right, key);
root.N = size(root.left) + size(root.right) + 1;
return root;
}Copy after login
In-order print tree——print
public void print() {
print(root);
}
private void print(Node root) {
if (root == null)
return;
print(root.left);
System.out.println(root.key);
print(root.right);
}Copy after login
The above is the detailed content of Java-Binary Search Tree (BST) algorithm sample code sharing. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
