Code:
java.util.TreeSet and java.util.TreeMap should be used when the order of the key does matter. The get and put operation has time cost O(logN). If order doesn't matter, java.util.HashSet and java.util.HashMap should be used, their get and put operation has time cost O(1).
import java.util.*;
public class test {
public static void main(String...args) {
Set<Integer> set = new TreeSet<>();
Map<Integer, String> map = new TreeMap<>();
set.add(1);
set.add(10);
set.add(5);
set.add(3);
set.add(30);
set.stream().forEach(System.out::println);
System.out.println("=========");
map.put(1, "one");
map.put(10, "ten");
map.put(5, "five");
map.put(3, "tree");
map.put(30, "thirty");
map.values().stream().forEach(System.out::println);
}
}
The following class is a simple example of BST.
//space: 56N. time: insert(search) worst. O(N) avg. O(logN)
public class BST<Key extends Comparable<Key>, Value> {
private Node root;
private class Node {
private Key key;
private Value val;
private Node left;
private Node right;
private int N;
public Node(Key key, Value val, int N) {
this.key = key;
this.val = val;
this.N = N;
}
}
public int size() {
return size(root);
}
private int size(Node x) {
if(x == null) return 0;
else return x.N;
}
public Value get(Key key) {
return get(root, key);
}
private Value get(Node x, Key key) {
if(x == null) return null;
int cmp = key.compareTo(x.key);
if(cmp < 0) {
return get(x.left, key);
} else if (cmp > 0) {
return get(x.right, key);
} else {
return x.val;
}
}
public void put(Key key, Value val) {
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
if(x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if(cmp < 0) {
x.left = put(x.left, key, val);
} else if(cmp > 0) {
x.right = put(x.right, key, val);
} else {
x.val = val;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}
public Value getMin() {
return getMin(root);
}
private Value getMin(Node x) {
if(x == null) return null;
if(x.left == null) return x.val;
else return getMin(x.left);
}
public static void main(String...args) {
BST<Integer, String> bst = new BST<>();
bst.put(5, "five");
bst.put(6, "six");
bst.put(11, "eleven");
bst.put(9, "nine");
bst.put(4, "four");
bst.put(7, "seven");
System.out.println(bst.size());
System.out.println(bst.get(6));
System.out.println(bst.getMin());
}
}
