使用分拣红黑树 [英] Using red black trees for sorting

问题描述

在红黑树运行插入时的最坏情况是 O（LG N）和如果我执行按顺序走在树上，我基本上是参观的每个节点，所以总最坏情况下的运行时打印的有序集合将是为O（n LGñ ）

The worst-case running time of insertion on a red-black tree is O(lg n) and if I perform a in-order walk on the tree, I essentially visit each node, so the total worst-case runtime to print the sorted collection would be O(n lg n)

我很好奇，为什么红黑树不是preferred进行排序了快速排序（其运行时间平均情况是为O（n LG N）。

I am curious, why are red-black trees not preferred for sorting over quick sort (whose average-case running time is O(n lg n).

我看到，也许是因为红黑树不排序就地，但我不知道，也许有人可以帮助。

I see that maybe because red-black trees do not sort in-place, but I am not sure, so maybe someone could help.

推荐答案

了解哪些排序算法进行更好的真的取决于你的数据和情况。

Knowing which sort algorithm performs better really depend on your data and situation.

如果你在谈论一般/实际上，

If you are talking in general/practical terms,

快速排序（一个在您选择轴随机/只选一个固定的，因此最坏的情况下欧米茄（N ^ 2））可能会比红黑树，因为（不一定按重要性排序）

Quicksort (the one where you select the pivot randomly/just pick one fixed, making worst case Omega(n^2)) might be better than Red-Black Trees because (not necessarily in order of importance)

• 快速排序是原地。将让你的内存占用低。之所以这样说，快速排序程序是一个程序，处理大量数据的一部分。如果你一直使用大量的内存，您的操作系统可以开始你的交换进程的内存和垃圾的PERF。

• Quicksort is in-place. The keeps your memory footprint low. Say this quicksort routine was part of a program which deals with a lot of data. If you kept using large amounts of memory, your OS could start swapping your process memory and trash your perf.

快速排序存储器访问本地化。这与缓存/交换打得很好。

Quicksort memory accesses are localized. This plays well with the caching/swapping.

快速排序可以很容易地并行（可能更多相关的这些天）。

Quicksort can be easily parallelized (probably more relevant these days).

如果你尝试和优化二叉树使用数组排序，而不是（用二叉树不均衡），你最终会做这样的事情的快速排序！

If you were to try and optimize binary tree sorting (using binary tree without balancing) by using an array instead, you will end up doing something like Quicksort!

红黑树有记忆的开销。你必须分配节点可能多次，树木内存需求是双打/三，使用数组。

Red-Black trees have memory overheads. You have to allocate nodes possibly multiple times, your memory requirements with trees is doubles/triple that using arrays.

整理后，说你想要的第一千○四十五（说）的元素，你需要保持你的树订单统计数据（因为这个额外的内存成本），你将有O（LOGN）存取时间！

After sorting, say you wanted the 1045th (say) element, you will need to maintain order statistics in your tree (extra memory cost because of this) and you will have O(logn) access time!

红黑树有开销只是访问的下一个元素（指针查询）

Red-black trees have overheads just to access the next element (pointer lookups)

红黑树不缓存踢好指针访问可能会引起更多的交换。

Red-black trees do not play well with the cache and the pointer accesses could induce more swapping.

旋转在红黑树将增加常数因子在O（nlogn）。

Rotation in red-black trees will increase the constant factor in the O(nlogn).

也许最重要的原因（但如果你有lib目录等提供有效），快速排序是很简单的理解和实施。即使是学校的孩子能理解！

Perhaps the most important reason (but not valid if you have lib etc available), Quicksort is very simple to understand and implement. Even a school kid can understand it!

我会说你尝试测量两个实现，看看会发生什么！

I would say you try to measure both implementations and see what happens!

此外，鲍勃·塞奇威克做了论文的快速排序！可能是值得一读。

Also, Bob Sedgewick did a thesis on quicksort! Might be worth reading.

这篇关于使用分拣红黑树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！