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

This program is for constructing a symbol table where a key is a word and value is the frequency of the word in a text file and finding the word with maximum frequency.

I did it in two ways:

First I used Java's inbuilt TreeMap, which uses a red-black tree as internal data structure.

Then I made my own implementation of red-black tree and did the same thing.But I was lot disappointed when my program came whole lot slower in accomplishing the task. I ran both the programs several times. But still the minimum time of TreeMap was lesser than my own program time by at least 1 million of nano seconds. Also it won every time when I computed average time taken by both. This much time lag makes me ask whether I can improve my implementation of red-black tree about which I am really skeptical.

First method:

import java.util.*;
import java.io.*;
class TREEMAP_APP
{
 public static void main(String []args)throws IOException
 {
     BufferedReader br = new BufferedReader(new FileReader("book.txt"));
     TreeMap tm = new TreeMap();
     String S="";
     String []arr;
     String line;
     int max=0;
     long st=System.nanoTime();
     while((line=br.readLine())!=null)
     {
         arr=line.split(" ");

         for(String k:arr)
          if(!tm.containsKey(k))
           tm.put(k,1);
          else
          {
            tm.put(k,tm.get(k)+1);
            if(tm.get(k)>max)
            {S=k;max=tm.get(k);}
          }
     }
     long ft=System.nanoTime()-st;
     System.out.println("time taken is "+ft);
     System.out.println("the word that occurs for the maximum no of times is and it occurs for");
     System.out.println(S+"    "+max);
    }
}

Red-black tree:

```
import java.io.*;
class REDBLACK
{
int max=0;String S="";
public Node insert(Node x,String key)
{
if(x==null)
{
return new Node(key,1,'R',null,null);
}
else if(key.compareTo(x.key)>0)
{
x.right=insert(x.right,key);
}
else if(ke

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 > 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)&&!isRed(x.left))   x=rotate_left(x);
 else if(isRed(x.left)&&isRed(x.left.left)) x=rotate_right(x);
 else if(isRed(x.left)&&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 > 0) {
        x.right = insert(x.right,key);
    } else if (comparison  max) {
            max = x.value;
            S = key;
        }
    }
    if (isRed(x.right) && !isRed(x.left)) {
        x = rotate_left(x);
    } else if (isRed(x.left) && isRed(x.left.left)) {
        x = rotate_right(x);
    } else if (isRed(x.left) && 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.

StackExchange Code Review Q#97354, answer score: 3