enlightening...
public class RedBlackBST<Key extends Comparable<Key>, Value> {
private Node root;
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
Key key;
Value val;
Node left, right;
int N;
boolean color;
Node(Key key, Value val, int N, boolean color) {
this.key = key;
this.val = val;
this.N = N;
this.color = color;
}
}
private boolean isRed(Node x) {
if(x == null) return false;
return x.color == RED;
}
//TODO: visit the one
Node rotateLeft(Node h) {
//ॐ mantra???मन्त्र
}
Node rotateRight(Node h) {
//末那识???मानस-विज्ञान
}
void flipColors(Node h) {//少林洗髓经
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK:
}
public int size() {
return size(root);
}
private int size(Node x) {
if(x == null) return 0;
else return x.N;
}
public void put(Key key, Value val) {
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val) {
if(h == null) return new Node(key, val, 1, RED);
int cmp = key.compareTo(h.key);
if(cmp < 0) h.left = put(h.left, key, val);
else if(cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
if(isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if(isRed(h.left) &&isRed(h.left.left)) h = rotateRight(h);
if(isRed(h.left) && isRed(h.right) flipColors(h);
h.N = size(h.left) + size(h.right) + 1;
return h;
}
public Key min() {return min(root).key;}
private Node min(Node x) {
if(x.left == null) return x;
return min(x.left);
}
public Key floor(Key key) {
Node x = floor(root, key);
if(x == null) return null;
return x.key;
}
private Node floor(Node x, Key key) {
if(x == null) return null;
int cmp = key.compareTo(x.key);
if(cmp == 0) return x;
if(cmp < 0) return floor(x.left, key);
Node t = floor(x.right, key);
if(t != null) return t;
else return x;
}
public Key select(int k) { return select(root, k).key; }
private Node select(Node x, int k) {
if(x == null) return null
int t = size(x.left);
if(t > k) return select(x.left, k);
else if(t < k) return select(x.right, k- t-1);
else return x;
}
public int rank(Key key) {return rank(key, root);}
private int rank(Key key, Node x) {
if(x == null) return 0;
int cmp = key.compareTo(x.key);
if(cmp < 0) return rank(key, x.left);
else if(cmp > 0) return 1 + size(x.left) + rank(key, x.right);
else return size(x.left);
}
public Iterable<Key> keys() {return keys(min(), max()); }
public Iterable<Key> keys(Key lo, Key hi) {
Queue<Key> queue = new Queue<Key>();
keys(root, queue, lo, hi);
return queue;
}
private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
if(x == null) return;
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if(cmplo < 0) keys(x.left, queue, lo, hi);
if(cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);
if(cmphi > 0) keys(x.right, queue, lo, hi);
}
private void print(Node x) {
if(x == null) return;
print(x.left);
System.out.println(x.key);
print(x.right);
}
}
