ریڈ بلیک ٹری ڈیٹا اسٹرکچر

اس سے پہلے ایک تحریر میں ہم نے Binary Search Tree کی یہ خاصیت ذکر کی تھی کہ اس میں کسی بھی نوڈ کے دائیں طرف والی چائلڈ نوڈ کی ویلیو اس سے بڑی ہوتی ہے اور بائیں طرف والی چائلڈ نوڈ کی ویلیو اس سے چھوٹی ہوتی ہے، اس خاصیت کی وجہ سے بائنری سرچ ٹری میں سے مطلوبہ ویلیو بہت تیز رفتاری کے ساتھ تلاش کی جا سکتی ہے۔ لیکن اگر بائنری سرچ ٹری کو ترتیب شدہ ڈیٹا کی مدد سے بنایا جائے تو یہ عملی طور پر Linked List بن جاتا ہے جس کی وجہ سے اس میں سے مطلوبہ ویلیو کی تلاش کے لیے ٹری کی تمام نوڈز سے اس کا موازنہ لازمی ہو جاتا ہے۔ چنانچہ اس سے اگلی تحریر میں ہم نے AVL Tree کے متعلق بات کی تھی کہ وہ ایسا بائنری سرچ ٹری ہے جس میں ٹری کو بیلنس کرنے کی اضافی خصوصیت شامل ہے، یعنی نئی نوڈ شامل کرتے وقت یا پرانی نوڈ ختم کرتے وقت چیک کیا جاتا ہے کہ ٹری کے لیولز کے درمیان Height کا فرق 1 سے زیادہ تو نہیں، اگر ایسا ہو تو پھر اسے بیلنس کیا جاتا ہے اور یوں یہ لنکڈ لسٹ کی شکل اختیار نہیں کرتا۔ اس ٹٹوریل میں ہم بائنری سرچ ٹری کے ایک اور ورژن Red Black Tree کے بارے میں بات کریں گے جس میں ٹری کو بیلنس کرنے کا ایک مختلف طریقہ اختیار گیا ہے۔

Red Black Tree میں نوڈ کے طور پر بنائے جانے والے آبجیکٹ میں ایک اضافی ویری ایبل رکھا جاتا ہے جس سے اس نوڈ کے ریڈ یا بلیک ہونے کی نشاندہی ہوتی ہے۔ جب کسی نئی ویلیو کے اضافے یا پرانی ویلیو کے خاتمے پر ٹری کا بیلنس خراب ہو جاتا ہے تو نوڈز کے یہ سرخ اور سیاہ رنگ ٹری کے لیولز کو بیلنس کرنے کے لیے استعمال کیے جاتے ہیں۔ ریڈ بلیک ٹری کی خصوصیات درج ذیل ہیں:

1. ٹری کی کوئی بھی نوڈ بلیک ہو گی یا ریڈ۔
2. ٹری کی روٹ نوڈ ہمیشہ بلیک ہوگی۔
3. نئی نوڈ داخل کرتے وقت ریڈ ہوگی۔
4. ریڈ نوڈ کے چلڈرن ہمیشہ بلیک ہوں گے۔ یعنی یکے بعد دیگرے دو لیولز پر بیلک نوڈز تو آسکتی ہیں لیکن ریڈ نوڈز نہیں۔
5. Root نوڈ سے لے کر کسی بھی Leaf نوڈ تک جو بھی پاتھ اختیار کیا جائے، اس میں بلیک نوڈز کی تعداد ایک جیسی ہوگی، البتہ ریڈ نوڈز کی تعداد مختلف ہو سکتی ہے۔
6. Null نوڈز ہمیشہ بلیک ہوں گی۔

ٹری میں نئی نوڈ کے اضافے یا کسی نوڈ کے خاتمے پر اگر اوپر بیان کی گئی شرائط میں سے کسی شرط کی خلاف ورزی ہو رہی ہو تو اس کا مطلب ہے کہ ٹری کو بیلنس کرنے کی ضرورت ہے۔ جیسا کہ اوپر ذکر کیا گیا ہے کہ ٹری میں نئی نوڈ داخل کرتے وقت ریڈ ہوگی، اس کے بعد متاثرہ لیولز کا بیلنس اس طرح سے درست کیا جائے گا کہ:

• اگر نئی نوڈ کی آنٹی نوڈ بلیک ہے تو پھر لیولز کو Rotate کیا جائے گا۔ اس کے نتیجے میں پیرنٹ نوڈ کو بلیک ہوجانا چاہیے اور چائلڈ نوڈز کو ریڈ۔ یہاں یہ بات نوٹ کریں کہ روٹیشن کے اصول وہی ہوں گے جو AVL Tree میں ہوتے ہیں۔
• اگر نئی نوڈ کی آنٹی نوڈ ریڈ ہے تو پھر لیولز کے رنگ Flip کیے جائیں گے یعنی ریڈ کو بلیک اور بلیک کو ریڈ کر دیا جائے گا۔ اس کے نتیجے میں پیرنٹ نوڈ کو ریڈ ہوجانا چاہیے اور چائلڈ نوڈز کو بلیک۔

درج ذیل ریڈ بیلک ٹری کی ایک تصویر پیش کی جا رہی ہے جس سے اس کے ڈھانچے کا اندازہ ہو جائے گا: