恩，明白了。
随机化二叉排序树是为了保证平衡么？是不是写起来比AVL或者SBT简单？所谓的“随机化二叉排序树”是不是就是Treap？

比红黑树那些写起来短
这个是treap的资料:[url=http://baike.baidu.com/view/956602.htm]http://baike.baidu.com/view/956602.htm[/url]
我说的随机化二叉排序树不是treap,而是考虑到可能出现特殊数据，而先对原数据打乱顺序，然后构造bst.我的打乱方法很简单，设数据规模为n，生成n个随机数（在n和0间，然后，每生成两个随机数，对这两个随机数所对应的变量进行交换，这样就可以较好的打乱顺序了。或者用一个quicksearch找一个中位数作为根，不过后者效率较低（虽然都是O(N),但是后者虽然找到了中位数，但对于特殊数据，数据的特殊性没有被打破)。这样，和quicksort类似，出现退化为链的可能性为2/n!，可以忽略掉
treap的代码长度一般比红黑树能少10行左右（参见野牛的测试），不过由于treap实现仍然需要旋转等操作，所以还是不好写。
由于对于这个题，不需要删除，只要插入和查找操作就可以了，所以，用以上方法，可以生成比较平衡的bst,所以这个个简单的方法（算法导论上好像提到过）可以较好的完成。

[[it] 本帖最后由 卧龙孔明 于 2008-7-8 12:24 编辑 [/it]]

是啊 写出来容易不过算法好就不容易了，都是高手~~加油学习

把6个元素丢入桶中,然后统计桶内元素的个数...
 解决了 0(n)...
   

随机化二叉排序树
clrs上有 ..

这6个数是int规模的，桶要多大？
这6个数是long long规模的，桶要多大？
这6个数是double规模的，桶要怎么设计？

那hash吧..

[[it] 本帖最后由 菜鸟选手 于 2008-7-8 14:51 编辑 [/it]]

程序我们注重思想，数据库我们注重原理，生活我们注重感情。07级程序&&数据库QQ交流群48335578，欢迎志士的加入

.....!

[[it] 本帖最后由 菜鸟选手 于 2008-7-8 15:58 编辑 [/it]]

程序我们注重思想，数据库我们注重原理，生活我们注重感情。07级程序&&数据库QQ交流群48335578，欢迎志士的加入