Red Black Tree Slower Than Regular Binary Search In My Tests

Question

I implemented a Red Black Tree, and I wanted to compare the time to a regular binary search tree. However, in my tests, I found that most of the time, Binary Search Tree's are actually faster. Is there something wrong in my implementation, or is this supposed to happen? This is my Red Black Tree:

public class RedBlackTree {

    public class RedBlackNode {
        Integer val;
        RedBlackNode left, right, parent;
        boolean color;

        public RedBlackNode() {

        }

        public RedBlackNode(Integer val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val + "";
        }

    }

    public static final boolean red = false, black = true;

    public RedBlackNode root;
    public final RedBlackNode nil;
    public int size;

    public RedBlackTree() {
        nil = new RedBlackNode();
        nil.color = black;
        root = nil;
    }

    public void insert(int val) {
        size ++;

        if(root == nil) {
            root = new RedBlackNode(val);
            root.parent = nil;
            root.left = nil;
            root.right = nil;
            root.color = black;
            return;
        }

        RedBlackNode dummy = root;

        while(true) {
            if(val < dummy.val) {
                if(dummy.left == nil) {
                    dummy.left = new RedBlackNode(val);
                    dummy.left.parent = dummy;
                    dummy.left.left = nil;
                    dummy.left.right = nil;
                    dummy.left.color = red;
                    dummy = dummy.left;
                    break;
                }

                dummy = dummy.left;
            } else {
                if(dummy.right == nil) {
                    dummy.right = new RedBlackNode(val);
                    dummy.right.parent = dummy;
                    dummy.right.left = nil;
                    dummy.right.right = nil;
                    dummy.right.color = red;
                    dummy = dummy.right;
                    break;
                }

                dummy = dummy.right;
            }
        }

        balance(dummy);
    }

    private void balance(RedBlackNode node) {
        while(node.parent.color == red) {
            if(node.parent == node.parent.parent.left) {
                if(node.parent.parent.right.color == red) {
                    node.parent.color = black;
                    node.parent.parent.color = red;
                    node.parent.parent.right.color = black;
                    node = node.parent.parent;
                } else {
                    if(node == node.parent.right) {
                        node = node.parent;
                        rotateLeft(node);
                    }

                    node.parent.color = black;
                    node.parent.parent.color = red;
                    rotateRight(node.parent.parent);
                }
            } else {
                if(node.parent.parent.left.color == red) {
                    node.parent.color = black;
                    node.parent.parent.color = red;
                    node.parent.parent.left.color = black;
                    node = node.parent.parent;
                } else {
                    if(node == node.parent.left) {
                        node = node.parent;
                        rotateRight(node);
                    }

                    node.parent.color = black;
                    node.parent.parent.color = red;
                    rotateLeft(node.parent.parent);
                }
            }
        }

        root.color = black;
    }

    private void rotateLeft(RedBlackNode node) {
        RedBlackNode temp = node.right;
        node.right = temp.left;
        temp.left.parent = node;
        temp.parent = node.parent;
        if(node.parent == nil) {
            root = temp;
        } else if(node == node.parent.left) {
            node.parent.left = temp;
        } else {
            node.parent.right = temp;
        }
        temp.left = node;
        node.parent = temp;
    }

    private void rotateRight(RedBlackNode node) {
        RedBlackNode temp = node.left;
        node.left = temp.right;
        temp.right.parent = node;
        temp.parent = node.parent;
        if(node.parent == nil) {
            root = temp;
        } else if(node == node.parent.right) {
            node.parent.right = temp;
        } else {
            node.parent.left = temp;
        }
        temp.right = node;
        node.parent = temp;
    }

    public void printInSorted() {
        printInSorted(root);
    }

    private void printInSorted(RedBlackNode root) {
        if(root == nil) {
            return;
        }

        printInSorted(root.left);
        System.out.print(root.val + " ");
        printInSorted(root.right);
    }

}

My Binary Search Tree:

public class BinarySearchTree {

    public class BinarySearchTreeNode {
        int val;
        BinarySearchTreeNode left, right;

        public BinarySearchTreeNode(int val) {
            this.val = val;
        }
    }

    private BinarySearchTreeNode root;
    private int size;

    public void insert(int val) {
        size ++;

        if(root == null) {
            root = new BinarySearchTreeNode(val);
            return;
        }

        BinarySearchTreeNode dummy = root;

        while(true) {
            if(val < dummy.val) {
                if(dummy.left == null) {
                    dummy.left = new BinarySearchTreeNode(val);
                    break;
                }

                dummy = dummy.left;
            } else {
                if(dummy.right == null) {
                    dummy.right = new BinarySearchTreeNode(val);
                    break;
                }

                dummy = dummy.right;
            }
        }
    }

    public boolean search(int val) {
        return search(root, val);
    }

    private boolean search(BinarySearchTreeNode root, int val) {
        if(root == null) {
            return false;
        }

        if(root.val == val) {
            return true;
        }

        return search(root.left, val) || search(root.right, val);
    }

    public void printInSorted() {
        printInSorted(root);
    }

    private void printInSorted(BinarySearchTreeNode root) {
        if(root == null) {
            return;
        }

        printInSorted(root.left);
        System.out.print(root.val + " ");
        printInSorted(root.right);
    }

    public int[] inSorted() {
        int[] ans = new int[size];
        int count = 0;
        Stack<BinarySearchTreeNode> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()) {
            BinarySearchTreeNode curr = stack.pop();

            if(curr.left != null || curr.right != null) {
                if(curr.right != null) {
                    stack.push(curr.right);
                    curr.right = null;
                }

                stack.push(curr);

                if(curr.left != null) {
                    stack.push(curr.left);
                    curr.left = null;
                }
            } else {
                ans[count ++] = curr.val;
            }
        }

        return ans;
    }

}

Here is my testing:

    int better = 0;
    for(int i = 0; i < 30; i ++) {
        RedBlackTree redBlackTree = new RedBlackTree();
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        int[] rand = Utility.createArray(100, 100);

        long start1 = System.currentTimeMillis();
        for(int j : rand) {
            redBlackTree.insert(j);
        }
        long end1 = System.currentTimeMillis();

        long start2 = System.currentTimeMillis();
        for(int j : rand) {
            binarySearchTree.insert(j);
        }
        long end2 = System.currentTimeMillis();

        long total1 = end1 - start1;
        long total2 = end2 - start2;

        if(total1 < total2) {
            better ++;
        }
    }

    System.out.println((double) (better) / 100 + "%");

This should print the percentage of the amount of times Red Black Tree was faster. Utility.createArray(int size, int max) just creates a array of size size and a maximum of max of random numbers. What I'm getting most of the time is percents like 0.02% or 0.03%.

score 4 · Accepted Answer · answered Mar 31 '20 at 19:49

This is not a good benchmark. See How do I write a correct micro-benchmark in Java?

To list a few pain points: System.currentTimeMillis doesn't give enough time resolution, your code doesn't do "warm up" iterations to ensure the code is compiled, it does nothing to ensure the compiler doesn't throw the code away because it doesn't have side effects, etc. If you're interested in making better benchmarks, I'd suggest learning to use JMH.

That said, the fact that you are inserting random numbers means you are very likely to avoid the pathological cases that make unbalanced binary search trees perform badly. You are in effect using a "treap" (randomized binary search tree). The overhead is lower than in a red-black tree, so it's not too surprising you may see better performance.

Those are very good points. I would like to add that 100 elements is way below the number where the performance starts to reflect the expected asymptotic complexity properties. And always remember to profile your code to get answers about its performance characteristics. — Zdeněk Jelínek, Mar 31 '20 at 20:14

Red Black Tree Slower Than Regular Binary Search In My Tests

1 Answers1