是一个红黑树我的理想数据结构？ [英] Is a red-black tree my ideal data structure?
问题描述
我目前正在计划使用一个红黑色的树，可能被调整以保持指针最小项目。但是我以前从来没有使用过，我不确定我的使用方式是否适合其特征。
1）是否有危险的删除模式左+随机插入会影响性能，例如要求比随机删除显着更高的旋转次数？或者将删除和插入操作仍然是O（log n）与这种使用模式？
2）其他一些数据结构会给我更好的性能，因为删除模式或利用我只需要找到最小的项目的事实？
更新：很高兴我问，二进制堆是对于这种情况来说，这显然是一个更好的解决方案，而且承诺证明是非常容易实现的。
Hugo
二进制堆对于你来说更好想。它更容易实现和更快速，因为您只需要定位最小的元素和插入。找到最小的元素是O（1），删除它是O（log N），插入也是O（log N）。
I have a collection of items (big rationals) that I'll be processing. In each case, processing will consist of removing the smallest item in the collection, doing some work, and then adding 0-2 new items (which will always be larger than the removed item). The collection will be initialised with one item, and work will continue until it is empty. I'm not sure what size the collection is likely to reach, but I'd expect in the range 1M-100M items. I will not need to locate any item other than the smallest.
I'm currently planning to use a red-black tree, possibly tweaked to keep a pointer to the smallest item. However I've never used one before, and I'm unsure whether my pattern of use fits its characteristics well.
1) Is there a danger the pattern of deletion from the left + random insertion will affect performance, eg by requiring a significantly higher number of rotations than random deletion would? Or will delete and insert operations still be O(log n) with this pattern of use?
2) Would some other data structure give me better performance, either because of the deletion pattern or taking advantage of the fact I only ever need to find the smallest item?
Update: glad I asked, the binary heap is clearly a better solution for this case, and as promised turned out to be very easy to implement.
Hugo
A binary heap is a lot better for what you want. It is easier to implement and faster since you only care about locating the smallest element and insertions. Locating the smallest element is O(1), removing it is O(log N), and an insertion is also O(log N).
这篇关于是一个红黑树我的理想数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
