Interval tree
کمپیوٹر سائنس میں، وقفہ ٹری وقفے کو برقرار رکھنے کے لیے ٹری ڈیٹا ڈھانچہ ہے۔ خاص طور پر، یہ کسی کو ان تمام وقفوں کو مؤثر طریقے سے تلاش کرنے کی اجازت دیتا ہے جو کسی بھی وقفے یا نقطہ کے ساتھ اوورلیپ ہوتے ہیں۔ یہ اکثر ونڈو سوالات کے لیے استعمال ہوتا ہے، مثال کے طور پر، ایک آئتاکار ویو پورٹ کے اندر کمپیوٹرائزڈ نقشے پر تمام سڑکوں کو تلاش کرنے کے لیے، یا تین جہتی منظر کے اندر تمام مرئی عناصر کو تلاش کرنے کے لیے۔ اسی طرح کا ڈیٹا ڈھانچہ سیگمنٹ ٹری ہے۔ معمولی حل یہ ہے کہ ہر وقفے پر جائیں اور جانچ کریں کہ آیا یہ دیئے گئے نقطہ یا وقفے کو کاٹتا ہے، جس کے لیے وقت درکار ہوتا ہے، مجموعہ میں وقفوں کی تعداد کہاں ہے۔ چونکہ کوئی استفسار تمام وقفے واپس کر سکتا ہے، مثال کے طور پر اگر استفسار مجموعہ میں تمام وقفوں کو کاٹتا ہوا ایک بڑا وقفہ ہے، تو یہ غیر علامتی طور پر بہترین ہے۔ تاہم، ہم آؤٹ پٹ حساس الگورتھم پر غور کرکے بہتر کر سکتے ہیں، جہاں رن ٹائم کا اظہار استفسار کے ذریعے پیدا ہونے والے وقفوں کی تعداد کے لحاظ سے کیا جاتا ہے۔ وقفہ درختوں میں استفسار کا وقت اور تخلیق کا ابتدائی وقت ہوتا ہے، جبکہ میموری کی کھپت کو محدود کرتا ہے۔ تخلیق کے بعد، وقفہ درخت متحرک ہو سکتے ہیں، جو وقت کے ساتھ وقفہ کو موثر طریقے سے داخل کرنے اور حذف کرنے کی اجازت دیتے ہیں۔ اگر وقفوں کے اختتامی نکات ایک چھوٹے سے انٹیجر رینج (مثال کے طور پر، رینج میں) کے اندر ہیں، تو تیز اور حقیقت میں بہترین ڈیٹا ڈھانچے پیشگی پروسیسنگ کے وقت اور استفسار کے وقت کے ساتھ موجود ہیں تاکہ وقفوں کی اطلاع دہندگی کے لیے جو ایک دیئے گئے استفسار کے نقطہ پر مشتمل ہو (ایک بہت ہی آسان نقطہ کے لیے دیکھیں)۔ سادہ صورت میں، وقفے اوورلیپ نہیں ہوتے ہیں اور انہیں ایک سادہ بائنری سرچ ٹری میں ڈالا جا سکتا ہے اور وقت کے ساتھ پوچھ گچھ کی جا سکتی ہے۔ تاہم، من مانی طور پر اوور لیپنگ وقفوں کے ساتھ، درخت میں داخل کرنے کے لیے دو وقفوں کا موازنہ کرنے کا کوئی طریقہ نہیں ہے کیونکہ ابتدائی نکات یا اختتامی نکات کے مطابق ترتیبات مختلف ہو سکتے ہیں۔ ایک بے وقوف نقطہ نظر یہ ہو سکتا ہے کہ دو متوازی درختوں کی تعمیر کی جائے، ایک ابتدائی نقطہ سے ترتیب دیا گیا ہے، اور ایک ہر وقفے کے اختتامی نقطہ سے ترتیب دیا گیا ہے۔ اس سے ہر درخت کا آدھا حصہ وقت پر پھینک دیا جا سکتا ہے، لیکن نتائج کو ضم کرنا ضروری ہے، جس میں وقت درکار ہوتا ہے۔ اس سے ہمیں سوالات ملتے ہیں، جو بروٹ فورس سے بہتر نہیں ہے۔ وقفہ درخت اس مسئلے کو حل کرتے ہیں۔ یہ مضمون وقفہ درخت کے لیے دو متبادل ڈیزائنوں کی وضاحت کرتا ہے، جسے مرکزی وقفہ درخت اور بڑھا ہوا درخت کہا جاتا ہے۔ مرکوز وقفہ درخت کے سوالات میں وقفوں کی کل تعداد اور رپورٹ شدہ نتائج کی تعداد کے ساتھ وقت درکار ہوتا ہے۔ تعمیر میں وقت لگتا ہے، اور ذخیرہ کرنے کے لیے جگہ درکار ہوتی ہے۔ نمبر لائن پر وقفوں کے ایک سیٹ کو دیکھتے ہوئے، ہم ایک ڈیٹا ڈھانچہ بنانا چاہتے ہیں تاکہ ہم دوسرے وقفے یا نقطہ کو اوور لیپ کرنے والے تمام وقفوں کو مؤثر طریقے سے بازیافت کرسکیں۔ ہم تمام وقفوں کی پوری رینج لے کر شروع کرتے ہیں اور اسے آدھے حصے میں تقسیم کرتے ہیں (عملی طور پر، درخت کو نسبتا متوازن رکھنے کے لیے منتخب کیا جانا چاہیے)۔ یہ وقفوں کے تین سیٹ دیتا ہے، وہ مکمل طور پر بائیں طرف جن سے ہم کال کریں گے، وہ مکمل طور پر دائیں طرف جن سے ہم کال کریں گے، اور وہ اوور لیپنگ جن سے ہم کال کریں گے۔ وقفے میں اور بار بار اسی انداز میں تقسیم کیے جاتے ہیں جب تک کہ کوئی وقفہ باقی نہ رہے۔ مرکز کے نقطہ کو اوورلیپ کرنے والے وقفے وقفہ درخت میں نوڈ سے منسلک ایک علیحدہ ڈیٹا ڈھانچے میں محفوظ کیے جاتے ہیں۔ یہ ڈیٹا ڈھانچہ دو فہرستوں پر مشتمل ہوتا ہے، ایک میں ان کے ابتدائی نکات کے مطابق ترتیب دیے گئے تمام وقفے ہوتے ہیں، اور دوسرے میں ان کے اختتامی نکات کے مطابق ترتیب دیے گئے تمام وقفے ہوتے ہیں۔ نتیجہ ایک بائنری ٹری ہے جس میں ہر نوڈ اسٹورنگ ہوتا ہے: ایک سینٹر پوائنٹ دوسرے نوڈ کا پوائنٹر جس میں تمام وقفے مکمل طور پر سینٹر پوائنٹ کے بائیں طرف ہوتے ہیں۔ ایک دوسرے نوڈ کا پوائنٹر جس میں تمام وقفے مکمل طور پر سینٹر پوائنٹ کے دائیں طرف ہوتے ہیں۔ سینٹر پوائنٹ کو اوور لیپ کرنے والے تمام وقفے ان کے ابتدائی پوائنٹ کے ذریعہ ترتیب دیئے جاتے ہیں۔ سینٹر پوائنٹ کو اوور لیپ کرنے والے تمام وقفے ان کے اختتامی پوائنٹ انٹرسیکٹنگ کے ذریعہ ترتیب دیئے جاتے ہیں۔ اوپر بنائے گئے ڈیٹا ڈھانچے کو دیکھتے ہوئے، ہمیں حدود یا پوائنٹس پر مشتمل سوالات موصول ہوتے ہیں، اور اس ان پٹ کو اوور لیپ کرنے والے اصل سیٹ میں تمام حدود واپس کردیتے ہیں۔ ایک نقطہ کے ساتھ کام درخت میں ان تمام وقفوں کو تلاش کرنا ہے جو کسی دیئے گئے نقطہ کو اوورلیپ کرتے ہیں۔ ٹری کو اسی طرح کے ریکرسو الگورتھم کے ساتھ چلایا جاتا ہے جیسا کہ روایتی بائنری ٹری کو عبور کرنے کے لیے استعمال کیا جاتا ہے، لیکن ہر نوڈ پر "سینٹر" پوائنٹ کو اوور لیپ کرنے والے وقفوں کو تلاش کرنے میں مدد کے لیے اضافی منطق کے ساتھ۔ ہر ٹری نوڈ کے لیے، اوپر نوڈ کی تعمیر میں استعمال ہونے والے مڈ پوائنٹ سے موازنہ کیا جاتا ہے۔ اگر اس سے کم ہے، تو وقفوں کے سب سے بائیں سیٹ پر غور کیا جاتا ہے۔ اگر اس سے بڑا ہے، تو وقفوں کا سب سے دائیں سیٹ، سمجھا جاتا ہے۔ جیسا کہ ہر نوڈ پر کارروائی کی جاتی ہے جب ہم درخت کو جڑ سے پتی تک لے جاتے ہیں، اس کی حدود پر کارروائی کی جاتی ہے۔ اگر اس سے کم ہے، تو ہم جانتے ہیں کہ تمام وقفے بعد میں ختم ہوتے ہیں، یا وہ بھی اوورلیپ نہیں ہو سکتے۔ لہذا، ہمیں صرف ان وقفوں کو تلاش کرنے کی ضرورت ہے جو اس سے پہلے شروع ہوتے ہیں۔ ہم ان فہرستوں سے مشورہ کر سکتے ہیں جو پہلے ہی بنائی جا چکی ہیں۔ چونکہ ہم اس منظر نامے میں صرف وقفے کے آغاز کی پرواہ کرتے ہیں، اس لیے ہم ابتدا کے لحاظ سے ترتیب دی گئی فہرست سے مشورہ کر سکتے ہیں۔ فرض کریں کہ ہمیں اس فہرست میں قریب ترین نمبر اس سے بڑا نہیں ملتا ہے۔ فہرست کے آغاز سے لے کر اس پائے جانے والے نقطہ تک تمام حدود اوورلیپ ہوتی ہیں کیونکہ وہ پہلے شروع ہوتی ہیں اور بعد میں ختم ہوتی ہیں (جیسا کہ ہم جانتے ہیں کیونکہ وہ اوورلیپ ہوتی ہیں جو اس سے بڑی ہوتی ہیں)۔ اس طرح، ہم صرف فہرست میں وقفوں کی گنتی شروع کر سکتے ہیں جب تک کہ اسٹارٹ پوائنٹ ویلیو زیادہ نہ ہو جائے۔ اسی طرح، اگر اس سے بڑا ہے، تو ہم جانتے ہیں کہ تمام وقفے پہلے شروع ہونے چاہئیں، لہذا ہم ان وقفوں کو تلاش کرتے ہیں جو وقفے کے اختتام کے لحاظ سے ترتیب دی گئی فہرست کو استعمال کرنے کے بعد ختم ہوتے ہیں۔ اگر بالکل مماثل ہو تو، تمام وقفوں کو مزید پروسیسنگ کے بغیر نتائج میں شامل کیا جا سکتا ہے اور ٹری ٹریورسل کو روکا جا سکتا ہے۔ وقفے کے ساتھ نتیجہ کے وقفے کے لیے ہمارے استفسار کے وقفے کو کاٹنے کے لیے درج ذیل میں سے ایک کو برقرار رکھنا چاہیے: کا آغاز اور/یا اختتامی نقطہ اندر ہے ؛ یا مکمل طور پر منسلک ہے۔ ہم سب سے پہلے ایک علیحدہ تعمیر شدہ درخت کا استعمال کرتے ہوئے اندر شروع اور/یا اختتامی نکات کے ساتھ تمام وقفے تلاش کرتے ہیں۔ یک جہتی معاملے میں، ہم ایک سرچ ٹری کا استعمال کر سکتے ہیں جس میں وقفہ سیٹ کے تمام آغاز اور اختتامی نکات ہوتے ہیں، ہر ایک کے ساتھ اس کے متعلقہ وقفے کا اشارہ ہوتا ہے۔ کے آغاز اور اختتام کے لیے وقت پر بائنری سرچ سے غور کرنے کے لیے کم سے کم اور زیادہ سے زیادہ پوائنٹس کا پتہ چلتا ہے۔ اس حد کے اندر ہر نقطہ ایک وقفے کا حوالہ دیتا ہے جو اوورلیپ ہوتا ہے اور نتیجہ کی فہرست میں شامل کیا جاتا ہے۔ نقل سے بچنے کے لیے احتیاط برتی جانی چاہیے، کیونکہ وقفہ اندر شروع اور ختم دونوں ہو سکتا ہے۔ یہ ہر وقفے پر بائنری فلیگ کا استعمال کرتے ہوئے کیا جا سکتا ہے تاکہ یہ نشان لگایا جا سکے کہ اسے نتیجہ سیٹ میں شامل کیا گیا ہے یا نہیں۔ آخر میں، ہمیں ایسے وقفے تلاش کرنے چاہئیں جو محصور ہوں۔ ان کو تلاش کرنے کے لیے، ہم کسی بھی نقطہ کو اندر سے چنتے ہیں اور اس نقطہ کو عبور کرنے والے تمام وقفوں کو تلاش کرنے کے لیے اوپر دیے گئے الگورتھم کا استعمال کرتے ہیں (دوبارہ، نقلوں کو ہٹانے کے لیے محتاط رہنا)۔ اعلی جہتیں وقفہ درخت کے ڈیٹا ڈھانچے کو یکساں استفسار اور تعمیراتی وقت اور جگہ کے ساتھ اعلی جہت میں عام کیا جا سکتا ہے۔ سب سے پہلے، طول و عرض میں ایک رینج ٹری بنایا جاتا ہے جو استفسار کے علاقے کے اندر ابتدائی اور اختتامی نکات کے ساتھ تمام وقفوں کی موثر بازیافت کی اجازت دیتا ہے۔ ایک بار جب متعلقہ حدود مل جاتی ہیں، تو صرف وہی چیز باقی رہ جاتی ہے جو اس خطے کو کسی جہت میں گھیرے ہوئے ہیں۔ ان اوورلیپس کو تلاش کرنے کے لیے، وقفہ کے درخت بنائے جاتے ہیں، اور ہر ایک کے لیے ایک محور کو کاٹ کر پوچھ گچھ کی جاتی ہے۔ مثال کے طور پر، دو جہتوں میں، مربع کے نچلے حصے (یا کوئی دوسری افقی لکیر جو ایک دوسرے کو کاٹتی ہے) سے افقی محور کے لیے بنائے گئے وقفہ درخت کے خلاف پوچھ گچھ کی جائے گی۔ اسی طرح، بائیں (یا کوئی دوسری عمودی لکیر جو ایک دوسرے کو کاٹتی ہے) سے عمودی محور پر بنائے گئے وقفہ درخت کے خلاف پوچھ گچھ کی جائے گی۔ ہر وقفہ درخت کو بھی اعلی طول و عرض کے لیے ایک اضافے کی ضرورت ہوتی ہے۔ ہر نوڈ پر ہم درخت میں گزرتے ہیں، اس کا موازنہ اوورلیپس تلاش کرنے کے لیے کیا جاتا ہے۔ پوائنٹس کی دو ترتیب شدہ فہرستوں کے بجائے جیسا کہ ایک جہتی معاملے میں استعمال کیا گیا تھا، ایک رینج ٹری بنایا جاتا ہے۔ یہ اس اوورلیپ خطے میں تمام نکات کی موثر بازیافت کی اجازت دیتا ہے۔ حذف کرنا اگر ٹری سے وقفہ ہٹانے کے بعد، اس وقفہ پر مشتمل نوڈ میں مزید وقفے نہیں ہوتے ہیں، تو اس نوڈ کو ٹری سے حذف کیا جا سکتا ہے۔ یہ عام بائنری ٹری ڈیلیشن آپریشن سے زیادہ پیچیدہ ہے۔ ایک وقفہ درخت میں کئی نوڈس کے مرکز نقطہ کو اوورلیپ کر سکتا ہے۔ چونکہ ہر نوڈ ان وقفوں کو ذخیرہ کرتا ہے جو اسے اوورلیپ کرتے ہیں، تمام وقفوں کے ساتھ مکمل طور پر بائیں ذیلی درخت میں اس کے مرکز کے بائیں طرف، اسی طرح دائیں ذیلی درخت کے لیے، اس کے بعد یہ ہوتا ہے کہ ہر وقفہ نوڈس کے سیٹ سے جڑ کے قریب نوڈ میں محفوظ ہوتا ہے جس کا مرکز نقطہ یہ اوورلیپ ہوتا ہے۔ بائنری ٹری میں عام حذف کرنے کی کارروائیوں میں (اس صورت میں جہاں نوڈ کو حذف کیا جا رہا ہے اس کے دو بچے ہیں) پتی سے آگے نوڈ کو حذف کیے جانے کی پوزیشن تک فروغ دینا شامل ہے (عام طور پر دائیں ذیلی ٹری کا بائیں سب سے چھوٹا بچہ، یا بائیں ذیلی ٹری کا دائیں سب سے چھوٹا بچہ)۔ اس پروموشن کے نتیجے میں، کچھ نوڈس جو پروموٹڈ نوڈ کے اوپر تھے اس کی اولاد بن جائیں گے۔ ان نوڈس کو ان وقفوں کے لیے تلاش کرنا ضروری ہے جو پروموٹڈ نوڈ کو بھی اوورلیپ کرتے ہیں، اور ان وقفوں کو پروموٹڈ نوڈ میں منتقل کرتے ہیں۔ نتیجے کے طور پر، اس کے نتیجے میں نئے خالی نوڈس بن سکتے ہیں، جنہیں دوبارہ اسی الگورتھم کی پیروی کرتے ہوئے حذف کرنا ضروری ہے۔ توازن وہی مسائل جو حذف کرنے کو متاثر کرتے ہیں وہ گردش کی کارروائیوں کو بھی متاثر کرتے ہیں۔ گردش کو اس غیر متغیر کو برقرار رکھنا چاہیے کہ نوڈس کو جڑ کے جتنا ممکن ہو اتنا قریب ذخیرہ کیا جائے۔ آگمینٹڈ ٹری وقفوں کی نمائندگی کرنے کا ایک اور طریقہ بیان کیا گیا ہے۔ داخل کرنے اور حذف کرنے دونوں میں وقت درکار ہوتا ہے، جس میں داخل کرنے یا حذف کرنے کے عمل سے پہلے درخت میں وقفوں کی کل تعداد ہوتی ہے۔ ایک بڑھا ہوا درخت ایک سادہ ترتیب شدہ درخت سے بنایا جا سکتا ہے، مثال کے طور پر بائنری سرچ ٹری یا سیلف بیلنسنگ بائنری سرچ ٹری، جو وقفوں کی 'کم' اقدار کے مطابق ترتیب دیا جاتا ہے۔ اس کے بعد ہر نوڈ میں ایک اضافی تشریح شامل کی جاتی ہے، جس میں اس نوڈ سے نیچے کے تمام وقفوں میں زیادہ سے زیادہ اوپری قیمت ریکارڈ کی جاتی ہے۔ اس خاصیت کو برقرار رکھنے میں نوڈ کے تمام آباؤ اجداد کو نیچے سے اپ ڈیٹ کرنا شامل ہے جب بھی نوڈ شامل یا حذف کیا جاتا ہے۔ یہ فی نوڈ اضافے یا ہٹانے کے لیے صرف O (h) اقدامات لیتا ہے، جہاں h درخت میں شامل یا ہٹائے گئے نوڈ کی اونچائی ہے۔ اگر داخل کرنے اور حذف کرنے کے دوران درختوں کی کوئی گردش ہوتی ہے، تو متاثرہ نوڈس کو بھی اپ ڈیٹ کرنے کی ضرورت پڑ سکتی ہے۔ اب، یہ معلوم ہوتا ہے کہ دو وقفے اور اوورلیپ صرف اس وقت ہوتے ہیں جب دونوں اور۔ کسی دیئے گئے وقفے کے ساتھ اوور لیپنگ نوڈس کے لیے درختوں کی تلاش کرتے وقت، آپ فوری طور پر چھوڑ سکتے ہیں: نوڈس کے دائیں طرف کے تمام نوڈس جن کی کم قیمت دیئے گئے وقفے کے اختتام سے آگے ہے۔ تمام نوڈس جن کی زیادہ سے زیادہ قیمت دی گئی وقفہ کے آغاز سے نیچے ہے۔ رکنیت کے سوالات کچھ کارکردگی حاصل کی جا سکتی ہے اگر درخت غیر ضروری سفر سے گریز کرتا ہے۔ یہ اس وقت ہو سکتے ہیں جب پہلے سے موجود وقفوں کو شامل کیا جائے یا ان وقفوں کو ہٹا دیا جائے جو موجود نہیں ہیں۔ وقفوں پر کل ترتیب کی تعریف پہلے ان کی نچلی حدود اور پھر ان کی اوپری حدود سے ترتیب دے کر کی جا سکتی ہے۔ پھر، رکنیت کی جانچ وقت پر کی جا سکتی ہے، بمقابلہ ڈپلیکیٹ تلاش کرنے کے لیے درکار وقت اگر وقفے داخل کرنے یا ہٹانے کے لیے وقفے کو اوورلیپ کرتے ہیں۔ اس حل کا فائدہ یہ ہے کہ کسی اضافی ڈھانچے کی ضرورت نہیں ہے۔ تبدیلی سختی سے الگورتھمک ہے۔ نقصان یہ ہے کہ رکنیت کے سوالات میں وقت لگتا ہے۔ متبادل طور پر، میموری کی شرح پر، متوقع مستقل وقت میں رکنیت کے سوالات کو ہیش ٹیبل کے ساتھ لاگو کیا جا سکتا ہے، جسے وقفہ درخت کے ساتھ لاک اسٹیپ میں اپ ڈیٹ کیا جاتا ہے۔ یہ ضروری نہیں کہ میموری کی کل ضرورت کو دوگنا کرے، اگر وقفے قدر کے بجائے حوالہ کے ذریعے محفوظ کیے جائیں۔ جاوا مثال: درخت میں ایک نیا وقفہ شامل کرنا ہر نوڈ کی کلید وقفہ ہی ہوتی ہے، اس لیے نوڈس کو پہلے کم قیمت اور آخر میں اعلی قیمت سے ترتیب دیا جاتا ہے، اور ہر نوڈ کی قیمت وقفے کا اختتامی نقطہ ہے: پبلک وایڈ ایڈ (وقفہ i) {پٹ (i، i.getEnd ()) ؛} جاوا مثال: درخت میں ایک نقطہ یا وقفہ تلاش کرنا وقفہ تلاش کرنے کے لیے، کوئی شخص درخت پر چلتا ہے، کلید (n.getKey ()) اور اعلی قیمت (n.getValue ()) کا استعمال کرتے ہوئے کسی بھی شاخ کو چھوڑ دیتا ہے جو استفسار کو اوورلیپ نہیں کر سکتی۔ سب سے آسان کیس ایک پوائنٹ استفسار ہے:// "p" پر مشتمل تمام وقفوں کو تلاش کریں، جو// نوڈ "n" سے شروع ہوتے ہیں اور فہرست میں مماثل وقفے شامل کرتے ہیں "نتیجہ" عوامی کالعدم تلاش (انٹرول نوڈ n، پوائنٹ p، لسٹ <وقفہ> نتیجہ) {// ایسے نوڈس نہ تلاش کریں جو موجود نہیں ہیں اگر (n = = صفر) واپس آتا ہے ؛// اگر p اس نوڈ اور تمام بچوں میں کسی بھی وقفے// کے دائیں نقطہ کے دائیں طرف ہے، تو کوئی میچ نہیں ہوگا۔ اگر (p.compareTo (n.getValue ())> 0) واپس آتا ہے ؛// بائیں طرف تلاش کریں بچے تلاش کریں (n.getLeft ()، p، نتیجہ) ؛// اس نوڈ کو چیک کریں اگر (n.getKey (). (p) پر مشتمل ہے) result.add (n.getKey ()) ؛// اگر p اس وقفے کے آغاز کے بائیں طرف ہے،// تو یہ کسی بھی بچے میں دائیں طرف نہیں ہو سکتا۔ اگر (p.compareTo (n.getKey (). getStart ()) <0) لوٹتا ہے ؛// بصورت دیگر، بچوں کی صحیح تلاش کریں تلاش کریں (n.getRight ()، p، نتیجہ) ؛} جہاں a.compareTo (b) منفی قدر واپس کرتا ہے اگر a <b a.compareTo (b) صفر واپس کرتا ہے اگر a = b a.compareTo (b) مثبت قدر واپس کرتا ہے اگر a> b وقفہ تلاش کرنے کا کوڈ یکساں ہے، سوائے بیچ میں چیک کے:// اس نوڈ کو چیک کریں اگر (n.getKey (). اوورلیپس کے ساتھ (i)) result.add (n.getKey () ؛ اوورلیپس کے ساتھ () کی تعریف اس طرح کی گئی ہے: عوامی مثال کے طور پر، دو جہتوں کے لیے، درخت کی عجیب سطحوں میں ایکس-کوآرڈینیٹ کے لیے حدود ہو سکتی ہیں، جبکہ یکساں سطحوں میں Y-کوآرڈینیٹ کے لیے حدود ہوتی ہیں۔ یہ نقطہ نظر مؤثر طریقے سے اعداد و شمار کے ڈھانچے کو ایک بڑھا ہوا بائنری ٹری سے بڑھا ہوا کے ڈی ٹری میں تبدیل کرتا ہے، اس طرح اندراج اور حذف کرنے کے لیے توازن کے الگورتھم کو نمایاں طور پر پیچیدہ بنا دیتا ہے۔ ایک آسان حل گھونسلے والے وقفے والے درختوں کا استعمال کرنا ہے۔ سب سے پہلے، Y-کوآرڈینیٹ کی حدود کا استعمال کرتے ہوئے ایک ٹری بنائیں۔ اب، ٹری کے ہر نوڈ کے لیے، ایکس رینج پر ایک اور وقفہ ٹری شامل کریں، ان تمام عناصر کے لیے جن کی Y رینج اس نوڈ کے Y رینج کے برابر ہے۔ اس حل کا فائدہ یہ ہے کہ اسے ایک ہی کوڈ بیس کا استعمال کرتے ہوئے صوابدیدی تعداد میں طول و عرض تک بڑھایا جا سکتا ہے۔ شروع میں، گھونسلے والے درختوں کی اضافی قیمت ممنوع لگ سکتی ہے، لیکن عام طور پر ایسا نہیں ہوتا ہے۔ جیسا کہ پہلے غیر گھونسلے والے حل کے ساتھ، ایک نوڈ فی ایکس کوآرڈینیٹ کی ضرورت ہوتی ہے، جس سے دونوں حلوں کے لیے یکساں تعداد میں نوڈ ملتے ہیں۔ واحد اضافی اوور ہیڈ گھونسلے والے درخت کے ڈھانچے کا ہے، ایک فی عمودی وقفہ۔ یہ ڈھانچہ عام طور پر نہ ہونے کے برابر سائز کا ہوتا ہے، جس میں صرف جڑ نوڈ کی طرف اشارہ ہوتا ہے، اور ممکنہ طور پر نوڈس کی تعداد اور درخت کی گہرائی ہوتی ہے۔ درمیانی یا لمبائی پر مبنی درخت ایک درمیانی یا لمبائی پر مبنی درخت ایک بڑھا ہوا درخت کی طرح ہوتا ہے، لیکن متناسب ہوتا ہے، جس میں بائنری سرچ ٹری وقفوں کے درمیانی نکات کے ذریعہ ترتیب دیا جاتا ہے۔ ہر نوڈ میں زیادہ سے زیادہ مبنی بائنری ڈھیر ہوتا ہے، جو وقفے کی لمبائی (یا لمبائی کے نصف) کے لحاظ سے ترتیب دیا جاتا ہے۔ اس کے علاوہ ہم ہر نوڈ میں ذیلی ٹری کی کم سے کم اور زیادہ سے زیادہ ممکنہ قیمت کو محفوظ کرتے ہیں (اس طرح ہم آہنگی)۔ اوورلیپ ٹیسٹ دو وقفوں کی صرف آغاز اور اختتامی اقدار کا استعمال کرتے ہوئے، کیونکہ، اوورلیپ ٹیسٹ مندرجہ ذیل طریقے سے انجام دیا جا سکتا ہے: اور اس کو مجموعہ اور فرق کا استعمال کرتے ہوئے آسان بنایا جا سکتا ہے: جو اوورلیپ ٹیسٹ کو کم کرتا ہے: وقفہ شامل کرنا ٹری میں نئے وقفے شامل کرنا بائنری سرچ ٹری کے لیے مڈیل ویلیو کو کلید کے طور پر استعمال کرنے کے مترادف ہے۔ ہم نوڈ سے وابستہ بائنری ڈھیر پر زور دیتے ہیں، اور تمام اعلی نوڈس سے وابستہ کم سے کم اور زیادہ سے زیادہ ممکنہ اقدار کو اپ ڈیٹ کرتے ہیں۔ تمام اوور لیپنگ وقفوں کی تلاش آئیے استفسار کے وقفے کے لیے استعمال کریں، اور نوڈ کی کلید کے لیے (وقفوں کے مقابلے میں) روٹ نوڈ سے شروع کرتے ہوئے، ہر نوڈ میں، پہلے ہم چیک کرتے ہیں کہ کیا یہ ممکن ہے کہ ہمارا استفسار کا وقفہ نوڈ کی کم از کم اور زیادہ سے زیادہ اقدار کا استعمال کرتے ہوئے نوڈ سبٹری کے ساتھ اوورلیپ ہو (اگر ایسا نہیں ہے تو، ہم اس نوڈ کے لیے جاری نہیں رکھتے)۔ پھر ہم اس نوڈ کے اندر کے وقفوں کا حساب لگاتے ہیں (نہ کہ اس کے بچوں کے) استفسار کے وقفے کے ساتھ اوورلیپ کرنے کے لیے (جاننا): اور اس کے بائنری ڈھیر پر اس سے بڑے کے لیے استفسار انجام دیتے ہیں۔ پھر ہم نوڈ کے بائیں اور دائیں دونوں بچوں سے گزرتے ہیں، ایک ہی کام کرتے ہوئے۔ بدترین صورت میں، ہمیں بائنری سرچ ٹری کے تمام نوڈس کو اسکین کرنا پڑتا ہے، لیکن چونکہ بائنری ہیپ استفسار زیادہ سے زیادہ ہے، اس لیے یہ قابل قبول ہے (ایک 2 جہتی مسئلہ دونوں جہتوں میں زیادہ سے زیادہ نہیں ہو سکتا) اس الگورتھم سے توقع کی جاتی ہے کہ وہ سرچ آپریشنز کے لیے روایتی وقفہ ٹری (آگمینٹڈ ٹری) سے زیادہ تیز ہو۔ عناصر کو شامل کرنا عملی طور پر تھوڑا سست ہے، حالانکہ ترقی کی ترتیب ایک جیسی ہے۔ حوالہ جات مارک ڈی برگ، مارک وین کریولڈ، مارک اوورمارس، اور اوٹ فرائیڈ شوارزکوف۔ کمپیوٹیشنل جیومیٹری، دوسرا نظر ثانی شدہ ایڈیشن۔ سپرنگر-ورلاگ 2000۔ سیکشن 10.1: وقفہ درخت، پی پی۔ 212-217 فرانکو پی پریپراٹا اور مائیکل ایان شاموس۔ کمپیوٹیشنل جیومیٹری: ایک تعارف۔ سپرنگر-ورلاگ، 1985 بیرونی روابط سی جی اے ایل: سی + + میں کمپیوٹیشنل جیومیٹری الگورتھم لائبریری رینج ٹریز Boost.Icl کے مضبوط نفاذ پر مشتمل ہے جو وقفہ سیٹوں اور نقشوں کے سی + + نفاذ پیش کرتا ہے۔ انٹرول ٹری (ازگر)-اے وی ایل بیلنسنگ کے ساتھ ایک مرکوز وقفہ ٹری، ٹیگ کیے گئے وقفوں کے ساتھ مطابقت رکھتا ہے انٹرول ٹری (سی #)-ایک بڑھا ہوا وقفہ ٹری، جس میں اے وی ایل بیلنسنگ انٹرول ٹری (روبی) ہے-ایک مرکوز وقفہ ٹری، غیر متغیر، ٹیگ کیے گئے وقفوں کے ساتھ مطابقت رکھتا ہے انٹرول ٹری (جاوا)-ایک بڑھا ہوا وقفہ ٹری، جس میں اے وی ایل بیلنسنگ، سپورٹ اوورلیپ، فائنڈ، کلیکشن انٹرفیس، آئی ڈی سے وابستہ وقفے ٹری:: وقفہ:: تیز (پرل/سی)-وقفہ ٹری کی موثر تخلیق اور ہیرا پھیری۔ درختوں کو تلاش کریں