خوارزمية فعالة لبناء شجرة AVL من مجموعة كبيرة

Question

لدي كبير شجرة أفغل التي أقوم بإنشاء بعض الأوقات أثناء البرنامج من مجموعة غير مصنفة (سيتم استخدامها لإدراج / إزالة العناصر لاحقا).

هل هناك أي خوارزمية أفضل من استخدام إدراج بسيط في كل عنصر؟ هل سيكون أكثر كفاءة لفرز المجموعة أولا ثم حاول بناءه بشكل مختلف؟

يخبرني بتوطام طلبي أن هذا المبنى AVL هو موقع نقطة ساخنة.

Answer 1

إذا كانت البيانات تتناسب بسهولة في الذاكرة، فسوف تتوقع بالفعل القيام ب Quicksort أولا، وبناء شجرة من ذلك سيكون أسرع من القيام بكل الإدراج المنتظم.

لبناء الشجرة من صفيف، تعمل بطريقة متكررة، تقسيم الشجرة إلى ثلاثة أجزاء: عنصر متوسط، الجزء الأيسر، والجزء الصحيح؛ يجب أن تحتوي كلا الجزأين بنفس الحجم (+ -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;
}