从大集合构建AVL树高效算法

Question

我有一个大 AVL树我建立程序期间的某一时间从一个未排序的集合（它将被用于插入/移除后项）。

有没有更好的算法比用在每个项目上的简单的插入？这将是更有效的第一排序集合，然后尝试以不同的方式构建它？

我的应用程序的性能分析告诉我，这AVL建设是一个热点的位置。

Answer 1

如果数据方便地装入内存，我的确会想到，首先进行快速排序，并建立从树会比做所有的常规插入得更快。

要从阵列构建树，操作以递归方式，将树分割为三个部分：一个中间元件，所述左部和右部;两个部件必须具有相同的大小（+ -1），然后形成树木这些零件。这保证了所得到的树是接近平衡（这将是完全平衡的，如果元件的数目是2 ^ N-1）。树的创建应该返回树的高度，这样就可以把平衡方便到每个节点。

修改：假设伊恩Piumarta的 tree.h中，我相信这个算法应该做的伎俩：

Node* tree_build(int key[], int value[], int L, int R) // L and R inclusive
{

  int M;
  Node *middle;
  int lh, rh;

  if(L == R)
    return Node_new(key[L], value[L]);

  if(L+1 == R) {
    Node *left = Node_new(key[L], value[L]);
    Node *right = Node_new(key[R], value[R]);
    left->tree.avl_right = right;
    left->tree.avl_height = 1;
    return left;
  }

  // more than two nodes
  M = L + (R-L)/2;
  middle = Node_new(key[M], value[M]);
  middle->tree.avl_left = tree_build(key, value, L, M-1);
  middle->tree.avl_right = tree_build(key, value, M+1, R);
  lh = middle->tree.avl_left->tree.avl_height;
  rh = middle->tree.avl_right->tree.avl_height;
  middle->tree.avl_height = 1 + (lh > rh ? lh:rh);
  return middle;
}