شجرة قطاعات

البناء

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

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

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

الوصف

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

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

T هي شجرة ثنائية .

وفي هذا الصدد، العقد الداخلية لـ T تتوافق مع اقسام تمثل اتحاد الفواصل الأولية. بمعنى ان الفاصلة Int( N ) المقابلة للعقدة N هي اتحاد الفواصل المقابلة للعقد الاوراق التي ستكون ان كان جذر الشجرة هو N. وهذا يعني ايضا أن Int( N ) هي اتحاد الفواصل بين طفليها.

وفي السياق ذاته، يقوم كل عقدة أو ورقة v في T تخزن القسم Int( v ) ومجموعة من الاقسام الاصغر، وضلك عبر بعض بنى بيانية. تحتوي هذه المجموعة الفرعية الأساسية للعقدة v على الفواصل [ x, x ′ ] من بحيث تحتوي [ x, x ′ ] على Int( v ) ولكن لا تحتوي على Int(W), بحيث W اب للعقدة v. وهذا يعني أن كل عقدة في T تخزن الأجزاء التي تمتد عبر اقسامها، ولكنها لا تصل لأقسام عقدتها الاب.

وفي هذا الصدد، تتوافق أوراقها مع الفواصل الأولية التي يسببها النقاط النهائية في ، بطريقة منظمة: الورقة الموجودة في أقصى اليسار تتوافق مع الفاصلة الموجودة في أقصى اليسار، وهكذا. الفاصل الأولي المقابل للورقة v يُشار إليه بـ Int( v ).

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

الاستعلامات

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

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

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

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

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

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

ملحوظات

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

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

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

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

تاريخ

مراجع

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

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

روابط خارجية

علاوةً على ذلك، http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf

تعقيد تخزيني

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

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