2

给定一个整数区间，一个具有唯一元素I的 RB 树和一个唯一元素序列，其值不在 中，插入的性能是否会因排序或随机顺序而异？答案将如何根据 和 的相对大小而变化？RnISnIRSRS|I|n

鉴于S不在其中的元素，R不清楚如何分析插入需要维护的不变量以及需要发生的重新平衡操作。我运行|I|的 Ruby 基准测试比n建议的排序插入执行速度快 10+% 大 100 倍。

4

2 回答 2

2

性能会有所不同。

C++ 中的示例测试（我知道 g++map是基于红黑树并使用它）：

#include <iostream>
#include <map>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 50000;
const int REPS = 100;
int ints[N];

int main()
{
  time_t t;
  srand(time(0));

  // fill ints[] with ints from 0 to N-1
  for (int i = 0; i < N; i++)
    ints[i] = i;

  // randomly shuffle ints[]
  for (int i = 0; i < N; i++)
  {
    int j = ((unsigned)rand() * rand()) % N;
    int t = ints[i];
    ints[i] = ints[j];
    ints[j] = t;
  }

  cout << "Inserting " << 2 * N << " sorted keys, repeating " << REPS << " times..." << endl;
  time(&t); cout << ctime(&t) << endl;
  for (int n = 0; n < REPS; n++)
  {
    map<int,int> m;
    for (int i = 0; i < N; i++)
      m[i] = i;
    for (int i = 0; i < N; i++)
      m[N + i] = i;
  }
  time(&t); cout << ctime(&t) << endl;

  cout << "Inserting " << N << " sorted keys and then " << N << " unsorted keys, repeating " << REPS << " times..." << endl;
  time(&t); cout << ctime(&t) << endl;
  for (int n = 0; n < REPS; n++)
  {
    map<int,int> m;
    for (int i = 0; i < N; i++)
      m[i] = i;
    for (int i = 0; i < N; i++)
      m[N + ints[i]] = i;
  }
  time(&t); cout << ctime(&t) << endl;

  return 0;
}

输出（liveworkspace）：

Inserting 100000 sorted keys, repeating 100 times...
Sun Apr 7 04:14:03 2013

Sun Apr 7 04:14:05 2013

Inserting 50000 sorted keys and then 50000 unsorted keys, repeating 100 times...
Sun Apr 7 04:14:05 2013

Sun Apr 7 04:14:10 2013

如您所见，性能明显不同：排序插入需要 2 秒，而未排序插入需要 5 秒。

于 2013-04-07T04:21:38.073 回答
0

当然性能各不相同；如果您将 2、1、3 插入到一棵空的红黑树中，则永远不会执行旋转；如果插入 1，然后 2，然后 3，则必须执行轮换。

如果您只想以最快的方式构建红黑树，请对列表进行排序，将其围绕中间元素拆分，从两半构建红黑树，并将中间元素作为两半的父元素。你在这里没有旋转或其他恶作剧。

就像 Alexey Frunze 所说，它的变化不能超过一个小的常数因子。

于 2013-04-07T03:01:02.177 回答