대규모 콜렉션에서 AVL 트리를 빌드하기위한 효율적인 알고리즘

Question

정렬되지 않은 컬렉션에서 프로그램 중에 몇 번 빌드하는 큰 AVL Tree이 있습니다 (나중에 항목을 삽입/제거하는 데 사용됩니다).

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

내 응용 프로그램 프로파일 링은이 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; 
}