老师为什么我不管用随机数还是顺序数测试的结果都是avl树花费的时间较少？

Question

如题？

Answer 1

liuyubobobo 2019-11-21 04:20:38

如果你确定你的代码是正确的话，这种情况也是正常的。因为 AVL 树和红黑树本身就是通复杂级别的算法，不存在谁会退化的情况，各项操作两种数据结构都是稳定的 O(nlogn)。

红黑树的优势在统计意义上，所谓统计意义，就是一方面，要有大量样本，一方面，要在各种顺序下实验，最终看平均结果。

另一方面，对于 Java 语言，由于最终是运行在 JVM 上的，所以 JVM 的优化，包括操作系统的状态，都会影响最终测试结果。不管怎样，我相信你所说的“少”，也不会有巨大的量级上的差异。如果真要严格看到我们的逻辑带来的性能影响，而抛弃其他因素的话，用 C/C++ 更好；用汇编更更好。

最后，我们所讲的红黑树，没有介绍删除操作。而删除操作由于比较复杂，也是会拉开红黑树与AVL树的性能，在统计意义上的关键原因。

不过依然是，这里我说的统计意义上的差距，对于个别情况，产生反转是正常的。他们都是 O(nlogn) 的树结构。

继续加油！：）

• 提问者 三儿弟弟_04355186 #1

  感谢老师！确实差距很小