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

编写了一个红黑树、二叉查找树的实现程序。
用随机不等的1-30W自然数初始插入节点30W个，来分别建立一颗红黑树和二叉排序树。
自然红黑树的建立时间比较长，用System.currentTimeMillis()方法记录建树时间，测试结果如下：

建立30W个节点的红黑树用时: 269毫秒
建立30W个节点的二叉查找树用时: 222毫秒


理论上红黑树是比二叉查找树更高效的查找树，测试查找关键字为15000的节点，结果如下：

红黑树中查找关键字为15000的节点用时: 0毫秒
二叉查找树中查找关键字为15000的节点用时: 0毫秒


但是这样就体现不出红黑树的优势所在啊，然后我加大了随机样本容量测试。
当取400W的时候，红黑树的建树时间反而比二叉查找树的时间小了。。（问题一）

建立400W个节点的红黑树用时: 5000毫秒
建立400W个节点的二叉查找树用时: 5216毫秒


而且两棵树查找关键字的时间依然都是0（这里测试了若干关键字值）（问题二）

所以我想到找一个更精确的时间函数，微妙级别的。看见论坛上有人说过javax.realtime.HighResolutionTime.getNanoseconds();这个方法，但是没有找到API下载~
大家帮我看看这些问题吧，还有javax.realtime的包是怎么得到的？ （问题三）

--------------------编程问答-------------------- 用System.nanoTime()测试运行时间。纳秒级的时间函数。 --------------------编程问答-------------------- --------------------编程问答-------------------- 不如换个思路？直接用循环来随机查找 10000 次，然后统计10000次的总体消耗时间；甚至考虑启用100个线程，并发每个查找1000次。

构建树的过程应该也要重复多次（比如连续构造10棵树），虽然他们的元素都一样。

增加统计样本，统计结果才更准确。 --------------------编程问答-------------------- --------------------编程问答-------------------- 红黑树和普通的二叉（搜索）树本来也没有太大的差异啊。完全不存在数量级上面的问题。
无非是插入（删除）一个结点的时候，导致树的翻转策略不同。
而且你又是真正的随机插入，估计搜索树也会很平衡的。

你干脆用JavaScript或者Ruby来做这个事情，也就是说插入一个结点的时候，这个语言本身导致耗费了更多的时间，而没有突出算法本身的精妙。

或许用C/C++来测这二者之间的比较才有意义。

补充：Java ,  Java SE