红黑树和二叉排序树的若干疑问 + 精确到微妙级的函数？

Question

用System.nanoTime()测试运行时间。纳秒级的时间函数。

Answer 1

红黑树和普通的二叉（搜索）树本来也没有太大的差异啊。完全不存在数量级上面的问题。
无非是插入（删除）一个结点的时候，导致树的翻转策略不同。
而且你又是真正的随机插入，估计搜索树也会很平衡的。你干脆用JavaScript或者Ruby来做这个事情，也就是说插入一个结点的时候，这个语言本身导致耗费了更多的时间，而没有突出算法本身的精妙。或许用C/C++来测这二者之间的比较才有意义。

Answer 2

红黑树主要是为了避免普通二叉查找树在输入基本有序的数列时树的高度过高导致的性能下降，你输入一万个连续升序或降序的数列就能够很明显的看出差别：这时候红黑树还是保持着很好的O(lgN)性能，而普通二叉树就是一条链表O(N)的性能了。