شجرة الفترات

بالنظر إلى مجموعة من${\displaystyle n}$بالنسبة للفترات على خط الأعداد، يلزم إنشاء بنية بيانات بحيث يمكن استرجاع جميع الفترات المتداخلة مع فترة أو نقطة أخرى بكفاءة.

أولاً، يتم أخذ النطاق الكامل لجميع الفترات وتقسيمه إلى نصفين عند${\displaystyle x_{\textrm {center}}}$(في الواقع العملي، ${\displaystyle x_{\textrm {center}}}$ينبغي اختيارها للحفاظ على توازن الشجرة نسبيًا). وهذا يعطي ثلاث مجموعات من الفترات، تلك الموجودة تمامًا على يسار ${\displaystyle x_{\textrm {center}}}$، مُسَمًّى${\displaystyle S_{\textrm {left}}}$أولئك الذين يقعون تمامًا على يمين${\displaystyle x_{\textrm {center}}}$، مُسَمًّى ${\displaystyle S_{\textrm {right}}}$وتلك المتداخلة${\displaystyle x_{\textrm {center}}}$، مُسَمًّى${\displaystyle S_{\textrm {center}}}$.

الفترات في ${\displaystyle S_{\textrm {left}}}$و ${\displaystyle S_{\textrm {right}}}$يتم تقسيمها بشكل متكرر بنفس الطريقة حتى لا يتبقى أي فترات.

الفترات في${\displaystyle S_{\textrm {center}}}$تُخزَّن الفترات التي تتداخل مع نقطة المركز في بنية بيانات منفصلة مرتبطة بالعقدة في شجرة الفترات. تتكون بنية البيانات هذه من قائمتين، إحداهما تحتوي على جميع الفترات مرتبة حسب نقاط بدايتها، والأخرى تحتوي على جميع الفترات مرتبة حسب نقاط نهايتها.

والنتيجة هي شجرة ثنائية تحتوي كل عقدة فيها على ما يلي:

• نقطة مركزية
• مؤشر إلى عقدة أخرى تحتوي على جميع الفترات الزمنية الواقعة بالكامل إلى يسار نقطة المركز
• مؤشر إلى عقدة أخرى تحتوي على جميع الفترات الزمنية الواقعة بالكامل على يمين نقطة المركز
• جميع الفترات المتداخلة مع النقطة المركزية مرتبة حسب نقطة بدايتها
• جميع الفترات المتداخلة مع نقطة المنتصف مرتبة حسب نقطة نهايتها

تتيح أشجار الفترات حساب جميع النطاقات المتداخلة مع أي مدخلات بسرعة.

مع نقطة

المهمة هي إيجاد جميع الفترات في الشجرة التي تتداخل مع نقطة معينة${\displaystyle x}$يتم اجتياز الشجرة باستخدام خوارزمية تكرارية مماثلة لتلك المستخدمة في اجتياز شجرة ثنائية تقليدية، ولكن مع منطق إضافي لدعم البحث عن الفترات المتداخلة مع نقطة "المركز" عند كل عقدة.

لكل عقدة من عقد الشجرة،${\displaystyle x}$مقارنة بـ ${\displaystyle x_{\textrm {center}}}$، وهي نقطة المنتصف المستخدمة في إنشاء العقدة أعلاه. إذا${\displaystyle x}$أقل من ${\displaystyle x_{\textrm {center}}}$، وهي المجموعة الموجودة في أقصى اليسار من الفترات الزمنية، ${\displaystyle S_{\textrm {left}}}$يُؤخذ في الاعتبار. إذا${\displaystyle x}$أكبر من ${\displaystyle x_{\textrm {center}}}$، وهي المجموعة اليمنى من الفترات الزمنية، ${\displaystyle S_{\textrm {right}}}$، يتم أخذه في الاعتبار.

أثناء معالجة كل عقدة أثناء اجتياز الشجرة من الجذر إلى ورقة، فإن النطاقات في ${\displaystyle S_{\textrm {center}}}$تتم معالجتها. إذا${\displaystyle x}$أقل من ${\displaystyle x_{\textrm {center}}}$جميع الفترات في ${\displaystyle S_{\textrm {center}}}$يجب إنهاء الإجازة${\displaystyle x}$أو أنها لا يمكن أن تتداخل أيضًا ${\displaystyle x_{\textrm {center}}}$لذلك، يكفي فقط إيجاد تلك الفترات في${\displaystyle S_{\textrm {center}}}$التي تبدأ قبل${\displaystyle x}$قوائم${\displaystyle S_{\textrm {center}}}$يمكن الرجوع إلى القوائم التي تم إنشاؤها مسبقًا. وبما أن بدايات الفترات فقط هي المهمة في هذا السيناريو، فيمكن فرز القائمة حسب البدايات. إذا كان أقرب رقم لا يزيد عن${\displaystyle x}$إذا وُجدت في هذه القائمة، فإن جميع النطاقات من بداية القائمة إلى تلك النقطة التي تم العثور عليها تتداخل${\displaystyle x}$لأنها تبدأ قبل${\displaystyle x}$وينتهي${\displaystyle x}$(لأنها تتداخل)${\displaystyle x_{\textrm {center}}}$وهو أكبر من${\displaystyle x}$وبالتالي، يمكن تعداد الفترات في القائمة حتى تتجاوز قيمة نقطة البداية${\displaystyle x}$.

وبالمثل، إذا${\displaystyle x}$أكبر من ${\displaystyle x_{\textrm {center}}}$جميع الفترات في ${\displaystyle S_{\textrm {center}}}$يجب أن يبدأ قبل${\displaystyle x}$لذا فإن الفترات التي تنتهي بعد${\displaystyle x}$يمكن العثور عليها باستخدام القائمة المصنفة حسب نهايات الفترات.

لو${\displaystyle x}$يتطابق تمامًا${\displaystyle x_{\textrm {center}}}$جميع الفترات في${\displaystyle S_{\textrm {center}}}$يمكن إضافتها إلى النتائج دون مزيد من المعالجة ويمكن إيقاف عملية اجتياز الشجرة.

يمكن تعميم بنية بيانات شجرة الفترات إلى بُعد أعلى${\displaystyle N}$مع نفس وقت الاستعلام والإنشاء و${\displaystyle O(n\log n)}$فضاء.

أولاً، شجرة نطاق في${\displaystyle N}$تم إنشاء أبعاد تسمح باسترجاع فعال لجميع الفترات ذات نقاط البداية والنهاية داخل منطقة الاستعلام${\displaystyle R}$بمجرد العثور على النطاقات المتناظرة، لا يتبقى سوى النطاقات التي تُحيط بالمنطقة في بُعدٍ ما. ولإيجاد هذه التداخلات، ${\displaystyle N}$يتم إنشاء أشجار الفترات، ويتقاطع محور واحد${\displaystyle R}$يتم الاستعلام عن كل منها. على سبيل المثال، في بعدين، الجزء السفلي من المربع ${\displaystyle R}$(أو أي خط أفقي آخر يتقاطع)${\displaystyle R}$سيتم الاستعلام عن ) مقابل شجرة الفترات التي تم إنشاؤها للمحور الأفقي. وبالمثل، اليسار (أو أي خط رأسي آخر يتقاطع${\displaystyle R}$سيتم الاستعلام عن ) مقابل شجرة الفترات التي تم إنشاؤها على المحور الرأسي.

تحتاج كل شجرة فترات أيضًا إلى إضافة للأبعاد الأعلى. عند كل عقدة نجتازها في الشجرة،${\displaystyle x}$تتم مقارنته بـ ${\displaystyle S_{\textrm {center}}}$لإيجاد نقاط التداخل. بدلاً من قائمتين مرتبتين من النقاط كما هو مستخدم في الحالة أحادية البعد، يتم إنشاء شجرة نطاق. وهذا يسمح باسترجاع جميع النقاط بكفاءة في ${\displaystyle S_{\textrm {center}}}$تلك المنطقة المتداخلة${\displaystyle R}$.

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

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

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

نتيجةً لهذا الترقية، ستصبح بعض العُقد التي كانت أعلى من العقدة المُرَقَّاة تابعةً لها؛ لذا، من الضروري البحث في هذه العُقد عن فترات زمنية تتداخل مع العقدة المُرَقَّاة، ونقل تلك الفترات إلى العقدة المُرَقَّاة. ونتيجةً لذلك، قد ينتج عن هذا ظهور عُقد فارغة جديدة، والتي يجب حذفها باتباع نفس الخوارزمية.

إن نفس المشكلات التي تؤثر على الحذف تؤثر أيضًا على عمليات التدوير؛ يجب أن يحافظ التدوير على الثابت المتمثل في تخزين العقد بالقرب من الجذر قدر الإمكان.

قد يتحسن الأداء قليلاً إذا تجنبت الشجرة عمليات الاجتياز غير الضرورية. قد تحدث هذه العمليات عند إضافة فترات موجودة مسبقاً أو إزالة فترات غير موجودة.

يمكن تعريف ترتيب كلي على الفترات بترتيبها أولاً حسب حدودها الدنيا ثم حسب حدودها العليا. بعد ذلك، يمكن إجراء فحص الانتماء في${\displaystyle O(\log n)}$الوقت، مقابل${\displaystyle O(k+\log n)}$الوقت اللازم للعثور على التكرارات إذا${\displaystyle k}$تتداخل الفترات مع الفترة المراد إدراجها أو إزالتها. يتميز هذا الحل بعدم الحاجة إلى أي هياكل إضافية، فالتغيير خوارزمي بحت. أما عيبه فهو أن استعلامات العضوية تستغرق وقتًا أطول.${\displaystyle O(\log n)}$وقت.

أو بدلاً من ذلك، بمعدل${\displaystyle O(n)}$يمكن تنفيذ استعلامات العضوية المتعلقة بالذاكرة في وقت ثابت متوقع باستخدام جدول تجزئة، يتم تحديثه بالتزامن مع شجرة الفترات. قد لا يؤدي هذا بالضرورة إلى مضاعفة إجمالي متطلبات الذاكرة، إذا تم تخزين الفترات بالمرجع بدلاً من القيمة.

مفتاح كل عقدة هو الفترة نفسها، وبالتالي يتم ترتيب العقد أولاً حسب القيمة المنخفضة وأخيراً حسب القيمة العالية، وقيمة كل عقدة هي نقطة نهاية الفترة:

public void add ( Interval i ) { put ( i , i . getEnd ()); }

للبحث عن فاصل زمني، يتم استعراض الشجرة باستخدام المفتاح ( n.getKey()) والقيمة العالية ( n.getValue()) لاستبعاد أي فروع لا يمكن أن تتداخل مع الاستعلام. أبسط حالة هي استعلام النقطة:

// ابحث عن جميع الفترات التي تحتوي على "p"، بدءًا من // العقدة "n" وإضافة الفترات المطابقة إلى القائمة "result" public void search ( IntervalNode n , Point p , List < Interval > result ) { // لا تبحث في العقد غير الموجودة if ( n == null ) return ;// إذا كانت p على يمين أقصى نقطة يمين أي فاصل زمني // في هذه العقدة وجميع أبنائها، فلن يكون هناك أي تطابق. إذا ( p . compareTo ( n . getValue ()) > 0 ) return ;// البحث عن الأبناء اليساريين search ( n . getLeft (), p , result );// تحقق من هذه العقدة إذا ( n . getKey (). contains ( p )) result . add ( n . getKey ());// إذا كان p على يسار بداية هذه الفترة، // فلا يمكن أن يكون في أي عنصر فرعي على اليمين. إذا ( p . compareTo ( n . getKey (). getStart ()) < 0 ) return ;// وإلا، ابحث عن الأبناء الأيمنين باستخدام search ( n.getRight ( ), p , result ); }

أين

a.compareTo(b)تُرجع قيمة سالبة إذا كانت قيمة a < b

a.compareTo(b)تُرجع القيمة صفر إذا كانت a = b

a.compareTo(b)تُرجع قيمة موجبة إذا كانت a > b

الكود المستخدم للبحث عن فترة زمنية مشابه، باستثناء الفحص الموجود في المنتصف:

// تحقق من هذه العقدة إذا ( n . getKey (). overlapsWith ( i )) result . add ( n . getKey ());

overlapsWith()يُعرَّف على النحو التالي:

public boolean overlapsWith ( Interval other ) { return start . compareTo ( other . getEnd ()) <= 0 && end . compareTo ( other . getStart ()) >= 0 ; }

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

الحل الأبسط هو استخدام أشجار الفترات المتداخلة. أولًا، أنشئ شجرة باستخدام نطاقات الإحداثي y . ثم، لكل عقدة في الشجرة، أضف شجرة فترات أخرى على نطاقات x ، لجميع العناصر التي يكون نطاق y الخاص بها هو نفسه نطاق y الخاص بتلك العقدة .

تتمثل ميزة هذا الحل في أنه يمكن توسيعه ليشمل عددًا عشوائيًا من الأبعاد باستخدام نفس قاعدة التعليمات البرمجية.

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

باستخدام قيمتي البداية والنهاية فقط لفترتين${\displaystyle \left(a_{i},b_{i}\right)}$، ل${\displaystyle i=0,1}$يمكن إجراء اختبار التداخل على النحو التالي:

${\displaystyle a_{0}<b_{1}}$و${\displaystyle a_{1}<b_{0}}$

يمكن تبسيط ذلك باستخدام المجموع والفرق:

${\displaystyle s_{i}=a_{i}+b_{i}}$

${\displaystyle d_{i}=b_{i}-a_{i}}$

مما يقلل اختبار التداخل إلى:

${\displaystyle \left|s_{1}-s_{0}\right|<d_{0}+d_{1}}$

إضافة فترات جديدة إلى الشجرة هي نفسها في شجرة البحث الثنائية باستخدام القيمة الوسطى كمفتاح. نقوم بدفعها.${\displaystyle d_{i}}$على الكومة الثنائية المرتبطة بالعقدة، وتحديث القيم الدنيا والقصوى الممكنة المرتبطة بجميع العقد الأعلى.

لنستخدم${\displaystyle a_{q},b_{q},m_{q},d_{q}}$بالنسبة لفترة الاستعلام، و${\displaystyle M_{n}}$بالنسبة لمفتاح العقدة (مقارنة بـ${\displaystyle m_{i}}$(من الفترات)

بدءًا من العقدة الجذرية، في كل عقدة، نتحقق أولاً مما إذا كان من الممكن أن تتداخل فترة الاستعلام الخاصة بنا مع الشجرة الفرعية للعقدة باستخدام القيم الدنيا والقصوى للعقدة (إذا لم يكن الأمر كذلك، فإننا لا نستمر لهذه العقدة).

ثم نقوم بالحساب${\displaystyle \min \left\{d_{i}\right\}}$لكي تتداخل الفترات الزمنية داخل هذه العقدة (وليس أبنائها) مع فترة الاستعلام (مع العلم بذلك).${\displaystyle m_{i}=M_{n}}$):

${\displaystyle \min \left\{d_{i}\right\}=\left|m_{q}-M_{n}\right|-d_{q}}$

ثم قم بإجراء استعلام على كومة الملفات الثنائية الخاصة بها لـ${\displaystyle d_{i}}$أكبر من${\displaystyle \min \left\{d_{i}\right\}}$

ثم نمر عبر كل من الأبناء الأيسر والأيمن للعقدة، ونفعل الشيء نفسه.

في أسوأ الأحوال، يتعين علينا فحص جميع عقد شجرة البحث الثنائية، ولكن بما أن استعلام الكومة الثنائية هو الأمثل، فهذا مقبول (لا يمكن أن تكون المشكلة ثنائية الأبعاد مثالية في كلا البعدين).

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