在我的测试中，红黑树比常规二叉搜索慢

Question

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

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%这样的百分比。

Answer 1

这不是一个好的基准。请参阅如何在 Java 中编写正确的微基准测试？

列出几个痛点：System.currentTimeMillis没有提供足够的时间分辨率，你的代码没有做"预热"迭代来确保代码被编译，它没有做任何事情来确保编译器不会因为没有副作用而丢弃代码，等等。如果你有兴趣制作更好的基准，我建议你学习使用JMH。

也就是说，您插入随机数的事实意味着您很可能避免使不平衡的二叉搜索树表现不佳的病理情况。您实际上是在使用"treap"(随机二叉搜索树)。开销比红黑树低，因此您可能会看到更好的性能也就不足为奇了。