Left-leaning Red-Black Tree (LLRB) - http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

LLRB.java

/**
 * A "Left-leaning Red-Black Tree"
 * 
 * http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
 */
public class LLRB<K extends Comparable<K>, V> {

    public static void main(String[] args) {
        LLRB<String, String> llrb = new LLRB<String, String>();
        
        for (int i = 0; i < 100; i++) {
            llrb.insert("Hello-" + i, "World-" + i);
        }
        
        System.out.println("GET #1: " + llrb.search("Hello-55"));
        System.out.println("GET #2: " + llrb.search("Hello-100"));
        
        llrb.delete("Hello-55");
        System.out.println("GET #3: " + llrb.search("Hello-55"));
        System.out.println("GET #4: " + llrb.search("Hello-56"));
    }
    
    private Node root = null;
    
    public V search(K key) {
        return search(root, key);
    }
    
    private V search(Node h, K key) {
        while (h != null) {
            int cmp = key.compareTo(h.key);
            if (cmp == 0) {
                return h.value;
            } else if (cmp < 0) {
                h = h.left;
            } else {
                h = h.right;
            }
        }
        return null;
    }
    
    public void insert(K key, V value) {
        root = insert(root, key, value);
        root.color = Node.BLACK;
    }
    
    private Node insert(Node h, K key, V value) {
        if (h == null) {
            return new Node(key, value);
        }
        
        if (isRed(h.left) && isRed(h.right)) {
            colorFlip(h);
        }
        
        int cmp = key.compareTo(h.key);
        if (cmp == 0) {
            h.value = value;
        } else if (cmp < 0) {
            h.left = insert(h.left, key, value);
        } else {
            h.right = insert(h.right, key, value);
        }
        
        if (isRed(h.right) && !isRed(h.left)) {
            h = rotateLeft(h);
        }
        
        if (isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }
        
        return h;
    }
    
    public void deleteMin() {
        root = deleteMin(root);
        root.color = Node.BLACK;
    }
    
    private Node deleteMin(Node h) {
        if (h.left == null) {
            return null;
        }
        
        if (!isRed(h.left) && !isRed(h.left.left)) {
            h = moveRedLeft(h);
        }
        
        h.left = deleteMin(h.left);
        return fixUp(h);
    }
    
    public void delete(K key) {
        root = delete(root, key);
        root.color = Node.BLACK;
    }
    
    private Node delete(Node h, K key) {
        if (key.compareTo(h.key) < 0) {
            if (!isRed(h.left) && !isRed(h.left.left)) {
                h = moveRedLeft(h);
            }
            h.left = delete(h.left, key);
        } else {
            if (isRed(h.left)) {
                h = rotateRight(h);
            }
            
            if (key.compareTo(h.key) == 0 && h.right == null) {
                return null;
            }
            
            if (!isRed(h.right) && !isRed(h.right.left)) {
                h = moveRedRight(h);
            }
            
            if (key.compareTo(h.key) == 0) {
                h.value = search(h.right, min(h.right).key);
                h.key = min(h.right).key;
                h.right = deleteMin(h.right);
            } else {
                h.right = delete(h.right, key);
            }
        }
        
        return fixUp(h);
    }
    
    private Node moveRedLeft(Node h) {
        colorFlip(h);
        
        if (isRed(h.right.left)) {
            h.right = rotateRight(h.right);
            h = rotateLeft(h);
            colorFlip(h);
        }
        
        return h;
    }
    
    private Node moveRedRight(Node h) {
        colorFlip(h);
        
        if (isRed(h.left.left)) {
            h = rotateRight(h);
            colorFlip(h);
        }
        
        return h;
    }
    
    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        
        x.color = h.color;
        h.color = Node.RED;
        return x;
    }
    
    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        
        x.color = h.color;
        h.color = Node.RED;
        return x;
    }
    
    private boolean isRed(Node h) {
        return h != null && h.color == Node.RED;
    }
    
    private void colorFlip(Node h) {
        h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
    }
    
    private Node min(Node h) {
        while (h.left != null) {
            h = h.left;
        }
        return h;
    }
    
    private Node fixUp(Node h) {
        if (isRed(h.right)) {
            h = rotateLeft(h);
        }
        
        if (h.left != null && isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }
        
        if (isRed(h.left) && isRed(h.right)) {
            colorFlip(h);
        }
        
        return h;
    }
    
    private class Node {
        
        public static final boolean RED = true;
        
        private static final boolean BLACK = false;
        
        private K key;
        
        private V value;
        
        private boolean color = RED;
        
        private Node left = null;
        
        private Node right = null;
        
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}