Effiziente Algorithmen für den Aufbau eines AVL-Baum aus großen Sammlung

Question

Ich habe ein großer AVL-Baum die ich einige Male während Programms aus einer unsortierten Sammlung bauen (es wird verwendet werden, um Elemente einfügen / entfernen später).

Gibt es einen besseren Algorithmus als die für jedes Element des einfachen Einsatz verwendet? Wird es effizienter sein, die Sammlung zunächst zu sortieren und dann versuchen, es anders zu bauen?

Profilieren meiner Bewerbung sagt mir, dass diese AVL Gebäude ein Hotspot Lage ist.

Answer 1

Wenn bequem die Daten in den Speicher passen, würde ich in der Tat davon aus, dass eine quicksort tun ersten und den Bau der Baum aus, dass schneller sein würde als alle regulären Einfügungen zu tun.

den Baum von einem Array zu bauen, zu betreiben in einer rekursiven Art und Weise, um den Baum in drei Teile aufgeteilt: ein Mittelelement, den linken Teil und den rechten Teil; beide Teile die gleiche Größe (+ -1) haben müssen, bilden dann Bäume dieser Teile aus. Das garantiert, dass der resultierende Baum nahezu ausgeglichen ist (es wird perfekt ausgeglichen sein, wenn die Anzahl der Elemente 2 ^ n-1). Baum Schöpfung sollte die Höhe des Baumes zurückkehren, so dass Sie das Gleichgewicht bequem in jeden Knoten setzen können.

Bearbeiten : Unter der Annahme, Ian Piumarta tree.h ich glaube, diesen Algorithmus sollte es tun:

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;
}