شجرة النطاق

شجرة النطاق أحادية البعد على مجموعة من n نقطة هي شجرة بحث ثنائية، والتي يمكن إنشاؤها في${\displaystyle O(n\log n)}$يتم بناء أشجار النطاق في الأبعاد الأعلى بشكل متكرر عن طريق إنشاء شجرة بحث ثنائية متوازنة على الإحداثي الأول للنقاط، ثم، لكل رأس v في هذه الشجرة، يتم إنشاء شجرة نطاق ذات ( d -1) بُعد على النقاط الموجودة في الشجرة الفرعية لـ v . يتطلب بناء شجرة نطاق بهذه الطريقة${\displaystyle O(n\log ^{d}n)}$وقت.

يمكن تحسين وقت الإنشاء هذا لأشجار النطاق ثنائية الأبعاد إلى${\displaystyle O(n\log n)}$[ ^{7 ]} ليكن S مجموعة من n نقطة ثنائية الأبعاد. إذا احتوت S على نقطة واحدة فقط، فأرجع ورقة تحتوي على تلك النقطة. وإلا، فأنشئ البنية المرتبطة بـ ^S ، وهي شجرة نطاق أحادية البعد على الإحداثيات y للنقاط في S. ليكن xm هو متوسط ​​الإحداثي x للنقاط. ولتكن S _{_L} مجموعة النقاط التي إحداثياتها x أقل من أو تساوي xm _، ولتكن S _{_R} مجموعة النقاط التي إحداثياتها x أكبر من xm . أنشئ بشكل متكرر v_{_L} ، وهي شجرة نطاق ثنائية الأبعاد على S_{_L} ، و v_{_R} ، وهي شجرة نطاق ثنائية الأبعاد على S_{_R} . أنشئ رأسًا v _L له الابن الأيسر v _{_L} والابن الأيمن v_{_R} . إذا رتبنا النقاط حسب إحداثياتها y في بداية الخوارزمية، وحافظنا على هذا الترتيب عند تقسيم النقاط حسب إحداثياتها x ، فيمكننا إنشاء البنى المرتبطة بكل شجرة فرعية في وقت خطي. هذا يقلل وقت إنشاء شجرة نطاق ثنائية الأبعاد إلى${\displaystyle O(n\log n)}$كما أنه يقلل من الوقت اللازم لإنشاء شجرة نطاق ذات أبعاد d إلى${\displaystyle O(n\log ^{d-1}n)}$.

يُبلغ استعلام النطاق على شجرة النطاق _عن مجموعة النقاط التي تقع ضمن فترة زمنية محددة. وللإبلاغ عن النقاط التي تقع في الفترة [ x1 , x2 ] ، نبدأ بالبحث عن x1 و _x2 . عند رأس ما في الشجرة، تتباعد مسارات البحث إلى x1 و x2. لنفترض أن _vsplit هو آخر _{رأس يشترك} فيه هذان المساران. لكل رأس v _في مسار البحث من _vsplit إلى x1 ، إذا _كانت القيمة المخزنة عند v أكبر من x1 ، يتم الإبلاغ _عن كل نقطة في الشجرة الفرعية اليمنى لـ v . إذا كانت v ورقة، يتم الإبلاغ عن القيمة المخزنة عند v إذا كانت ضمن فترة الاستعلام. _{وبالمثل} ، يتم الإبلاغ عن جميع النقاط المخزنة في الأشجار الفرعية اليسرى للرؤوس ذات القيم الأقل من x2 على _طول مسار البحث من vsplit إلى x2 _{، ويتم الإبلاغ عن ورقة هذا المسار إذا كانت} ضمن فترة الاستعلام.

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

تتشابه استعلامات النطاق في الأبعاد d . فبدلاً من الإبلاغ عن جميع النقاط المخزنة في الأشجار الفرعية لمسارات البحث، يتم إجراء استعلام نطاق ذي ( d -1) بُعد على البنية المرتبطة بكل شجرة فرعية. وفي النهاية، سيتم إجراء استعلام نطاق أحادي البُعد، وسيتم الإبلاغ عن النقاط الصحيحة. بما أن استعلامًا ذا أبعاد d يتكون من${\displaystyle O(\log n)}$بالنسبة للاستعلامات عن نطاق ذي أبعاد ( d -1)، فإن الوقت اللازم لإجراء استعلام عن نطاق ذي أبعاد d هو${\displaystyle O(\log ^{d}n+k)}$حيث k هو عدد النقاط في فترة الاستعلام. ويمكن اختزال ذلك إلى${\displaystyle O(\log ^{d-1}n+k)}$باستخدام شكل مختلف من التتالي الجزئي . ^{[ 2 ] [ 4 ] [ 7 ]}