Red-black tree not matching performance of Java's TreeMap
My own tests

I ran your program with various inputs, and in all my tests, your red black tree was faster than the TreeMap version.  I even fixed the TreeMap version so that it wouldn't search up to three times for the same word:

        Integer val;
        arr=line.split(" ");

        for(String k:arr) {
            val = tm.get(k);
            if (val == null) {
                tm.put(k,1);
            } else {
                int newVal = val + 1;
                tm.put(k, newVal);
                if (newVal &gt; max) {
                    S = k;
                    max = newVal;
                }
            }
        }


With the above change, the TreeMap version is about 10% slower than your red black tree.  It makes sense that the red black tree version would be faster because in the TreeMap version, you have a get followed by a put for each string.  In your red black tree version, you only have one insert which performs both functions.

Comments on your code

There were several places where I thought you squished your code when you didn't have to.  For example:


 else {x=new Node(key,x.value+1,x.color,x.left,x.right);}     

 if(isRed(x.right)&amp;&amp;!isRed(x.left))   x=rotate_left(x);
 else if(isRed(x.left)&amp;&amp;isRed(x.left.left)) x=rotate_right(x);
 else if(isRed(x.left)&amp;&amp;isRed(x.right)) flip_color(x);



and


Node left,right;static int max=0;static String S="";



I feel like you should space your code out and keep your statements on separate lines from the if and else.

Improvement to red black tree

In your red black tree code, where you have this:


 else {x=new Node(key,x.value+1,x.color,x.left,x.right);}     



it could be faster if you don't allocate a new node and instead modify the current one.  Also, you could make the insert faster by only calling the comparison function once.  Here is a rewrite of your insert() function that makes your program about 10% faster than before:

public static int max;
public static String S;
public Node insert(Node x,String key)
{
    if (x == null) {
        if (max == 0) {
            max = 1;
            S = key;
        }
        return new Node(key,1,'R',null,null);
    }
    int comparison = key.compareTo(x.key);
    if (comparison &gt; 0) {
        x.right = insert(x.right,key);
    } else if (comparison &lt; 0) {
        x.left = insert(x.left,key);
    } else {
        x.value++;
        if (x.value &gt; max) {
            max = x.value;
            S = key;
        }
    }
    if (isRed(x.right) &amp;&amp; !isRed(x.left)) {
        x = rotate_left(x);
    } else if (isRed(x.left) &amp;&amp; isRed(x.left.left)) {
        x = rotate_right(x);
    } else if (isRed(x.left) &amp;&amp; isRed(x.right)) {
        flip_color(x);
    }
    return x;
}


Try HashMap instead

What I think you are missing is that a HashMap is faster than both the TreeMap and the red black tree.  I replaced the TreeMap with a HashMap and the result was about 50% faster than the TreeMap and about 25% faster than the improved red black tree.