بائنری سرچ ٹری ڈیٹا اسٹرکچر

پچھلی چند تحریروں میں ہم نے Skip List, Linked List, Array List ڈیٹا اسٹرکچرز کا کچھ تعارف پیش کیا تھا۔ ان تینوں کو Linear کہا جاتا ہے، اس وجہ سے کہ کمپیوٹر میموری کے اندر یہ ڈیٹا اسٹرکچرز ایسے تسلسل کے ساتھ موجود ہوتے ہیں کہ لسٹ کا ہر آبجیکٹ اپنے سے اگلے اور پچھلے آبجیکٹ کے ساتھ منسلک ہوتا ہے۔ اس ٹٹوریل میں Binary Search Tree کے بارے میں بات کریں گے جو کہ Non-Linear ڈیٹا اسٹرکچر ہے، اور یہ دیکھیں گے کہ یہ کیسے کام کرتا ہے اور دیگر ڈیٹا اسٹرکچرز کے مقابلے اس کی نمایاں خصوصیت کیا ہے۔

سب سے پہلے ہم یہ دیکھتے ہیں کہ بائنری ٹری سے کیا مراد ہے، اس کے بعد ہم بائنری سرچ ٹری کے بارے میں بات کریں گے۔

Binary Tree

جیسا کہ آپ جانتے ہوں گے کہ Binary کا مطلب ایسی شے ہے جو دو چیزوں پر مشتمل ہو، یا دو چیزوں کا استعمال کرے۔ مثال کے طور پر بائنری نمبر سسٹم جو کمپیوٹر سسٹم کی بنیاد ہے یہ 0 اور 1 کے دو اعداد پر مشتمل ہوتا ہے۔ اسی طرح بائنری آپریٹرز + - / * > < وغیرہ ہیں جو اپنے دائیں اور بائیں موجود دو چیزوں پر حساب کتاب یا موازنے کا عمل سرانجام دیتے ہیں۔ البتہ Tree سے یہاں مراد عام درخت نہیں بلکہ شجرۂ نسب (Family Tree) ہے۔ چنانچہ Binary Tree سے مراد ایسا ڈیٹا اسٹرکچر ہے کہ اسے جب کمپیوٹر میموری میں اسٹور کیا جائے تو اس کا ڈھانچہ شجرۂ نسب کی طرح ہو اور اس کی خصوصیات درج ذیل ہوں:

• وہ Node (آبجیکٹ) جس سے بائنری ٹری کا آغاز ہوتا ہے اسے Root کہتے ہیں۔
• بائنری ٹری کی کسی بھی نوڈ کے آگے زیادہ سے زیادہ دو نوڈز منسلک ہو سکتی ہیں۔
• ہر نوڈ اپنے سے نیچے والی نوڈ کی Parent کہلاتی ہے۔ جبکہ نیچے والی نوڈ Child کہلاتی ہے۔
• بائنری ٹری کی سب سے آخر والی نوڈ جس کا کوئی چائلڈ نہیں ہوتا اسے Leaf کہتے ہیں۔
• بائنری ٹری کی سب سے پہلی نوڈ اس ٹری کا Root کہلاتی ہے- جبکہ کوئی بھی نوڈ اپنے نیچے براہ راست منسلک نوڈز کا Root ہوتی ہے۔

درج ذیل تصویر میں بائنری ٹری کا ایک خاکہ پیش کیا گیا ہے۔

آئیں اب بائنری ٹری کی کچھ اصطلاحات پر نظر ڈال لیتے ہیں:

• بائنری ٹری کی Height سے مراد یہ ہے کہ اس ٹری کے کتنے لیولز ہیں۔
• بائنری ٹری کے Size کا مطلب یہ ہے کہ اس میں موجود نوڈز کی تعداد کیا ہے۔
• ایسی نوڈ جس کا کوئی چائلڈ ہو اسے Internal Node کہتے ہیں اور وہ نوڈ جس کا کوئی چائلڈ نہ ہو اسے External Node کہتے ہیں۔
• اگر یہ پوچھا جائے کہ کسی نوڈ کا Level کیا ہے تو اس کا مطلب یہ ہے کہ Root نوڈ سے لے کر اس نوڈ تک کتنے لیولز ہیں۔
• ایسا بائنری ٹری جس میں Leaf نوڈز کے علاوہ ہر نوڈ کے دو چلڈرن ہوں تو اسے Full Binary Tree کہتے ہیں۔
• ایسا بائنری ٹری جس کی ہر نوڈ کے دو چلڈرن ہوں، اور اس ٹری کی تمام Leaf نوڈز ایک ہی لیول پر ہوں تو اسے Perfect Binary Tree کہتے ہیں۔
• ایسا بائنری ٹری جس کے آخری لیول کے علاوہ تمام لیولز پر ہر نوڈ کے دو چلڈرن ہوں، اور آخری لیولز پر موجود تمام نوڈز بائیں جانب ہوں تو اسے Complete Binary Tree کہتے ہیں۔

Binary Search Tree

بائنری سرچ ٹری سے مراد وہ بائنری ٹری ہے جسے بناتے وقت ایک خاص ترتیب کا لحاظ رکھا جائے۔ وہ اس طرح کہ کسی بھی نوڈ کی جو Key ہوگی، اس نوڈ کے نیچے دائیں طرف والی نوڈ میں اس سے بڑی Key ہوگی اور بائیں طرف والی نوڈ میں اس سے چھوٹی Key ہوگی۔ بائنری سرچ ٹری میں سے کوئی مخصوص نوڈ بہت تیز رفتاری سے حاصل کی جا سکتی ہے۔ اس کی وجہ یہ ہے کہ اررے یا لنکڈ لسٹ کی طرح بائنری سرچ ٹری میں نوڈز ایک دوسرے کے ساتھ سلسلہ وار منسلک نہیں ہوتیں، اس لیے مطلوبہ نوڈ تک پہنچنے کے لیے اس سے پیچھے موجود تمام نوڈز کے ساتھ اس کا موازنہ کرنے کی ضرورت نہیں ہے۔ جیسا کہ ہم جانتے ہیں کہ بائنری سرچ ٹری میں کسی بھی نوڈ کے دائیں طرف والے چائلڈ نوڈ کی Key بڑی ہوتی ہے اور بائیں طرف والے چائلڈ کی Key چھوٹی ہوتی ہے۔ چنانچہ جب کوئی نوڈ تلاش کی جاتی ہے تو سب سے پہلے یہ دیکھا جاتا ہے کہ اس نوڈ کی Key بائنری سرچ ٹری کے Root نوڈ کی Key سے چھوٹی ہے یا بڑی؟ اگر بڑی ہے تو پھر ٹری کا بایاں حصہ نظر انداز ہو جائے گا۔ یعنی اگر ٹری میں ایک لاکھ نوڈز ہیں تو پہلی کوشش میں ٹری کی پچاس ہزار ویلیوز نظر انداز ہو جائیں گی کیونکہ ہمیں معلوم ہے کہ مطلوبہ نوڈ سے بائیں طرف والی تمام نوڈز چھوٹی ہیں۔ اس کے بعد ہر لیول پر اسی طرح موازنہ کرنے سے اس لیول کا بقیہ حصہ نظر انداز ہوتا چلا جاتا ہے اور یوں بہت جلد مطلوبہ ویلیو حاصل ہو جاتی ہے۔

درج ذیل اینیمیشن میں دیکھا جا سکتا ہے کہ اررے سے 27 والی نوڈ حاصل کرنے کے لیے اس سے پیچھے موجود تمام ویلیوز کے ساتھ اس کا موازنہ کیا جا رہا ہے، جبکہ بائنری سرچ ٹری میں سے مطلوبہ ویلیو حاصل کرنے کے لیے ہر لیول پر دائیں اور بائیں چائلڈ کے ساتھ اس کا موازنہ کیا جا رہا ہے۔

البتہ بائنری سرچ ٹر ی کے ساتھ ایک مسئلہ یہ ہے کہ اگر ترتیب شدہ یعنی Sorted صورت میں موجود ڈیٹا کی مدد سے یہ ٹری بنایا جائے تو وہ لنکڈ لسٹ کی شکل اختیار کر جاتا ہے، اس لیے کہ ڈیٹا کی ویلیوز ٹری کے ایک طرف ہی شامل ہوتی چلی جاتی ہیں اور دوسری سائیڈ خالی رہ جاتی ہے۔ ایسے بائنری سرچ ٹری سے مطلوبہ ویلیو تلاش کرنے کی رفتار سست ہو جاتی ہے کیونکہ پھر تمام ویلیوز کے ساتھ مطلوبہ ویلیو کا موازنہ کرنا پڑ جاتا ہے۔ اسے سمجھنے کے لیے درج ذیل اینیمیشن دیکھیں:

چنانچہ جتنے زیادہ بے ترتیب یعنی Unsorted ڈیٹا کی مدد سے بائنری سرچ ٹری بنایا جائے اتنا ہی وہ تلاش کے لیے بہتر تصور کیا جاتا ہے۔

درج بالا طریقہ تو بائنری سرچ ٹری سے کوئی مخصوص نوڈ حاصل کرنے کا تھا۔ لیکن جب بائنری سرچ ٹری پر Traversal کرنا مقصود ہو یعنی اس کی تمام نوڈز حاصل کرنے کی ضرورت ہو تو اس کے لیے درج ذیل طریقے اختیار کیے جاتے ہیں۔ ٹری کے Root سے آغاز کرنے کے بعد:

بائنری سرچ ٹری میں سے نوڈز حاصل کرنے کے ان تمام طریقوں کے اپنے اپنے فوائد ہیں لیکن In-order Traversal کو ان تمام طریقوں پر فوقیت حاصل ہے۔ وہ اس طرح کہ اس کے ذریعے سے ٹری کی تمام نوڈز ہمیشہ ایک ترتیب سے یعنی Sorted صورت میں حاصل ہوتی ہیں۔ اس کا مطلب یہ ہے کہ کسی بھی ڈیٹا کو جب ہم بائنری سرچ ٹری کی شکل میں لاتے ہیں تو In-order Traversal کر کے اس تمام ڈیٹا کو Sorted صورت میں حاصل کیا جا سکتا ہے۔