title: Red Black Tree Slower Than Regular Binary Search In My Tests
body: <p>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:</p>
  
  <pre><code>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 &lt; 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);
      }
  
  }
  </code></pre>
  
  <p>My Binary Search Tree:</p>
  
  <pre><code>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 &lt; 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&lt;BinarySearchTreeNode&gt; stack = new Stack&lt;&gt;();
          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;
      }
  
  }
  </code></pre>
  
  <p>Here is my testing:</p>
  
  <pre><code>    int better = 0;
      for(int i = 0; i &lt; 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 &lt; total2) {
              better ++;
          }
      }
  
      System.out.println((double) (better) / 100 + "%");
  </code></pre>
  
  <p>This should print the percentage of the amount of times Red Black Tree was faster. <code>Utility.createArray(int size, int max)</code> just creates a array of size <code>size</code> and a maximum of <code>max</code> of random numbers. What I'm getting most of the time is percents like <code>0.02%</code> or <code>0.03%</code>.</p>