اے وی ایل ٹری ڈیٹا اسٹرکچر

پچھلے ٹٹوریل میں ہم نے دیکھا تھا کہ Binary Search Tree کو بنانے کے لیے اگر ترتیب شدہ ڈیٹا استعمال کیا جائے تو اس کی کارکردگی Linked List کے برابر ہو جاتی ہے۔ اس لیے یہ ضروری ہے کہ جس ڈیٹا کی مدد سے بائنری سرچ ٹری بنایا جا رہا ہے وہ Unsorted ہو کیونکہ اس سے ٹری کے دونوں جانب نوڈز اسٹورہوں گی جس کے نتیجے میں ٹری میں سے مطلوبہ ویلیو بہت تیز رفتاری کے ساتھ تلاش کی جا سکے گی۔ لیکن یہ ضروری نہیں ہے کہ کمپیوٹر پروگرام کو ہمیشہ غیر ترتیب شدہ ڈیٹا ہی ملے اس لیے اس صورتحال سے بچنے کی کوئی صورت ہونی چاہیے۔ چنانچہ اس مسئلہ کے حل کے طور پر AVL Tree متعارف کروایا گیا جو کہ دراصل ایک ایسا Binary Search Treeہے جس میں ٹری کو بیلنس کرنے کی اضافی خصوصیت شامل کی گئی ہے۔

AVL Tree

بائنری سرچ ٹری میں سے کوئی نوڈ تلاش کرنے پر ٹری کے ڈھانچے کو کوئی فرق نہیں پڑتا، البتہ نئی نوڈ شامل کرنے یا پہلے سے موجود کوئی نوڈ ختم کرنے سے ٹری کے ڈھانچے میں تبدیلی آتی ہے۔ یعنی یہ عین ممکن ہے کہ ابتدا میں تو بائنری سرچ ٹری میں سے مطلوبہ ویلیو بہت تیز رفتاری سے حاصل کی جا رہی ہو، لیکن بہت زیادہ نئی نوڈز کے اضافے اور خاتمے کے ساتھ ٹری کا ڈھانچہ ایسا بن جائے کہ اب مطلوبہ نوڈ تلاش کرنے کی رفتار بہت کم ہو جائے۔ چنانچہ اے وی ایل ٹری اس طرح سے کام کرتا ہے کہ نئی نوڈ کے اضافے یا پرانی نوڈ کے خاتمے پر چیک کیا جائے کہ ٹری کے لیولز کے درمیان 1 سے زیادہ کا فرق نہ رہے۔ اس فرق کو Balance Factor کہا جاتا ہے۔ یعنی نئی نوڈ شامل کرنے یا کوئی نوڈ ختم کرنے کے بعد جیسے ہی ٹری کے لیولز کے درمیان فرق 2 ہو جائے، تو پھر متاثرہ لیول کی نوڈز کو Rotate کیا جائے گا، اور اگر اس روٹیشن کے نتیجے میں اس سے اوپر والے لیول کا بیلنس خراب ہو جائے تو اسے بھی روٹیشن کے ذریعے بیلنس کیا جائے گا، چنانچہ یہ عمل ٹری کے Root تک جا سکتا ہے۔ روٹیشن کا عمل درج ذیل اینیمیشن میں دیکھا جا سکتا ہے۔

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

اے وی ایل ٹری کے تحت کسی متاثرہ لیول کو بیلنس کرنے کے لیے چار طرح کی روٹیشنز کی جاتی ہیں:

Left Rotation

اگر کسی نوڈ کے دائیں طرف والے چائلڈ کے نیچے دائیں طرف نئی نوڈ شامل کرنے سے بیلنس خراب ہو رہا ہو تو پھر اس لیول کو بیلنس کرنے کے لیے نوڈز کو بائیں طرف گھمایا جاتا ہے۔

Right Rotation

اگر کسی نوڈ کے بائیں طرف والے چائلڈ کے نیچے بائیں طرف نئی نوڈ شامل کرنے سے بیلنس خراب ہو رہا ہو تو پھر اس لیول کو بیلنس کرنے کے لیے نوڈز کو دائیں طرف گھمایا جاتا ہے۔

Left-Right Rotation

اگر کسی نوڈ کے بائیں طرف والے چائلڈ کے نیچے دائیں طرف نئی نوڈ شامل کرنے سے بیلنس خراب ہو رہا ہو تو پھر اس لیول کو بیلنس کرنے کے لیے (1) پہلے نوڈز کو بائیں طرف گھمایا جاتا ہے (2) پھر نوڈز کو دائیں طرف گھمایا جاتا ہے۔

Right-Left Rotation

اگر کسی نوڈ کے دائیں طرف والے چائلڈ کے نیچے بائیں طرف نئی نوڈ شامل کرنے سے بیلنس خراب ہو رہا ہو تو پھر اس لیول کو بیلنس کرنے کے لیے (1) پہلے نوڈز کو دائیں طرف گھمایا جاتا ہے (2) پھر نوڈز کو بائیں طرف گھمایا جاتا ہے۔

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