AA tree
کمپیوٹر سائنس میں اے اے ٹری متوازن ٹری کی ایک شکل ہے جو آرڈر شدہ ڈیٹا کو مؤثر طریقے سے ذخیرہ کرنے اور بازیافت کرنے کے لیے استعمال ہوتی ہے۔ اے اے درختوں کا نام ان کے موجد، سویڈش کمپیوٹر سائنسدان آرن اینڈرسن کے نام پر رکھا گیا ہے۔ اے اے ٹری سرخ سیاہ درخت کی ایک قسم ہے، جو بائنری سرچ ٹری کی ایک شکل ہے جو اندراجات کے موثر اضافے اور حذف کرنے کی حمایت کرتی ہے۔ سرخ سیاہ درختوں کے برعکس، اے اے درخت پر سرخ نوڈس کو صرف دائیں ذیلی بچے کے طور پر شامل کیا جا سکتا ہے۔ دوسرے لفظوں میں، کوئی سرخ نوڈ لیفٹ سب چائلڈ نہیں ہو سکتا۔ اس کے نتیجے میں 2-3-4 درخت کے بجائے 2 سے 3 درخت کا نقالی ہوتا ہے، جو دیکھ بھال کے کاموں کو بہت آسان بناتا ہے۔ سرخ-سیاہ درخت کے لیے دیکھ بھال کے الگورتھم کو درخت کو مناسب طریقے سے متوازن کرنے کے لیے سات مختلف شکلوں پر غور کرنے کی ضرورت ہے: دوسری طرف ایک اے اے درخت کو صرف دو شکلوں پر غور کرنے کی ضرورت ہے کیونکہ سخت ضرورت ہے کہ صرف صحیح لنکس سرخ ہو سکتے ہیں: گردش کو متوازن کرنا جبکہ سرخ-سیاہ درختوں کو فی نوڈ (رنگ) میں میٹا ڈیٹا کو متوازن کرنے کے لیے ایک بٹ کی ضرورت ہوتی ہے، اے اے درختوں کو فی نوڈ میں میٹا ڈیٹا کے او (لاگ (لاگ (این))) بٹس کی ضرورت ہوتی ہے، ایک انٹیجر "لیول" کی شکل میں۔ اے اے درختوں کے لیے درج ذیل غیر متغیرات ہوتے ہیں: ہر پتی کے نوڈ کی سطح ایک ہوتی ہے۔ ہر بائیں بچے کی سطح اس کے والدین سے بالکل ایک کم ہوتی ہے۔ ہر صحیح بچے کی سطح اس کے والدین کے برابر یا اس سے ایک کم ہوتی ہے۔ ہر صحیح پوتے کی سطح اس کے دادا دادی سے سختی سے کم ہوتی ہے۔ ایک سے زیادہ سطح کے ہر نوڈ میں دو بچے ہوتے ہیں۔ ایک لنک جہاں بچے کی سطح اس کے والدین کے برابر ہوتی ہے اسے افقی لنک کہا جاتا ہے، اور یہ سرخ-سیاہ درخت میں سرخ لنک سے مشابہت رکھتا ہے۔ انفرادی دائیں افقی لنکس کی اجازت ہے، لیکن لگاتار ممنوع ہیں ؛ تمام بائیں افقی لنکس ممنوع ہیں۔ یہ سرخ کالے درختوں کے مقابلے میں زیادہ پابندیاں ہیں، جس کے نتیجے میں اے اے درخت کو دوبارہ متوازن کرنا طریقہ کار کے لحاظ سے سرخ کالے درخت کو دوبارہ متوازن کرنے سے کہیں زیادہ آسان ہے۔ اندراج اور حذف کرنے سے عارضی طور پر اے اے ٹری غیر متوازن ہو سکتا ہے (یعنی اے اے ٹری کے غیر متغیرات کی خلاف ورزی کرنا)۔ توازن بحال کرنے کے لیے صرف دو الگ الگ کارروائیوں کی ضرورت ہوتی ہے: "سکیو" اور "اسپلٹ"۔ سکیو ایک دائیں گردش ہے جس میں بائیں افقی لنک پر مشتمل ذیلی درخت کو دائیں افقی لنک کے ساتھ تبدیل کیا جاتا ہے۔ تقسیم ایک بائیں گردش اور سطح میں اضافہ ہے جو ایک ذیلی درخت کو تبدیل کرنے کے لیے ہوتا ہے جس میں دو یا زیادہ مسلسل دائیں افقی لنکس ہوتے ہیں جن میں سے ایک میں دو کم مسلسل دائیں افقی لنکس ہوتے ہیں۔ توازن برقرار رکھنے والے اندراج اور حذف کرنے کے نفاذ کو آسان بنایا جاتا ہے، اسکیو اور اسپلٹ آپریشنز پر انحصار کرتے ہوئے صرف ضرورت پڑنے پر ٹری میں ترمیم کی جاتی ہے، بجائے اس کے کہ کال کرنے والوں کو یہ فیصلہ کرنے پر مجبور کیا جائے کہ سکیو یا اسپلٹ کرنا ہے۔ فنکشن سکیو ان پٹ ہے: ٹی، ایک نوڈ جو اے اے ٹری کی نمائندگی کرتا ہے جسے دوبارہ متوازن کرنے کی ضرورت ہے۔ آؤٹ پٹ: ایک اور نوڈ جو دوبارہ متوازن اے اے ٹری کی نمائندگی کرتا ہے۔ اگر نیل (ٹی) ہے تو نیل واپس کریں ورنہ نیل (بائیں (ٹی) ہے تو ٹی واپس کریں ورنہ اگر سطح (بائیں (ٹی)) = = سطح (ٹی) ہے تو افقی بائیں لنکس کے پوائنٹرز کو تبدیل کریں۔ L = لیفٹ (T) لیفٹ (T): = رائٹ (L) رائٹ (L): = T ریٹرن L ورنہ ریٹرن T اینڈ اگر اینڈ فنکشن اسکیو: فنکشن اسپلٹ ان پٹ ہے: T، ایک نوڈ جو ایک AA ٹری کی نمائندگی کرتا ہے جسے ری بیلنس کرنے کی ضرورت ہے۔ آؤٹ پٹ: ایک اور نوڈ جو دوبارہ متوازن اے اے ٹری کی نمائندگی کرتا ہے۔ اگر نیل (ٹی) ہے تو نیل واپس کریں ورنہ نیل (دائیں (ٹی)) یا نیل (دائیں (ٹی)) ہے تو ٹی واپس کریں ورنہ اگر سطح (ٹی) = = سطح (دائیں (ٹی)) ہے تو ہمارے پاس دو افقی دائیں روابط ہیں۔ درمیانی نوڈ لیں، اسے اوپر اٹھائیں، اور اسے واپس کریں۔ R = دائیں (T) دائیں (T): = بائیں (R) بائیں (R): = T سطح (R): = سطح (R) + 1 واپسی R ورنہ واپسی T اختتام اگر اختتامی فنکشن تقسیم: اندراج اندراج عام بائنری ٹری کی تلاش اور اندراج کے طریقہ کار سے شروع ہوتا ہے۔ پھر، جیسے ہی کال اسٹیک کھلتا ہے (تلاش کے تکراری نفاذ کو فرض کرتے ہوئے)، ٹری کی صداقت کی جانچ کرنا اور ضرورت کے مطابق کوئی بھی گردش انجام دینا آسان ہے۔ اگر افقی بائیں لنک پیدا ہوتا ہے، تو ایک ترچھا انجام دیا جائے گا، اور اگر دو افقی دائیں لنک پیدا ہوتے ہیں، تو ایک تقسیم انجام دی جائے گی، ممکنہ طور پر موجودہ ذیلی درخت کے نئے جڑ نوڈ کی سطح میں اضافہ ہوگا۔ نوٹ کریں، جیسا کہ اوپر دیئے گئے کوڈ میں، سطح (T) کا اضافہ۔ اس سے درخت کی صداقت کی جانچ جاری رکھنا ضروری ہو جاتا ہے کیونکہ تبدیلیاں پتوں سے ابھر کر سامنے آتی ہیں۔ فنکشن انسرٹ ان پٹ ہے: X، جو قیمت داخل کی جانی ہے، اور T، جو اسے داخل کرنے کے لیے درخت کی جڑ ہے۔ آؤٹ پٹ: ایک متوازن ورژن T بشمول X۔ عام بائنری ٹری داخل کرنے کا طریقہ کار کریں۔ اگر کوئی نیا نوڈ بنایا گیا ہو یا سبٹری کی جڑ بدل گئی ہو تو ریکرسو کال کا نتیجہ درست چائلڈ پر سیٹ کریں۔ اگر نیل (ٹی) ہے تو ایکس کے ساتھ ایک نیا لیف نوڈ بنائیں۔ ریٹرن نوڈ (ایکس، 1، نیل، نیل) ورنہ اگر ایکس <ویلیو (ٹی) ہے تو لیفٹ (ٹی): = انسرٹ (ایکس، لیفٹ (ٹی)) ورنہ اگر ایکس> ویلیو (ٹی) ہے تو رائٹ (ٹی): = انسرٹ (ایکس، رائٹ (ٹی)) ختم ہوتا ہے اگر نوٹ کریں کہ ایکس = = ویلیو (ٹی) کا معاملہ غیر متعین ہے۔ جیسا کہ دیا گیا ہے، داخل کرنے سے کوئی اثر نہیں پڑے گا۔ عمل درآمد کرنے والا مختلف طرز عمل کی خواہش کر سکتا ہے۔ سکیو انجام دیں اور پھر تقسیم کریں۔ وہ شرائط جو اس بات کا تعین کرتی ہیں کہ گردش ہوگی یا نہیں وہ طریقہ کار کے اندر ہیں، جیسا کہ اوپر دیا گیا ہے۔ T: = سکیو (T) T: = اسپلٹ (T) ریٹرن T اینڈ فنکشن ڈیلیشن زیادہ تر متوازن بائنری ٹریز کی طرح، اندرونی نوڈ کے حذف ہونے کو اندرونی نوڈ کو اس کے قریب ترین پیشرو یا جانشین کے ساتھ تبدیل کرکے لیف نوڈ کے حذف ہونے میں تبدیل کیا جا سکتا ہے، اس پر منحصر ہے کہ کون سا درخت میں ہے یا عمل درآمد کرنے والے کی خواہش پر۔ پیشرو کو بازیافت کرنا محض ایک بائیں لنک اور پھر باقی تمام دائیں لنکس کی پیروی کرنے کی بات ہے۔ اسی طرح، جانشین کو ایک بار دائیں اور بائیں جانے سے اس وقت تک پایا جا سکتا ہے جب تک کہ کالعدم پوائنٹر نہ مل جائے۔ ایک سے زیادہ سطح کے تمام نوڈس کی اے اے پراپرٹی کی وجہ سے جن کے دو بچے ہیں، جانشین یا پیشرو نوڈ سطح 1 میں ہوگا، جس سے ان کا ہٹانا معمولی ہو جائے گا۔ کسی درخت کو دوبارہ متوازن کرنے کے لیے چند طریقے ہیں۔ اینڈرسن نے اپنے اصل مقالے میں جو بیان کیا ہے وہ سب سے آسان ہے، اور اسے یہاں بیان کیا گیا ہے، حالانکہ اصل نفاذ زیادہ بہتر نقطہ نظر کا انتخاب کر سکتے ہیں۔ ہٹانے کے بعد، درخت کی توثیق کو برقرار رکھنے کا پہلا قدم کسی بھی نوڈس کی سطح کو کم کرنا ہے جس کے بچے ان سے دو درجے نیچے ہیں، یا جو بچے لاپتہ ہیں۔ پھر، پوری سطح کو منحنی اور تقسیم کیا جانا چاہیے۔ یہ نقطہ نظر پسند کیا گیا تھا، کیونکہ جب تصوراتی طور پر مقرر کیا جاتا ہے، تو اس کے تین آسانی سے سمجھنے والے الگ الگ مراحل ہوتے ہیں: اگر مناسب ہو تو سطح کو کم کریں۔ سطح کو موڑ دیں۔ سطح کو تقسیم کریں۔ تاہم، ہمیں اس بار صرف ایک نوڈ کے بجائے پوری سطح کو موڑنا اور تقسیم کرنا ہوگا، جس سے ہمارا کوڈ پیچیدہ ہو جائے گا۔ فنکشن ڈیلیٹ ان پٹ ہے: X، حذف کرنے کی قیمت، اور T، درخت کی جڑ جس سے اسے حذف کیا جانا چاہیے۔ آؤٹ پٹ: T، متوازن، قیمت X کے بغیر۔ اگر صفر (T) ہے تو T کو واپس کریں ورنہ اگر X> قیمت (T) ہے تو دائیں (T): = حذف کریں (X، دائیں (T)) ورنہ اگر X <قیمت (T) ہے تو بائیں (T): = حذف کریں (X، بائیں (T)) ورنہ اگر ہم پتے ہیں، تو آسان ہے، بصورت دیگر پتے کے کیس میں گھٹ جائیں۔ اگر پتی (T) پھر دائیں (T) واپس کریں ورنہ اگر صفر (بائیں (T)) تو L: = جانشین (T) دائیں (T): = حذف کریں (قیمت (L)، دائیں (T)) قیمت (T): = قیمت (L) ورنہ L: = پیشرو (T) بائیں (T): = حذف کریں (قیمت (L)، بائیں (T)) قیمت (T): = قیمت (L) ختم ہو جاتی ہے اگر درخت کو دوبارہ متوازن کریں۔ اگر ضروری ہو تو اس سطح میں تمام نوڈس کی سطح کو کم کریں، اور پھر نئی سطح میں تمام نوڈس کو منحنی اور تقسیم کریں۔ ٹی: = کمی _ سطح (ٹی) ٹی: = سکیو (ٹی) صحیح (ٹی): = سکیو (دائیں (ٹی)) اگر نیل نہیں ہے (دائیں (ٹی)) صحیح (دائیں (ٹی): = سکیو (دائیں (ٹی)) ختم ہوتا ہے اگر ٹی: = تقسیم (ٹی) صحیح (ٹی): = تقسیم (دائیں (ٹی) واپسی ٹی اینڈ فنکشن فنکشن کمی _ سطح ان پٹ ہے: ٹی، ایک درخت جس کے لیے ہم ایسے لنکس کو ہٹانا چاہتے ہیں جو سطحوں کو چھوڑ دیتے ہیں۔ آؤٹ پٹ: ٹی اس کی سطح کے ساتھ کم ہوا۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ ہونا چاہیے۔ کارکردگی اے اے درخت کی کارکردگی سرخ سیاہ درخت کی کارکردگی کے برابر ہے۔ جبکہ ایک اے اے ٹری سرخ سیاہ درخت کے مقابلے میں زیادہ گردش کرتا ہے، آسان الگورتھم تیز ہوتے ہیں، اور یہ سب توازن برقرار رکھتے ہیں جس کے نتیجے میں اسی طرح کی کارکردگی ہوتی ہے۔ ایک سرخ سیاہ درخت اے اے درخت کے مقابلے میں اپنی کارکردگی میں زیادہ مستقل ہوتا ہے، لیکن ایک اے اے درخت چپٹا ہوتا ہے، جس کے نتیجے میں تلاش کا وقت قدرے تیز ہوتا ہے۔ سرخ-سیاہ درخت بی-درخت اے وی ایل درخت قربانی کا بکرا حوالہ جات بیرونی روابط اے اینڈرسن بھی دیکھیں۔ متوازن تلاش کے درختوں نے سادہ اے اینڈرسن بنا دیا۔ بائنری سرچ ٹری میں تلاش کرنے پر ایک نوٹ بی ایس ٹی ایل آئی بی-سی کے لیے ایک اوپن سورس اے اے ٹری لائبریری بذریعہ ٹرائزڈی اے ویژول 2007 1.5-اے اے ٹری ڈھانچوں کو تعلیم دینے کے لیے اوپن سورس ڈیلفی پروگرام بہت سارے کوڈ کے ساتھ مکمل ٹیوٹوریل جولین واکر جس میں ایک عملی نفاذ بھی شامل ہے آبجیکٹ پر مبنی نفاذ ٹیسٹ کے ساتھ ایک دریافت بائنری سرچ ٹری ڈیٹا ڈھانچوں کے کارکردگی کے رویے پر (صفحات 67-75)-اے اے درختوں، سرخ سیاہ درختوں، ٹریپس، سکپ لسٹس، اور ریڈکس درختوں کا موازنہ ایک آبجیکٹیو-سی نفاذ ازگر کی تلاش کے درخت