대형 컬렉션에서 AVL 트리를 구축하기위한 효율적인 알고리즘

Question

나는 큰 것을 가지고있다 AVL 트리 분류되지 않은 컬렉션에서 프로그램 중에 시간을 제작합니다 (나중에 품목을 삽입/제거하는 데 사용됩니다).

각 항목에 간단한 삽입물을 사용하는 것보다 더 나은 알고리즘이 있습니까? 먼저 컬렉션을 정렬 한 다음 다르게 구축하는 것이 더 효율적입니까?

내 응용 프로그램의 프로파일 링은이 AVL 건물이 핫스팟 위치임을 알려줍니다.

Answer 1

데이터가 메모리에 편리하게 맞는 경우, 먼저 빠른 소트를 수행하고 트리를 구축하는 것이 모든 일반 삽입을 수행하는 것보다 빠를 것으로 기대합니다.

어레이에서 트리를 만들려면 재귀적인 방식으로 작동하여 트리를 세 부분으로 나누십시오 : 중간 요소, 왼쪽 부분 및 오른쪽 부분; 두 부분 모두 동일한 크기 (+-1)를 가져야 하며이 부분에서 나무를 형성해야합니다. 결과 트리의 균형이 거의 균형이 잡히는 것을 보장합니다 (요소 수가 2^N-1 인 경우 완벽하게 균형을 잡을 수 있습니다). 나무 생성은 나무의 높이를 되돌려 각 노드에 편리하게 균형을 넣을 수 있도록해야합니다.

편집하다: Ian Piumarta 's를 가정합니다 나무 .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;
}