شجرة الاقسام

مثال رسومي لهيكل شجرة الافسام. المثال مبني للاقسام الموضحة في الأسفل.

في علوم الكمبيوتر ، شجرة الأقسام هي هيكل بياني تُستخدم لتخزين المعلومات حول الفواصل أو الأقسام. تسمح بالاستعلام عن أي من الأقسام المخزنة تحوي على نقطة معينة يتم الاستعلام عنها. هيكل بيانات مماثل لها هو شجرة الفواصل .

تستخدم شجرة الاقسام لمجموعة I من لمصفوفة بطول n تعقيد مساحي مساوي ل O ( n log n ) ويمكن إنشاؤها في تعقيد وقتي O ( n log n ). تدعم شجرة الاقسام البحث عن جميع الفواصل الزمنية التي تحتوي على نقطة معينة بزمن ( O (log (n + k )، حيث يمثل k عدد المقاطع التي تحوي النقاط المطلوبة.

تطبيقات شجرة الاقسام تشمل مجالات الهندسة رياضية حاسوبية ونظم المعلومات الجغرافية وتعلم الآلة .

يمكن استخدام شجرة الاقسام ل مصفوفة ذو أبعاد متعددة.

التعريف

الوصف

ليكن S مجموعة من الاقسام. وليكن p1 _، p2 _، ... ، p_m قائمة نقاط نهايات الاقسام الغير مكررة. مرتبة من اليسار إلى اليمين. مثل تقسيم خط الاعداد الحقيقية الناتج عن تلك النقاط. وتسمى مناطق هذا التقسيم بالفواصل الأولية . وبالتالي، فإن الفواصل الأولية هي، من اليسار إلى اليمين:

$(-\infty ,p_{1}),[p_{1},p_{1}],(p_{1},p_{2}),[p_{2},p_{2}],\dots ,(p_{m-1},p_{m}),[p_{m},p_{m}],(p_{m},+\infty )$

وهذا هو قائمة الفواصل الأولية التي تتكون من فواصل مفتوحة بين حدين متتاليين p_i و p_{i +1} ، بالتناوب مع حدود مغلقة تتكون من نقطة نهاية واحدة. يتم التعامل مع النقاط الفردية على أنها قسم منفصل لأن إجابة الاستعلام ليست بالضرورة هي نفسها في الجزء الداخلي من قسم ونقاط نهايتها.

بفرض لدينا مجموعة I من الاقسام أو المقاطع، فإن شجرة الافسامT لـ I يتم بنائها على النحو التالي:

• T هي شجرة ثنائية .
• تتوافق أوراقها مع الفواصل الأولية التي يسببها النقاط النهائية في I ، بطريقة منظمة: الورقة الموجودة في أقصى اليسار تتوافق مع الفاصلة الموجودة في أقصى اليسار، وهكذا. الفاصل الأولي المقابل للورقة v يُشار إليه بـ Int( v ).
• العقد الداخلية لـ T تتوافق مع اقسام تمثل اتحاد الفواصل الأولية. بمعنى ان الفاصلة Int( N ) المقابلة للعقدة N هي اتحاد الفواصل المقابلة للعقد الاوراق التي ستكون ان كان جذر الشجرة هو N. وهذا يعني ايضا أن Int( N ) هي اتحاد الفواصل بين طفليها.
• يقوم كل عقدة أو ورقة v في T تخزن القسم Int( v ) ومجموعة من الاقسام الاصغر، وضلك عبر بعض بنى بيانية. تحتوي هذه المجموعة الفرعية الأساسية للعقدة v على الفواصل [ x, x ′ ] من I بحيث تحتوي [ x, x ′ ] على Int( v ) ولكن لا تحتوي على Int(W), بحيث W اب للعقدة v. وهذا يعني أن كل عقدة في T تخزن الأجزاء التي تمتد عبر اقسامها، ولكنها لا تصل لأقسام عقدتها الاب.

البناء

يمكن بناء شجرة الاقسام من مجموعة اقسام I ، على النحو التالي. أولاً، يتم فرز نقاط النهاية للأقسام الموجودة في I يتم الحصول على الفواصل الأولية من ذلك. وبعد ذلك يتم بناء شجرة ثنائية متوازنة على الفواصل الأولية، ولكل عقدة v يتم تحديد الفاصل Int( v ) الذي تمثله. يبقى علينا حساب المجموعات الفرعية الأساسية للعقد. وللقيام بذلك، يتم إدراج الفواصل الزمنية في I واحدة تلو الأخرى في شجرة الاقسام. يمكن إدراج الفاصل الزمني X = [ x, x′] في شجرة فرعية جذؤها عند العقدة التي رمزها T ، باتباع الإجراء:

• إذا تم تضمين Int( T ) في X ، فخزن X في T ، ثم انهي العملية.
• والا:
  • إذا كان X يتقاطع مع فاصل الطفل الأيسر لـ T ، فأدخل X في هذا الطفل بشكل متكرر.
  • إذا كان X يتقاطع مع فاصل الطفل الأيمن لـ T ، فأدخل X في هذا الطفل بشكل متكرر.

تستغرق اجراء البناء كاملا تعقيد زمني مساوي ل O ( n log n ) ، حيث n يمثل عدد الأجزاء في I

الاستعلامات

استعلاماً في شجرة أقسام تتمثل بنقطة q _x (يجب أن تكون هذه النقطة إحدى أوراق الشجرة)، فترجع الشجرة قائمة بجميع الاقسام المخزنة التي تحتوي على النقطة q _x .

شرح اخر: يُعطى عقدة (شجرة فرعية) v ونقطة استعلام q _x ، يتم إجراء الاستعلام باستخدام الخوارزمية التالية:

1. أرجع جميع الأقسام في I(v) .
2. إذا لم تكن v ورقة:
   • إذا كان q _x في Int(الطفل الأيسر لـ v ) فإن
     • قم بإجراء استعلام في الطفل الأيسر لـ v .
   • إذا كان q _x في Int(الطفل الأيمن لـ v ) فإن
     • قم بإجراء استعلام في الطفل الأيمن من v .

في شجرة الأقسام التي تحوي n قسم، يمكن الإبلاغ عن تلك التي تحتوي على نقطة استعلام معينة في تعقيد زمني O (log n + k )، حيث k هو عدد الاقسام المبلغ عنها.

تعقيد تخزيني

تستخدم شجرة المقطع T لمجموعة I من n قسم تعقيد تخزيني O ( n log n ).

المجموعة I تحتوي دائما على 4n+1 قسم أولي على الأكثر. لأن T عبارة عن شجرة متوازنة ثنائية تحتوي على 4n+1 ورقة على الأكثر، فإن عمقها هو O(log n ). نظرًا لأن أي قسم يتم تخزينها مرتين على الأكثر عند عمق معين من الشجرة، فإن إجمالي كمية التخزين هي O ( n log n ).

استخدام لأبعاد أعلى

يمكن استخدام شجرة الأقسام لبيانات ذو أبعاد فوق احادية، وذلك على شكل أشجار اقسام متعددة المستويات. في النسخ ذو الأبعاد الأعلى، تخزن شجرة الأقسام مجموعة من المستطيلات المتوازية مع المحور، ويمكنها استرداد المستطيلات التي تحتوي على نقطة استعلام معينة. يستخدم الهيكل تخزين O ( n log ^d n )، يمكن الاجابة على الاستعلامات في وقت O (log ^d n ).

ملحوظات

يُدعى الاستعلام الذي يطلب جميع الاقسام التي تحتوي على نقطة معينة باسم الاستعلام الطاعن .

تعتبر شجرة الاقسام أبطئ من شجرة الفواصل لاستعلامات المجال في بُعد واحد، بسبب متطلبات التخزين الأعلى: O ( n log n ) لشجرة الاقسام مقابل O( n ) لشجرة الفواصل. تكمن أهمية شجرة القطاعات في إمكانية تخزين القطاعات داخل المجموعة الفرعية الأساسية لكل عقدة بأي طريقة عشوائية.

القسم n الذي تكون نقاط نهايته في مجال صغير (على سبيل المثال، في النطاق [1, ..., O(n)] . فإن يوجد هياكل بيانات افضل من شجرة الاقسام بوقت معالجة مسبق خطي O(n) ووقت استعلام O (1 + k ) للإبلاغ عن جميع فترات k التي تحتوي على نقطة استعلام معينة.

ميزة أخرى لشجرة الاقسام هي أنه من السهل استخدامها لاستعلامات العد؛ أي الإبلاغ عن عدد الاقسام التي تحتوي على نقطة معينة، بدلاً من الإبلاغ عن الاقسام نفسها. بدلاً من تخزين الفواصل في المجموعات الفرعية الأساسية، يمكن ببساطة تخزين عددها. تستخدم شجرة الاقسام في هذه الحالة تخزينًا خطيًا، وتتطلب وقت استعلام O (log n )، لذلك هي مناسبة لهذا النوع من الاستعلامات.

تاريخ

تم اختراع شجرة الأفسام بواسطة جون بنتلي في عام 1977م؛ كحل ل "لمشاكل مستطيل كلي".

مصادر تم ذكرها

• de Berg، Mark؛ van Kreveld، Marc؛ Overmars، Mark؛ Schwarzkopf، Otfried (2000). "More Geometric Data Structures". Computational Geometry: algorithms and applications (ط. 2nd). Springer-Verlag Berlin Heidelberg New York. DOI:10.1007/978-3-540-77974-2. ISBN:3-540-65620-0.
• http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf

روابط خارجية

• شجرة القطاعات – خوارزميات CP