Testing Prevailing AVL tree vs. Red Black Tree Wisdom

In almost every online discussion of AVL vs. Red-black trees there is a statement similar to this:

• AVL trees are more rigidly balanced so they are faster for lookups
• Red-black trees perform fewer rotations so they are faster for inserts

For example, see this discussion on Stack Overflow

Honestly, the vagueness of these statements greatly annoys me. Are these assumptions about performance valid enough to choose one balanced binary tree or another? Let's insert the same sequence of values into both trees and count the rotations and see what the actual numbers are.

For the first test we will allocate an array of size 300,000 and fill it with random integer sequences of 16. The code in Java to build the array is below:

java.util.Random r = new java.util.Random();
Integer[] groupedRandomNumbers = new Integer [300000];
for (int i = 0; i < groupedRandomNumbers.length;) {
    Integer nextRand = r.nextInt(Integer.MAX_VALUE - 16);
    for (int j=0; j < 16; j++) {
	groupedRandomNumbers[i++] = nextRand + j;
    }
}

Now the numbers for AVL, WAVL and Red-Black trees:

Tree Type	Tree Size	Tree Height	Rotations
AVL	300,000	21	411,552
WAVL	300,000	21	411,552
Red-black	300,000	23	506,609

Interesting? The red-black tree performs more rotations and builds a taller tree, the worst of both worlds. I'll leave out runtimes but red-black was the slowest and would likely perform the worst on lookups too since the tree is taller. The code is attached to this project.

Do you have real world tests you would like incorporated into this result? Please email me - dmcmanam gmail. Do you have a real world use case where your team assumed red-black trees would be faster but never tested it? I would enjoy hearing that too.