红黑树是我理想的数据结构吗？

Question

我有一系列的事项（大分数），将要进行处理。在每种情况下，处理将包括移除集合中最小的项目，进行一些工作，然后添加0-2个新项目（这些新项目始终大于已移除的项目）。集合将被初始化为一个项目，并且处理将继续进行直到它为空。我不确定集合可能会达到多大，但我预计在1M-100M个项目的范围内。我只需要定位最小的项目。

目前，我打算使用红黑树，可能对其进行调整以保留对最小项目的指针。但是，我以前从未使用过红黑树，也不确定我的使用模式是否与其特性相适应。

1）从左边删除+随机插入的模式会影响性能吗？例如，是否需要旋转的数量比随机删除要高得多？或者，在这种使用模式下，删除和插入操作仍然是O(log n)的吗？

2）是否有其他数据结构可以给我提供更好的性能，无论是由于删除模式还是利用我只需要找到最小项的事实？

更新：很高兴我问了，二叉堆显然是这种情况下更好的解决方案，而且如承诺般非常容易实现。

Hugo

- Hugo van der Sanden

---

除非您确定逻辑上应删除的节点不会被新计算出的值所需，否则您可能希望忽略或延迟删除。对于后者，Halt＆Sweep方法应该可行，其中子树的根节点已变得过于混乱，则通过重新平衡代码访问这些根节点以进行集中重新平衡。这可以防止严重退化，同时仍然提供无需删除的性能前景。 - user1899861

Answer 1

一个二叉堆是更适合你所需的。它更容易实现和更快，因为你只关心定位最小的元素和插入操作。定位最小元素的时间复杂度为O(1)，删除它的时间复杂度为O(log N)，插入操作的时间复杂度也是O(log N)。

- IVlad

---

实际上，如果他知道他总是插入比删除的项更大的项，那么二叉堆（treap）最终会变得非常不平衡。100M条记录很多，所以这可能会变得不平衡到不再是O(log(n))，而是O(n) - 例如，当n = 100M时，如果treap的高度最终达到160k，则为O(n/((lgn)^2))。 - Etai

@Etai - 二进制堆对于我提到的操作始终是O(log N)。我不知道你为什么提到treap，我的回答是关于二进制堆而非treap的。堆确实在treap结构中起着重要作用，但两者是不同的数据结构。 - IVlad

二叉堆插入的平均时间复杂度为O(1)（Brodal的最坏情况），这是使用它而不是BST的主要原因：https://dev59.com/MG025IYBdhLWcg3wNTEV#29548834 - Ciro Santilli OurBigBook.com

Answer 2

使用堆可以实现O(log n)的插入和删除操作，而且相比红黑树，堆的实现更简单。

- BlueRaja - Danny Pflughoeft

---

实际上，删除操作的时间复杂度为O(log N)，而查找最小/最大值的时间复杂度为O(1)。其中，“locating”的意思是“查找（某个值）”。 - IVlad

我从未见过一个有1M-100M项的堆，是否有人对它的速度有一些了解？ - Nick Larsen

这正是“大 O 记号”所用的目的。 - BlueRaja - Danny Pflughoeft

我明白这一点，然而，大 O（Big-O）存在于理论世界中，而计算机上的 1 亿条记录则存在于物理世界中。在内存有限的情况下，是否有比堆更好的数据结构呢？ - Nick Larsen

@Nick：堆可以使用数组来实现，因此它不需要额外的空间。 - BlueRaja - Danny Pflughoeft

二叉堆插入的平均时间复杂度为O(1)（Brodal的最坏情况），这是使用它而不是BST的主要原因：https://dev59.com/MG025IYBdhLWcg3wNTEV#29548834 - Ciro Santilli OurBigBook.com

Answer 3

如果需要的话，了解如何创建更复杂的数据结构是很好的。然而，通常最好从尽可能简单的开始，只有在确实需要时才使用更复杂的东西。

我唯一实现自平衡树的时候是当我知道我的树将非常大（超过10,000个元素），并且数据将呈排序状态时。这意味着如果我使用普通的二叉树，我最终会得到几乎是一个链表。

如果您的数据以随机顺序输入，则真的不必费心平衡算法。

- T.E.D.

---

首先，同意KISS原则，只有在必要时才使用复杂的方法。有许多方法可以解决自平衡的要求，例如创建索引以随机顺序读取数据，但是需要注意的是，这仅适用于您了解要求的情况下。例如：不适用于通用用途，如创建库。而且，把这个任务留给后来维护你代码的可怜人是非常不礼貌的。尽管如此，我总体上赞同你的哲学观点。 - user1899861