Level ancestor problem
گراف تھیوری اور نظریاتی کمپیوٹر سائنس میں، سطح کے آباؤ اجداد کا مسئلہ ایک دیئے گئے جڑ والے درخت T کو ڈیٹا ڈھانچے میں پہلے سے پروسیس کرنے کا مسئلہ ہے جو درخت کی جڑ سے دیئے گئے فاصلے پر کسی دیئے گئے نوڈ کے آباؤ اجداد کا تعین کر سکتا ہے۔ مزید واضح طور پر، T کو n نوڈس کے ساتھ جڑا ہوا درخت ہونے دیں، اور v کو T کا صوابدیدی نوڈ ہونے دیں۔ سطح کا آباؤ اجداد کا استفسار ایل اے (v، d) نوڈ v کے آباؤ اجداد سے گہرائی d پر درخواست کرتا ہے، جہاں کسی درخت میں نوڈ v کی گہرائی درخت کی جڑ سے نوڈ v تک کے مختصر ترین راستے پر کناروں کی تعداد ہوتی ہے۔ اس مسئلے کو مستقل وقت فی استفسار میں حل کرنا ممکن ہے، ایک پری پروسیسنگ الگورتھم کے بعد جو O (n) لیتا ہے اور جو ڈیٹا ڈھانچہ بناتا ہے جو O (n) اسٹوریج کی جگہ استعمال کرتا ہے۔ بے وقوف طریقے نوڈ کے سطح کے آباؤ اجداد کو تلاش کرنے کا سب سے آسان طریقہ درخت کی جڑ کی طرف درخت پر چڑھنا ہے۔ درخت کی جڑ کے راستے پر، نوڈ کے ہر آباؤ اجداد کا دورہ کیا جا سکتا ہے اور اس لیے اطلاع دی جا سکتی ہے۔ اس صورت میں، درخت کو پہلے سے پروسیس کرنے کی ضرورت نہیں ہے اور کسی سوال کا جواب دینے کا وقت او (ایچ) ہے، جہاں "ایچ" درخت کی اونچائی ہے۔ یہ نقطہ نظر ایسے حالات میں ممکن نہیں ہے جہاں درخت کی اونچائی زیادہ ہو اور بڑی تعداد میں سوالات پر کارروائی کرنے کی ضرورت ہو۔ متبادل طور پر، تمام ممکنہ حلوں کو پہلے سے شمار کیا جا سکتا ہے اور میز میں محفوظ کیا جا سکتا ہے۔ اس صورت میں، سوالات کا جواب O (1) میں دیا جا سکتا ہے لیکن جگہ اور پری پروسیسنگ کا وقت O (n2) ہے۔ سب سے آسان سوالات جن کا جواب بغیر کسی پری پروسیسنگ کے مستقل وقت میں دیا جا سکتا ہے وہ ہیں ایل اے (وی، 0) اور ایل اے (وی، ڈیپتھ (وی))۔ سابقہ صورت میں، جواب ہمیشہ درخت کی جڑ ہوتا ہے اور مؤخر الذکر صورت میں، جواب خود نوڈ v ہوتا ہے۔ ان میں سے ہر ایک نتیجہ O (1) لیتا ہے۔ سکیو بائنری بے ترتیب رسائی کی فہرست میں درخت کے ذریعے راستوں کو ذخیرہ کرنے سے درخت کو ایک وقت میں ایک O (1) قدم نیچے کی طرف بڑھایا جا سکتا ہے، لیکن اب تلاش کو O (لاگ (p)) میں آگے بڑھنے کی اجازت دیتا ہے، جہاں "p" v سے مطلوبہ گہرائی تک کا فاصلہ ہے۔ یہ نقطہ نظر اس وقت ممکن ہے جب درخت خاص طور پر چوڑا ہو یا اسے آن لائن بڑھایا جائے اور اس لیے اسے مؤثر طریقے سے پہلے سے پروسیس نہیں کیا جا سکتا، کیونکہ اسٹوریج اور رسائی کا وقت خالصتا راستے کی لمبائی سے طے ہوتا ہے۔ جمپ پوائنٹر الگورتھم جمپ پوائنٹر الگورتھم O (n لاگ n) وقت میں ایک درخت پر پہلے سے کارروائی کرتا ہے اور O (لاگ n) وقت میں سطح کے آباؤ اجداد کے سوالات کا جواب دیتا ہے۔ جمپ پوائنٹر الگورتھم درخت کے ہر سرے پر این پوائنٹروں کو لاگ کرنے کے لیے منسلک کرتا ہے۔ ان اشاروں کو جمپ پوائنٹر کہا جاتا ہے کیونکہ وہ درخت کی جڑ کی طرف درخت پر چھلانگ لگاتے ہیں۔ کسی درخت کے دیئے گئے نوڈ v کے لیے، الگورتھم لمبائی میں چھلانگ لگانے والوں کی ایک صف کو ذخیرہ کرتا ہے۔ اس صف کا ith عنصر v کے 2th آباؤ اجداد کی طرف اشارہ کرتا ہے۔ اس طرح کے ڈیٹا ڈھانچے کا استعمال ہمیں کسی بھی نوڈ سے درخت کے آدھے راستے پر چھلانگ لگانے میں مدد کرتا ہے۔ جب الگورتھم کو کسی استفسار پر کارروائی کرنے کے لیے کہا جاتا ہے، تو ہم ان نکات کا استعمال کرتے ہوئے بار بار درخت پر چھلانگ لگاتے ہیں۔ چھلانگوں کی تعداد زیادہ سے زیادہ لاگ این ہوگی اور اس لیے سوالات کا جواب لاگ این ٹائم میں دیا جا سکتا ہے۔ سیڑھی الگورتھم سیڑھی الگورتھم کسی درخت کو راستوں کے مجموعے میں آسان بنانے کے خیال پر مبنی ہے۔ اس کی وجہ یہ حقیقت ہے کہ جب آباؤ اجداد کے سوالات کی سطح کی بات آتی ہے تو راستوں سے پوچھ گچھ کرنا آسان ہوتا ہے۔ ایک پاتھ P پر غور کریں جو n نوڈس پر مشتمل ہے جس کی جڑیں نوڈ r پر ہیں۔ ہم پاتھ کو سائز n کی صف میں محفوظ کر سکتے ہیں جسے سیڑھی کہا جاتا ہے اور ہم ایل اے (v، d) کے سطح کے آباؤ اجداد کے سوال کا جواب سیڑھی [d] واپس کر کے دے سکتے ہیں اگر گہرائی (v) ≤ d ہو۔ یہ O (1) لے گا۔ تاہم، یہ تب ہی کام کرے گا جب دیا ہوا درخت ایک راستہ ہو۔ ورنہ، ہمیں اسے راستوں میں تحلیل کرنے کی ضرورت ہے۔ یہ دو مراحل میں کیا جاتا ہے: لمبا راستہ سڑنا اور لمبا راستہ سیڑھی میں بڑھانا۔ مرحلہ 1: لمبا راستہ سڑنا یہ ایک تکراری طریقہ ہے جو کسی دیئے گئے درخت کو راستوں میں سڑ دیتا ہے۔ یہ مراحل درخت میں جڑ سے پتی تک کا سب سے طویل راستہ تلاش کرنے سے شروع ہوتے ہیں۔ اس کے بعد یہ درخت سے اپنے بندھن توڑ کر اس راستے کو ہٹا دیتا ہے جو درخت کے بقیہ حصے کو ذیلی درختوں میں توڑ دے گا اور پھر یہ ہر ذیلی درخت پر بار بار عمل کرتا ہے۔ ہر بار جب کوئی راستہ سڑ جاتا ہے، تو اس راستے کے ساتھ مل کر ایک صف بنائی جاتی ہے جس میں جڑ سے پتی تک کے راستے کے عناصر ہوتے ہیں۔ اس تکرار کا بنیادی معاملہ تب ہوتا ہے جب درخت ایک راستہ ہوتا ہے جس صورت میں اسے ہٹانے سے ایک خالی گراف نکل جاتا ہے۔ ہر ورٹیکس v میں ایک منفرد سیڑھی ہوتی ہے جو اس پر مشتمل سیڑھی ہوتی ہے اور ہم اسے "v کی سیڑھی" کہتے ہیں۔ تاہم، اس پری پروسیسنگ مرحلے کے بعد، سوالات کا جواب فوری طور پر نہیں دیا جا سکتا۔ در حقیقت ایک سطح کے آباؤ اجداد کے سوال کا جواب دینے کے لیے، الگورتھم کو ایک راستے سے دوسرے راستے پر کودنے کی ضرورت ہوتی ہے جب تک کہ وہ جڑ تک نہ پہنچ جائے اور پتی سے جڑ کے راستے پر اس طرح کے راستوں کے ≤ () ہو سکتے ہیں۔ یہ ہمیں ایک الگورتھم کی طرف لے جاتا ہے جو درخت کو O (n) وقت میں پہلے سے پروسیس کر سکتا ہے اور O () میں سوالات کا جواب دے سکتا ہے۔ استفسار کے زیادہ سے زیادہ وقت تک پہنچنے کے لیے، ہمیں ذیل میں بیان کردہ دوسرے مرحلے میں نتائج پر کارروائی کرنے کی ضرورت ہے۔ مرحلہ 2: سیڑھیوں میں لمبے راستوں کو بڑھانا الگورتھم کا پہلا مرحلہ درخت کو متعدد جداگانہ راستوں میں تحلیل کر دیتا ہے۔ الگورتھم کے دوسرے مرحلے میں، ہر راستے کو بڑھایا جاتا ہے اور اس وجہ سے نتیجے میں آنے والے راستے باہمی طور پر خصوصی نہیں ہوں گے۔ الگورتھم کے پہلے مرحلے میں، ہر راستہ سائز h 'کی صف سے وابستہ ہے۔ ہم اسی صف میں راستے کے اوپری حصے میں ایچ 'فوری آباؤ اجداد کو شامل کرکے اس راستے کو بڑھاتے ہیں۔ یہ ہر صف کو اس کے اصل سائز سے زیادہ سے زیادہ دوگنا بڑھا دے گا جس کے نتیجے میں تمام سیڑھیوں میں نوڈس کی کل تعداد 2n ہوگی۔ نوٹ کریں کہ سیڑھیوں کی تعداد تبدیل نہیں کی گئی ہے اور ہر نوڈ کی سیڑھی یکساں رہتی ہے۔ اگرچہ نوڈ v کو اب متعدد راستوں میں درج کیا جا سکتا ہے لیکن اس کی سیڑھی وہی ہے جو الگورتھم کے پہلے مرحلے میں v سے وابستہ تھی۔ یہ دونوں مراحل O (n) میں عمل ہو سکتے ہیں لیکن استفسار کا وقت ابھی مستقل نہیں ہے۔ اونچائی ایچ کے نوڈ یو پر ایک سطح کے آباؤ اجداد کے استفسار پر غور کریں۔ یو کی سیڑھی کے اوپری حصے تک سفر کرنے سے، اونچائی کے ایک سرے پر کم از کم 2h تک پہنچ جائے گا۔ مشاہدہ کریں کہ تمام نوڈس کی اونچائی کم از کم 1 ہے اور اس لیے یہ i بار کرنے کے بعد، ہم کم از کم 2i اونچائی کے نوڈ تک پہنچ جاتے ہیں اور اس لیے ہمیں زیادہ سے زیادہ لاگ n اوقات میں ایسا کرنے کی ضرورت ہے۔ یہ ہمیں او (لاگ این) کا استفسار کا وقت دیتا ہے۔ مرحلہ 3: دونوں طریقوں کو یکجا کرنا یہ پتہ چلتا ہے کہ سیڑھی الگورتھم خود ہی چال نہیں چلاتا ہے۔ درحقیقت جمپ پوائنٹر الگورتھم اور لیڈر الگورتھم ایک دوسرے کی تکمیل کرتے ہیں۔ دونوں الگورتھم مخالف سمتوں میں کام کرتے ہیں: جمپ پوائنٹر الگورتھم تیزی سے ہوپس کو کم کرتا ہے اور سیڑھی الگورتھم تیزی سے ہوپس کو بڑھاتا ہے۔ دونوں الگورتھم کا مجموعہ O (1) وقت میں سوالات کا جواب دے سکتا ہے۔ ایک سنگل جمپ پوائنٹر کسی بھی سوال کو کم از کم درخت کے آدھے راستے پر لے جاتا ہے جس کے بعد صرف ایک سیڑھی چڑھنے سے سوال کا جواب ملے گا۔ اس کے نتیجے میں او (این لاگ این) پری پروسیسنگ ٹائم اور او (1) استفسار ٹائم ہوتا ہے۔ پری پروسیسنگ کو مزید کم کر کے O (n) وقت کیا جا سکتا ہے چار روسی طریقہ کار کے استعمال سے، جس میں درخت کو لکیری پری پروسیسنگ کے ساتھ ایک چھوٹے درخت میں تبدیل کر دیا جاتا ہے، اور بہت چھوٹے درختوں کا مجموعہ، جو اتنے چھوٹے ہوتے ہیں کہ تمام درختوں کی مکمل گنتی اور ان درختوں کی پری پروسیسنگ اب بھی O (n) وقت ہوتا ہے۔ سائز کے درخت (لاگ این)/4 کافی ہیں۔ برکمین اور وشکن کا حل ایک مختلف حل برکمین اور وشکن کی وجہ سے ہے۔ یہ حل درختوں کی پروسیسنگ کے لیے اویلر ٹور تکنیک پر مبنی ہے۔ اہم مشاہدہ یہ ہے کہ ایل اے (وی، ڈی) گہرائی ڈی کا پہلا نوڈ ہے جو وی کے آخری ظہور کے بعد اویلر ٹور میں ظاہر ہوتا ہے۔ اس طرح، اویلر ٹور اور گہرائی سے متعلق متعلقہ معلومات کی تعمیر سے، مسئلہ کم ہو کر صفوں پر استفسار تک پہنچ جاتا ہے، جسے فائنڈ سمالر (ایف ایس) کہا جاتا ہے۔ ایک صف A کے لیے، اور ایک درست اشاریہ i، FS (i، x) پہلا اشاریہ j> i اس طرح واپس کرتا ہے کہ A [i] <x (یہاں، ہم x = d + 1 استعمال کرتے ہیں)۔ ایف ایس مسئلے کا ایک موثر حل عام طور پر مشکل ہے، لیکن یولر دوروں سے پیدا ہونے والے خصوصی معاملے کے لیے آسان ہے۔ اس معاملے میں، ملحقہ عناصر ±1 سے مختلف ہوتے ہیں۔ یہ خیال پیچیدگی O (n لاگ n) کے پری پروسیسنگ الگورتھم کے ساتھ O (1) استفسار کا وقت فراہم کرتا ہے۔ چار روسیوں کے طریقہ کار کی درخواست کے ذریعے پری پروسیسنگ کا وقت O (n) تک بہتر کیا جاتا ہے۔ یہ بھی دیکھیں رینج استفسار (کمپیوٹر سائنس) سب سے کم عام آباؤ اجداد حوالہ جات نظریاتی کمپیوٹر سائنس درخت (گراف تھیوری)