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

Question

我有一个很大的 AVL 树，我在程序期间从未排序的集合中构建了几次（它将稍后用于插入/删除项目）。

有没有比在每个项目上使用简单插入更好的算法？首先对集合进行排序，然后尝试以不同的方式构建它会更有效吗？

对我的应用程序的分析表明，该 AVL 大楼是一个热点位置。

Answer 1

如果数据可以方便地装入内存，我确实希望首先进行快速排序，然后从中构建树会比执行所有常规插入更快。

要从数组构建树，请以递归方式操作，将树分为三个部分：中间元素、左侧部分和右侧部分；两个部分必须具有相同的大小（+-1），然后用这些部分形成树。这保证了生成的树几乎是平衡的（如果元素的数量是 2^n-1，它将是完美平衡的）。树的创建应该返回树的高度，以便您可以方便地将平衡放入每个节点。

编辑：假设 Ian 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;
}