Top tree
ٹاپ ٹری ایک ڈیٹا ڈھانچہ ہے جو بائنری ٹری پر مبنی غیر جڑ والے متحرک درختوں کے لیے ہے جو بنیادی طور پر راستے سے متعلق مختلف کارروائیوں کے لیے استعمال ہوتا ہے۔ یہ سادہ تقسیم اور فتح الگورتھم کی اجازت دیتا ہے۔ اس کے بعد سے اسے درخت کی متحرک طور پر مختلف خصوصیات جیسے قطر، مرکز اور میڈین کو برقرار رکھنے کے لیے بڑھایا گیا ہے۔ ایک اوپری درخت کی تعریف ایک بنیادی درخت اور زیادہ سے زیادہ دو عمودی حصوں کے ایک سیٹ کے لیے کی جاتی ہے جسے بیرونی باؤنڈری ورٹیسیس گلوسری باؤنڈری نوڈ کہا جاتا ہے۔ ایک منسلک ذیلی درخت میں ایک چوٹی باؤنڈری ورٹیکس ہے اگر یہ ذیلی درخت کے باہر کسی سرے سے کسی کنارے سے منسلک ہو۔ بیرونی باؤنڈری ورٹیسیس اوپری درخت میں عمودی چوٹیوں کے جوڑے تک کو بیرونی باؤنڈری ورٹیسیس کہا جا سکتا ہے، انہیں کلسٹر کے باؤنڈری ورٹیسیس کے طور پر سمجھا جا سکتا ہے جو پورے اوپری درخت کی نمائندگی کرتا ہے۔ کلسٹر ایک جڑا ہوا ذیلی درخت ہے جس میں زیادہ سے زیادہ دو باؤنڈری ورٹیسز ہوتے ہیں۔ کسی دیئے گئے کلسٹر کے باؤنڈری ورٹیسیس کے سیٹ کو اس طرح ظاہر کیا جاتا ہے کہ ہر کلسٹر کے ساتھ صارف کچھ میٹا معلومات کو منسلک کر سکتا ہے اور اسے مختلف اندرونی کارروائیوں کے تحت برقرار رکھنے کے طریقے دے سکتا ہے۔ پاتھ کلسٹر اگر کم از کم ایک کنارے پر مشتمل ہو تو اسے پاتھ کلسٹر کہا جاتا ہے۔ پوائنٹ کلسٹر دیکھیں لیف کلسٹر لیف کلسٹر اگر اس میں کوئی کنارہ نہیں ہے یعنی صرف ایک باؤنڈری ورٹیکس ہے تو اسے لیف کلسٹر کہا جاتا ہے۔ ایک واحد کنارے پر مشتمل کلسٹر کو ایج کلسٹر کہا جاتا ہے۔ لیف ایج کلسٹر اصل کلسٹر میں ایک لیف کی نمائندگی ایک کلسٹر کے ذریعے کی جاتی ہے جس میں صرف ایک باؤنڈری ورٹیکس ہوتا ہے اور اسے لیف ایج کلسٹر کہا جاتا ہے۔ دو باؤنڈری نوڈس والے پاتھ ایج کلسٹرز کو پاتھ ایج کلسٹر کہا جاتا ہے۔ اندرونی نوڈ میں ایک نوڈ کو کلسٹر پاتھ کا اندرونی نوڈ کہا جاتا ہے۔ باؤنڈری ورٹیسز کے درمیان کے راستے کو کلسٹر پاتھ کہا جاتا ہے اور اسے مرجیبل کلسٹرز ٹو کلسٹرز سے ظاہر کیا جاتا ہے اور اگر سنگلٹن سیٹ ہو (ان میں بالکل ایک نوڈ مشترک ہو) اور یہ ایک کلسٹر ہو تو وہ ضم ہونے کے قابل ہوتے ہیں۔ تعارف اوپر کے درختوں کا استعمال لنک اور کٹ آپریشن کے تحت متحرک جنگل (درختوں کے سیٹ) کو برقرار رکھنے کے لیے کیا جاتا ہے۔ بنیادی خیال یہ ہے کہ اصل درخت میں نوڈس کی تعداد میں لوگرتھمک اونچائی کے متوازن بائنری ٹری کو برقرار رکھا جائے (یعنی۔ وقت میں) ؛ اوپر کا درخت بنیادی طور پر کلسٹرز میں اصل درخت کی تکراری ذیلی تقسیم کی نمائندگی کرتا ہے۔ عام طور پر درخت کے کناروں پر وزن ہو سکتا ہے۔ اصل درخت کے کناروں اور اوپری درخت کے پتی کے نوڈس کے ساتھ ایک سے ایک خط و کتابت ہوتا ہے اور اس کا ہر اندرونی نوڈ ایک کلسٹر کی نمائندگی کرتا ہے جو کلسٹرز کے اتحاد کی وجہ سے بنتا ہے جو اس کے بچے ہیں۔ اوپر کے درخت کے ڈیٹا ڈھانچے کو وقت پر شروع کیا جا سکتا ہے۔ لہذا () کے اوپر کا درخت ایک بائنری درخت ہے جس کے نوڈس () کے کلسٹر ہیں۔ کے پتے بہن بھائی کے کلسٹر کے کناروں کے پڑوسی ہیں اس معنی میں کہ وہ ایک ہی سرے میں کاٹتے ہیں، اور پھر ان کا پیرنٹ کلسٹر ان کا اتحاد ہے۔ کی جڑ خود درخت ہے، جس میں زیادہ سے زیادہ دو بیرونی باؤنڈری ورٹیسز ہوتے ہیں۔ ایک واحد سرے والے درخت میں ایک خالی اوپری درخت ہوتا ہے، اور جس کے صرف ایک کنارے ہوتا ہے وہ صرف ایک نوڈ ہوتا ہے۔ یہ درخت آزادانہ طور پر قابل اضافہ ہیں جو صارف کو ڈیٹا ڈھانچے کے اندرونی کام کی تفصیلات میں جانے کے بغیر لچک اور پیداواری صلاحیت کی وسیع اقسام کی اجازت دیتے ہیں، جسے بلیک باکس بھی کہا جاتا ہے۔ متحرک کارروائیاں درج ذیل تین صارف کے قابل اجازت فاریسٹ اپ ڈیٹس ہیں۔ لنک (v، w): مختلف درختوں 1 اور 2 میں عمودی کہاں اور کہاں ہیں۔ یہ وی ڈبلیو کٹ (وی، ڈبلیو) کی نمائندگی کرنے والا ایک واحد اوپری درخت واپس کرتا ہے: اوپری درخت والے درخت کے کنارے کو ہٹا دیتا ہے جس سے اسے دو درختوں وی اور ڈبلیو میں تبدیل کر دیتا ہے اور دو اوپری درختوں وی اور ڈبلیو کو واپس کرتا ہے۔ ایکسپوز (ایس): اسے اوپری درخت پر زیادہ تر سوالات کو لاگو کرنے کے لیے سبروٹین کہا جاتا ہے۔ زیادہ سے زیادہ 2 عمودی پر مشتمل ہے۔ یہ اصل بیرونی عمودی کو عام عمودی بناتا ہے اور اوپری درخت کے نئے بیرونی باؤنڈری عمودی سے عمودی بناتا ہے۔ اگر خالی نہیں ہے تو یہ نیا روٹ کلسٹر ایکسپوز ({v, w}) کے ساتھ واپس کرتا ہے اگر عمودی مختلف درختوں سے ہوں تو ناکام ہوجاتا ہے۔ اندرونی کارروائیاں جنگل کی تمام اپ ڈیٹس زیادہ تر اندرونی کارروائیوں کے سلسلے کے ذریعے انجام دی جاتی ہیں، جس کی ترتیب کا حساب مزید وقت میں لگایا جاتا ہے۔ ایسا ہو سکتا ہے کہ ٹری اپ ڈیٹ کے دوران، پتی کا جھنڈ پاتھ جھنڈ اور اس کے برعکس میں تبدیل ہو جائے۔ ٹاپ ٹری کی اپ ڈیٹس خصوصی طور پر ان اندرونی کارروائیوں کے ذریعے کی جاتی ہیں۔ ہر اندرونی آپریشن سے وابستہ صارف کے متعین فنکشن کو کال کرکے اسے اپ ڈیٹ کیا جاتا ہے۔ یہاں ضم کریں اور ضم ہونے والے کلسٹرز ہیں، یہ بنیادی کلسٹر کے طور پر واپس آتا ہے اور اور باؤنڈری عمودی کے ساتھ کمپیوٹس کے باؤنڈری عمودی کے طور پر استعمال کرتا ہے اور تقسیم کرتا ہے یہاں جڑ کلسٹر ہے یہ کلسٹر کو اپ ڈیٹ کرتا ہے اور استعمال کرتا ہے اور اس سے حذف کرتا ہے۔ اسپلٹ کو عام طور پر کلین میتھڈ کا استعمال کرتے ہوئے لاگو کیا جاتا ہے جو صارف کے طریقہ کار کو اپ ڈیٹس اور استعمال اور اپ ڈیٹس کے لیے کال کرتا ہے تاکہ یہ معلوم ہو کہ اس کے بچوں میں کسی زیر التواء اپ ڈیٹ کی ضرورت نہیں ہے۔ تھان کو صارف کے متعین افعال کو کال کیے بغیر خارج کر دیا جاتا ہے۔ سوالات کے لیے اکثر تقسیم کرنے کی ضرورت کے بغیر کلین کی ضرورت ہوتی ہے۔ اگر اسپلٹ کلین سبروٹین کا استعمال نہیں کرتا ہے، اور کلین کی ضرورت ہے، تو اس کا اثر اوور ہیڈ کے ساتھ ضم اور اسپلٹ کو ملا کر حاصل کیا جا سکتا ہے۔ اگلے دو افعال مندرجہ بالا دو کے مترادف ہیں اور بیس کلسٹرز کے لیے استعمال ہوتے ہیں۔ کنارے کے سیٹ کے لیے ایک کلسٹر بنائیں شروع سے شمار کیا جاتا ہے۔ ایراڈیکیٹ ایج کلسٹر ہے۔ صارف کے بیان کردہ فنکشن کو پروسیس کرنے کے لیے کہا جاتا ہے اور اس کے بجائے کلسٹر کو اوپر والے درخت سے حذف کر دیا جاتا ہے۔ غیر مقامی تلاش صارف چوز آپریشن کی وضاحت کر سکتا ہے جو جڑ (غیر پتی) کلسٹر کے لیے اپنے چائلڈ کلسٹر میں سے کسی ایک کا انتخاب کرتا ہے۔ ٹاپ ٹری بلیک باکس سرچ روٹین فراہم کرتا ہے، جو چوز کوریریز اور ٹاپ ٹری کی تنظیم نو (اندرونی کارروائیوں کا استعمال کرتے ہوئے) کو اس طرح منظم کرتا ہے کہ یہ تمام منتخب کلسٹرز کے چوراہے میں واحد کنارے کا پتہ لگاتا ہے۔ بعض اوقات تلاش کسی راستے تک محدود ہونی چاہیے۔ اس طرح کے مقاصد کے لیے غیر مقامی تلاش کی ایک قسم ہے۔ اگر جڑ کے کلسٹر میں دو بیرونی باؤنڈری عمودی ہیں، تو کنارے کو صرف راستے پر تلاش کیا جاتا ہے۔ مندرجہ ذیل ترمیم کرنا کافی ہے: اگر روٹ کلسٹر بچوں میں سے صرف ایک پاتھ کلسٹر ہے، تو اسے چوز آپریشن کو کال کیے بغیر ڈیفالٹ طور پر منتخب کیا جاتا ہے۔ غیر مقامی تلاش کی مثالیں = ایکسپوز ({v, w}) کے بعد سرچ () کے ساتھ مناسب چوز کے ذریعے طویل راستے پر آئی-تھ ایج تلاش کیا جا سکتا ہے۔ چوز کو لاگو کرنے کے لیے ہم گلوبل متغیر کی نمائندگی کرتے ہیں اور گلوبل متغیر کی نمائندگی کرتے ہیں۔ چوز کلسٹر کو منتخب کرتا ہے جس کی لمبائی کم از کم آئی ایف ایف ہے۔ آپریشن کو سپورٹ کرنے کے لیے لمبائی کو برقرار رکھنا ضروری ہے۔ غیر اکائی لمبائی والے کناروں والے گراف کے لیے بھی اسی طرح کا کام وضع کیا جا سکتا ہے۔ اس صورت میں فاصلہ دو کناروں کے درمیان کسی کنارے یا سرے سے خطاب کر سکتا ہے۔ ہم چوز کی تعریف اس طرح کر سکتے ہیں کہ ورٹیکس کی طرف جانے والا کنارہ مؤخر الذکر صورت میں واپس آ جائے۔ ایک مستقل کے ذریعے راستے کے تمام کناروں کی لمبائی میں اضافہ کرنے والی متعین اپ ڈیٹ ہو سکتی ہے۔ ایسے منظر نامے میں یہ اپڈیٹس صرف روٹ کلسٹر میں مستقل وقت میں کی جاتی ہیں۔ بچوں کو تاخیر سے اپ ڈیٹ تقسیم کرنے کے لیے کلین کی ضرورت ہوتی ہے۔ چوز کو کال کرنے سے پہلے کلین کو کال کیا جانا چاہیے۔ لمبائی کو برقرار رکھنے کے لیے اس صورت میں یونٹ کی لمبائی کو بھی برقرار رکھنے کی ضرورت ہوگی۔ سرے پر مشتمل درخت کا مرکز تلاش کرنا یا تو دو مرکز کے کنارے یا کنارے کو تلاش کرکے کیا جا سکتا ہے جس کا مرکز ایک اختتامی نقطہ کے طور پر ہو۔ کنارے کو = ایکسپوز ({v}) کے بعد سرچ () کے ساتھ مناسب چوز کے ذریعے پایا جا سکتا ہے۔ انتخاب زیادہ سے زیادہ فاصلے والے بچے کے ساتھ بچوں کے درمیان انتخاب کرتا ہے۔ آپریشن کو سپورٹ کرنے کے لیے کلسٹر سبٹری میں باؤنڈری ورٹیکس سے زیادہ سے زیادہ فاصلہ برقرار رکھا جانا چاہیے۔ اس کے لیے کلسٹر راستے کی لمبائی کی دیکھ بھال کی بھی ضرورت ہوتی ہے۔ دلچسپ نتائج اور ایپلی کیشنز اصل میں دوسرے طریقوں سے نافذ کردہ متعدد دلچسپ ایپلی کیشنز کو ٹاپ ٹری کے انٹرفیس کا استعمال کرتے ہوئے آسانی سے لاگو کیا گیا ہے۔ ان میں سے کچھ میں شامل ہیں ([سلیٹر اور ٹارجن 1983])۔ ہم فی لنک اور کٹ کے وقت میں وزن والے درختوں کا متحرک مجموعہ برقرار رکھ سکتے ہیں، وقت میں کسی بھی دو عمودی کے درمیان زیادہ سے زیادہ کنارے کے وزن کے بارے میں سوالات کی حمایت کرتے ہیں۔ ثبوت کا خاکہ: اس میں ہر نوڈ پر اس کے کلسٹر راستے پر زیادہ سے زیادہ وزن (میکس _ ڈبلیو ٹی) کو برقرار رکھنا شامل ہے، اگر یہ ایک پوائنٹ کلسٹر ہے تو میکس _ ڈبلیو ٹی () کو اس طرح شروع کیا جاتا ہے جب ایک کلسٹر دو کلسٹرز کا اتحاد ہوتا ہے تو یہ دو ضم شدہ کلسٹرز کی زیادہ سے زیادہ قیمت ہوتی ہے۔ اگر ہمیں اور اس کے درمیان زیادہ سے زیادہ ڈبلیو ٹی تلاش کرنا ہے تو ہم ایکسپوز کرتے ہیں اور رپورٹ کرتے ہیں۔ مندرجہ بالا ایپلی کیشن کے منظر نامے میں ہم وقت پر دیے گئے راستے کے تمام کناروں پر ایک مشترکہ وزن بھی شامل کر سکتے ہیں۔ ثبوت کا خاکہ: ہم ایک وزن متعارف کراتے ہیں جسے اضافی () کہا جاتا ہے جسے تمام کناروں میں شامل کیا جاتا ہے جس میں مناسب طریقے سے برقرار رکھا جاتا ہے۔ تقسیم () کے لیے ضروری ہے کہ، ہم ہر راستے کے لیے بچے کو زیادہ سے زیادہ _ ڈبلیو ٹی (اے): = زیادہ سے زیادہ _ ڈبلیو ٹی () + اضافی () اور اضافی (): = اضافی () + اضافی () مقرر کریں۔ کے لیے: = شامل کریں ()، ہم مقرر کرتے ہیں میکس _ ڈبلیو ٹی (): = میکس {میکس _ ڈبلیو ٹی ()، میکس _ ڈبلیو ٹی ()} اور اضافی (): = 0۔ آخر میں، راستے پر زیادہ سے زیادہ وزن تلاش کرنے کے لیے ہم مقرر کرتے ہیں: = ظاہر کریں اور زیادہ سے زیادہ _ ڈبلیو ٹی () واپس کریں۔ ([گولڈبرگ ایٹ آل۔ 1991])۔ ہم وقت پر دیئے گئے سرے پر مشتمل بنیادی درخت میں زیادہ سے زیادہ وزن مانگ سکتے ہیں۔ ثبوت کا خاکہ: اس کے لیے ضم اور تقسیم کی کارروائیوں کے تحت کلسٹر میں زیادہ سے زیادہ وزن والے غیر کلسٹر راستے کے کنارے کے بارے میں اضافی معلومات کو برقرار رکھنے کی ضرورت ہوتی ہے۔ دو چوٹیوں کے درمیان فاصلہ اور وقت میں لمبائی کے طور پر پایا جا سکتا ہے (ظاہر کریں)۔ ثبوت کا خاکہ: ہم کلسٹر راستے کی لمبائی () کو برقرار رکھیں گے۔ لمبائی کو زیادہ سے زیادہ وزن کے طور پر برقرار رکھا جاتا ہے سوائے اس کے کہ، اگر جوڑ (ضم) کے ذریعہ بنایا گیا ہے، تو لمبائی () اس کے راستے کے بچوں کے ساتھ ذخیرہ شدہ لمبائی کا مجموعہ ہے۔ درخت کے قطر اور اس کے بعد کی دیکھ بھال کے بارے میں سوالات میں وقت لگتا ہے۔ سینٹر اور میڈین مجھے لنک (ضم) اور کٹ (تقسیم) کارروائیوں کے تحت برقرار رکھ سکتے ہیں اور وقت پر غیر مقامی تلاش کے ذریعے پوچھ گچھ کر سکتے ہیں۔ اوپر کے درختوں کو متحرک دو کنارے والے رابطے کے لیے جدید ترین الگورتھم میں استعمال کیا جاتا ہے۔ اس مسئلے میں، متحرک رابطے کی طرح، گراف کنارے کو حذف کرنے اور داخل کرنے کے ساتھ ساتھ یہ پوچھنے والے سوالات سے مشروط ہے کہ آیا عمودی کا ایک جوڑا دو کنارے سے جڑا ہوا ہے، یا ان کو الگ کرنے والا کوئی پل ہے۔ ہولم، ڈی لکٹنبرگ، اور تھورپ ایک تعیناتی الگورتھم دیتے ہیں جس میں ادائیگی شدہ اپ ڈیٹ کا وقت، اور استفسار کا وقت ہوتا ہے۔ ہولم، روٹن برگ، اور تھورپ کے بعد کے کام نے اسے اپ ڈیٹ کے وقت میں بہتر بنایا ہے، جس میں ٹاپ ٹریز کا بھی استعمال کیا گیا ہے۔ گراف کو برقرار رکھا جا سکتا ہے جس سے ایج سیٹ کو اپ ڈیٹ کیا جا سکتا ہے اور ورٹیکس 2-کنیکٹوٹی پر سوالات پوچھے جا سکتے ہیں۔ اپ ڈیٹس کی تخفیف شدہ پیچیدگی ہے۔ سوالات کو اور بھی تیزی سے نافذ کیا جا سکتا ہے۔ الگورتھم معمولی نہیں ہے، جگہ کا استعمال کرتا ہے۔ اوپر کے درختوں کو درختوں کو اس طرح سے کمپریس کرنے کے لیے استعمال کیا جا سکتا ہے جو کبھی بھی ڈی اے جی کمپریشن سے زیادہ بدتر نہیں ہوتا، لیکن یہ تیزی سے بہتر ہو سکتا ہے۔ نفاذ ٹاپ ٹریز کو مختلف طریقوں سے نافذ کیا گیا ہے، ان میں سے کچھ میں ملٹی لیول پارٹیشن (ٹاپ ٹریز اور ڈائنامک گراف الگورتھم جیکب ہولم اور کرسٹیئن ڈی لیکٹن برگ) کا استعمال کرتے ہوئے عمل درآمد شامل ہے۔ تکنیکی رپورٹ)، اور یہاں تک کہ سلیٹر-ٹارجن ایس-ٹی درختوں کا استعمال کرتے ہوئے (عام طور پر وقت کی حدود کے ساتھ)، فریڈرکسن کے ٹوپولوجی درخت (بدترین صورت میں وقت کی حدود کے ساتھ) (السٹرپ اور دیگر۔ اوپر کے درختوں کے ساتھ مکمل طور پر متحرک درختوں میں معلومات کو برقرار رکھنا)۔ تخفیف شدہ نفاذ زیادہ آسان ہوتے ہیں، اور وقت کی پیچیدگی میں چھوٹے ضرب والے عوامل کے ساتھ۔ اس کے برعکس بدترین صورت حال کے نفاذ استفسار کے دوران غیر ضروری معلومات کی تازہ کاریوں کو بند کرکے سوالات کو تیز کرنے کی اجازت دیتے ہیں (استقامت کی تکنیکوں کے ذریعے نافذ کیا جاتا ہے)۔ استفسار کا جواب دینے کے بعد اوپر والے درخت کی اصل حالت استعمال کی جاتی ہے اور استفسار ورژن کو خارج کر دیا جاتا ہے۔ ملٹی لیول پارٹیشننگ کا استعمال کرتے ہوئے کسی درخت کے کلسٹرز کی کسی بھی پارٹیشننگ کی نمائندگی کلسٹر پارٹیشن ٹری سی پی ٹی کے ذریعے درخت کے ہر کلسٹر کو کنارے سے بدل کر کی جا سکتی ہے۔ اگر ہم تقسیم کرنے کے لیے حکمت عملی P استعمال کرتے ہیں تو CPT CPTP ہوگا۔ یہ اس وقت تک بار بار کیا جاتا ہے جب تک کہ صرف ایک کنارے باقی نہ رہ جائے۔ ہم دیکھیں گے کہ متعلقہ اوپری درخت کے تمام نوڈس کو اس کثیر سطحی تقسیم کے کناروں میں منفرد طور پر نقشہ بنایا گیا ہے۔ ملٹی لیول پارٹیشن میں کچھ کنارے ہو سکتے ہیں جو اوپر کے درخت میں کسی نوڈ سے مطابقت نہیں رکھتے ہیں، یہ وہ کنارے ہیں جو اس کے نیچے کی سطح میں صرف ایک بچے کی نمائندگی کرتے ہیں، یعنی۔ ایک سادہ کلسٹر۔ صرف وہ کنارے جو جامع کلسٹرز سے مطابقت رکھتے ہیں وہ اوپر والے درخت کے نوڈس سے مطابقت رکھتے ہیں جب ہم درخت کو کلسٹرز میں تقسیم کرتے ہیں تو تقسیم کرنے کی حکمت عملی اہم ہوتی ہے۔ صرف ایک محتاط حکمت عملی اس بات کو یقینی بناتی ہے کہ ہم اونچائی ملٹی لیول پارٹیشن (اور اس وجہ سے اوپر کا درخت) میں ختم ہو جائیں۔ بعد کی سطحوں میں کناروں کی تعداد میں مستقل عنصر کی کمی ہونی چاہیے۔ اگر کسی نچلی سطح کو اپ ڈیٹ کے ذریعے تبدیل کیا جاتا ہے تو ہمیں زیادہ سے زیادہ مستقل تعداد میں اندراجات اور حذفیوں کا استعمال کرتے ہوئے اس کے فورا اوپر والے کو اپ ڈیٹ کرنے کے قابل ہونا چاہیے۔ تقسیم کرنے کی مذکورہ حکمت عملی وقت پر اوپر والے درخت کی دیکھ بھال کو یقینی بناتی ہے۔ لنک/کٹ ٹری یولر ٹور ٹری ڈائنامک الگورتھم ڈائنامک کنیکٹوٹی حوالہ جات اسٹیفن السٹرپ، جیکب ہولم، کرسٹیئن ڈی لکٹن برگ، اور میکل تھورپ، ٹاپ ٹری کے ساتھ مکمل طور پر متحرک درختوں میں معلومات کو برقرار رکھنا، الگورتھم پر ACM ٹرانزیکشنز (TALG)، جلد۔ 1 (2005)، 243-264، اسٹیفن آلسٹروپ، جیکب ہولم، کرسٹین ڈی لکٹنبرگ، اور میکل تھورپ، کنیکٹوٹی کے لیے پولی-لوگرتھمک ڈیٹرمینیسٹک ڈائنامک الگورتھم، کم از کم اسپانڈنگ ٹری، 2-ایج، اور بائی کنیکٹوٹی، جرنل آف دی ACM، جلد۔ 48 شمارہ 4 (جولائی 2001)، 723-760، ڈونلڈ نوتھ۔ کمپیوٹر پروگرامنگ کا فن: بنیادی الگورتھم، تیسرا ایڈیشن۔ ایڈیسن-ویسلی، 1997۔ سیکشن 2: درخت، پی پی۔ 308-423۔ تھامس ایچ کورمین، چارلس ای لیسرسن، رونالڈ ایل ریویسٹ، اور کلفورڈ اسٹین۔ الگورتھم کا تعارف، دوسرا ایڈیشن۔ ایم آئی ٹی پریس اور میک گرا ہل، 2001۔ سیکشن 10.4: جڑوں والے درختوں کی نمائندگی، پی پی۔ 214-217 ابواب 12-14 (بائنری سرچ ٹریز، ریڈ بلیک ٹریز، اگمینٹنگ ڈیٹا اسٹرکچرز)، پی پی۔ 253-320۔ بیرونی روابط اوپر والے درختوں کے ساتھ مکمل طور پر متحرک درختوں میں معلومات کو برقرار رکھنا۔ آلسٹرپ اور دیگر سیلف ایڈجسٹنگ ٹاپ ٹریز۔ ٹارجن اینڈ ورنک، پروک۔ 16 واں سوڈا، 2005 بائنری درخت