rank()

/* Find the rank of a given key */
public int rank(Key key) {
    return rank(root, key);                                 // 1
}

/* Private rank() method */
private int rank(Node<Key, Value> x, Key key) {
    if (x == null) {                                        // 2
        return 0;                                           // 2
    }

    int cmp = key.compareTo(x.key);                         // 3
    if (cmp < 0) {                                          // 4
        return rank(x.left, key);                           // 4
    } else if (cmp > 0) {                                   // 5
        return 1 + size(x.left) + rank(x.right, key);       // 5
    } else {                                                // 6
        return size(x.left);                                // 6
    }
}