我实现了一棵红黑树，我想将时间与常规二叉搜索树进行比较。然而，在我的测试中，我发现大多数时候，二叉搜索树实际上更快。我的实现中是否有问题，或者应该发生这种情况？这是我的红黑树：

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);
    }

}

我的二进制搜索树：

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;
    }

}

以下是我的测试:

    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 + "%");

这应该会打印红黑树更快的次数百分比Utility.createArray（int size，int max）只创建一个大小size的数组，最大值max随机数。我大部分时间得到的是百分比，如0.02%或0.03%。