Tango tree
ٹینگو ٹری بائنری سرچ ٹری کی ایک قسم ہے جسے ایرک ڈی ڈیمین، ڈیون ہارمون، جان آئکونو، اور میھائی پیٹراسکو نے 2004 میں تجویز کیا تھا۔ اس کا نام بیونس آئرس کے نام پر رکھا گیا ہے، جس میں ٹینگو علامتی ہے۔ یہ ایک آن لائن بائنری سرچ ٹری ہے جو آف لائن آپٹیمل بائنری سرچ ٹری کے مقابلے میں مسابقتی تناسب حاصل کرتا ہے، جبکہ فی نوڈ صرف میموری کے اضافی بٹس کا استعمال کرتا ہے۔ اس سے پچھلے سب سے مشہور مسابقتی تناسب میں بہتری آئی، جو کہ تھا۔ ساخت ٹینگو کے درخت بائنری سرچ ٹری کو ترجیحی راستوں کے ایک سیٹ میں تقسیم کرکے کام کرتے ہیں، جو خود معاون درختوں میں محفوظ ہوتے ہیں (لہذا ٹینگو کے درخت کو درختوں کے درخت کے طور پر پیش کیا جاتا ہے)۔ ایک ٹینگو ٹری کی تعمیر کے لیے، ہم ایک مکمل بائنری سرچ ٹری کی تقلید کرتے ہیں جسے ریفرنس ٹری کہا جاتا ہے، جو محض ایک روایتی بائنری سرچ ٹری ہے جس میں تمام عناصر ہوتے ہیں۔ یہ درخت اصل نفاذ میں کبھی ظاہر نہیں ہوتا ہے، لیکن ٹینگو درخت کے درج ذیل ٹکڑوں کے پیچھے تصوراتی بنیاد ہے۔ خاص طور پر، حوالہ درخت کی اونچائی ہے۔ یہ سب سے طویل راستے کی لمبائی کے برابر ہے، اور اس لیے سب سے بڑے معاون درخت کے سائز کے برابر ہے۔ معاون درختوں کو معقول طور پر متوازن رکھ کر، معاون درختوں کی اونچائی کو اس سے محدود کیا جا سکتا ہے۔ یہ الگورتھم کی کارکردگی کی ضمانتوں کا ذریعہ ہے۔ ترجیحی راستے سب سے پہلے، ہم ہر نوڈ کے لیے اس کے ترجیحی بچے کی وضاحت کرتے ہیں، جو غیر رسمی طور پر روایتی بائنری سرچ ٹری تلاش کے ذریعے سب سے زیادہ حال ہی میں دیکھا جانے والا بچہ ہے۔ مزید رسمی طور پر، ایک ذیلی درخت T پر غور کریں، جس کی جڑیں p پر ہیں، بچوں l (بائیں) اور r (دائیں) کے ساتھ۔ ہم r کو p کے ترجیحی بچے کے طور پر سیٹ کرتے ہیں اگر T میں سب سے حال ہی میں رسائی شدہ نوڈ r پر جڑے ذیلی درخت میں ہے، اور l بصورت دیگر ترجیحی بچے کے طور پر۔ نوٹ کریں کہ اگر T کا سب سے حالیہ رسائی شدہ نوڈ خود p ہے، تو تعریف کے لحاظ سے l ترجیحی بچہ ہے۔ ترجیحی راستے کی وضاحت جڑ سے شروع کرکے اور ترجیحی بچوں کی پیروی کرتے ہوئے کی جاتی ہے جب تک کہ پتی کے نوڈ تک نہ پہنچ جائے۔ اس راستے پر نوڈس کو ہٹانے سے درخت کے بقیہ حصے کو کئی ذیلی درختوں میں تقسیم کیا جاتا ہے، اور ہم ہر ذیلی درخت پر دوبارہ کام کرتے ہیں (اس کی جڑ سے ایک ترجیحی راستہ بناتے ہیں، جو ذیلی درخت کو مزید ذیلی درختوں میں تقسیم کرتا ہے)۔ معاون درخت ترجیحی راستے کی نمائندگی کرنے کے لیے، ہم اس کے نوڈس کو متوازن بائنری سرچ ٹری، خاص طور پر سرخ سیاہ درخت میں محفوظ کرتے ہیں۔ ترجیحی راستے P میں ہر غیر پتوں والے نوڈ n کے لیے، اس میں ایک غیر ترجیحی چائلڈ c ہوتا ہے، جو ایک نئے معاون درخت کی جڑ ہے۔ ہم اس دوسرے معاون درخت کی جڑ (c) کو P میں n سے جوڑتے ہیں، اس طرح معاون درختوں کو ایک ساتھ جوڑتے ہیں۔ ہم معاون درخت کو ہر نوڈ پر اس نوڈ کے نیچے ذیلی درخت میں نوڈس کی کم سے کم اور زیادہ سے زیادہ گہرائی (حوالہ درخت میں گہرائی، یعنی) ذخیرہ کرکے بھی بڑھاتے ہیں۔ الگورتھم سرچنگ ٹینگو ٹری میں کسی عنصر کو تلاش کرنے کے لیے، ہم صرف حوالہ ٹری کو تلاش کرنے کی تقلید کرتے ہیں۔ ہم جڑ سے منسلک ترجیحی راستے کو تلاش کرکے شروع کرتے ہیں، جو اس ترجیحی راستے سے مطابقت رکھنے والے معاون درخت کو تلاش کرکے نقل کیا جاتا ہے۔ اگر معاون درخت مطلوبہ عنصر پر مشتمل نہیں ہے، تو تلاش مطلوبہ عنصر پر مشتمل ذیلی درخت کی جڑ کے والدین پر ختم ہو جاتی ہے (ایک اور ترجیحی راستے کا آغاز)، لہذا ہم صرف اس ترجیحی راستے کے لیے معاون درخت کو تلاش کر کے آگے بڑھتے ہیں، وغیرہ۔ اپ ڈیٹ کرنا ٹینگو ٹری کی ساخت کو برقرار رکھنے کے لیے (معاون درخت ترجیحی راستوں سے مطابقت رکھتے ہیں)، ہمیں کچھ اپ ڈیٹ کرنے کا کام کرنا چاہیے جب بھی ترجیحی بچے تلاش کے نتیجے میں تبدیل ہوتے ہیں۔ جب کوئی ترجیحی بچہ بدلتا ہے، تو ترجیحی راستے کا اوپری حصہ نچلے حصے سے الگ ہو جاتا ہے (جو اس کا اپنا ترجیحی راستہ بن جاتا ہے) اور دوسرے ترجیحی راستے سے دوبارہ منسلک ہو جاتا ہے (جو نیا نچلا حصہ بن جاتا ہے)۔ اسے مؤثر طریقے سے کرنے کے لیے، ہم اپنے معاون درختوں پر کٹ اینڈ جوائن آپریشنز کی وضاحت کریں گے۔ ہمارے جوائن آپریشن میں شامل ہوں دو معاون درختوں کو اس وقت تک یکجا کریں گے جب تک کہ ان کے پاس یہ خاصیت ہو کہ ایک کا اوپری نوڈ (حوالہ درخت میں) دوسرے کے نچلے نوڈ کا بچہ ہے (بنیادی طور پر، کہ متعلقہ ترجیحی راستوں کو مربوط کیا جا سکتا ہے)۔ یہ سرخ کالے درختوں کے کنکیٹینٹ آپریشن کی بنیاد پر کام کرے گا، جو دو درختوں کو اس وقت تک جوڑتا ہے جب تک کہ ان میں یہ خاصیت ہو کہ ایک کے تمام عناصر دوسرے کے تمام عناصر سے کم ہیں، اور تقسیم، جو الٹا کرتا ہے۔ حوالہ درخت میں، نوٹ کریں کہ اوپری راستے میں دو نوڈس موجود ہیں جیسے کہ ایک نوڈ نچلے راستے میں ہو اگر اور صرف اس صورت میں جب اس کی کلیدی قیمت ان کے درمیان ہو۔ اب، اوپری راستے کے نچلے راستے میں شامل ہونے کے لیے، ہم صرف ان دو نوڈس کے درمیان اوپری راستے کو تقسیم کرتے ہیں، پھر نیچے کے راستے کے معاون درخت کے دونوں طرف دونوں نتیجے میں معاون درختوں کو جوڑتے ہیں، اور ہمارے پاس ہمارا آخری، منسلک معاون درخت ہے۔ کٹ ہمارا کٹ آپریشن ایک ترجیحی راستے کو دیئے گئے نوڈ پر دو حصوں میں تقسیم کرے گا، ایک اوپری حصہ اور نیچے کا حصہ۔ مزید رسمی طور پر، یہ ایک معاون درخت کو دو معاون درختوں میں تقسیم کرے گا، جیسے کہ ایک حوالہ درخت میں ایک خاص گہرائی پر یا اس سے اوپر کے تمام نوڈس پر مشتمل ہو، اور دوسرے میں اس گہرائی سے نیچے کے تمام نوڈس پر مشتمل ہو۔ جیسا کہ جوائن میں ہے، نوٹ کریں کہ اوپری حصے میں دو نوڈس ہیں جو نچلے حصے کو بریکٹ کرتے ہیں۔ اس طرح، ہم راستے کو تین حصوں میں تقسیم کرنے کے لیے ان دونوں نوڈس میں سے ہر ایک پر آسانی سے تقسیم کر سکتے ہیں، پھر دو بیرونی حصوں کو جوڑ سکتے ہیں تاکہ ہم دو حصوں کے ساتھ ختم ہو جائیں، اوپر اور نیچے، جیسا کہ چاہیں۔ تجزیہ ٹینگو درختوں کے مسابقتی تناسب کو پابند کرنے کے لیے، ہمیں بہترین آف لائن درخت کی کارکردگی پر ایک نچلی حد تلاش کرنی چاہیے جسے ہم ایک معیار کے طور پر استعمال کرتے ہیں۔ ایک بار جب ہم ٹینگو ٹری کی کارکردگی پر اوپری حد تلاش کر لیتے ہیں، تو ہم انہیں مسابقتی تناسب کے پابند کرنے کے لیے تقسیم کر سکتے ہیں۔ انٹرلییو باؤنڈ زیادہ سے زیادہ آف لائن بائنری سرچ ٹری کے ذریعہ کیے گئے کام پر کم حد تلاش کرنے کے لیے، ہم دوبارہ ترجیحی بچوں کا تصور استعمال کرتے ہیں۔ رسائی کے سلسلے (تلاشوں کا ایک سلسلہ) پر غور کرتے وقت، ہم اس بات پر نظر رکھتے ہیں کہ حوالہ ٹری نوڈ کا ترجیحی چائلڈ کتنی بار تبدیل ہوتا ہے۔ سوئچ کی کل تعداد (تمام نوڈس پر خلاصہ) دی گئی رسائی کی ترتیب پر کسی بھی بائنری سرچ ٹری الگورتھم کے ذریعہ کیے گئے کام پر ایک آسپٹوٹک نچلی حد دیتی ہے۔ اسے انٹرلییو لوئر باؤنڈ کہا جاتا ہے۔ ٹینگو کا درخت اسے ٹینگو کے درختوں سے جوڑنے کے لیے، ہمیں ٹینگو کے درخت کے ذریعے کیے گئے کام پر دی گئی رسائی کے سلسلے کے لیے ایک اوپری باؤنڈ ملے گا۔ ہماری اوپری حد ہوگی، جہاں k انٹرلییوز کی تعداد ہے۔ کل لاگت کو دو حصوں میں تقسیم کیا گیا ہے، عنصر کی تلاش، اور مناسب غیر متغیرات کو برقرار رکھنے کے لیے ٹینگو ٹری کے ڈھانچے کو اپ ڈیٹ کرنا (ترجیحی بچوں کو تبدیل کرنا اور ترجیحی راستوں کو دوبارہ ترتیب دینا)۔ یہ دیکھنے کے لیے کہ تلاش (اپ ڈیٹ نہیں) اس حد میں فٹ بیٹھتی ہے، بس نوٹ کریں کہ ہر بار جب معاون درخت کی تلاش ناکام ہوتی ہے اور ہمیں اگلے معاون درخت کی طرف جانا پڑتا ہے، جس کے نتیجے میں ترجیحی چائلڈ سوئچ ہوتا ہے (چونکہ والدین کا ترجیحی راستہ اب بچے کے ترجیحی راستے میں شامل ہونے کے لیے سمتوں کو تبدیل کرتا ہے)۔ چونکہ تمام معاون درختوں کی تلاش ناکام ہوتی ہے سوائے آخری کے (ہم قدرتی طور پر ایک بار تلاش کامیاب ہونے کے بعد رک جاتے ہیں)، ہم معاون درختوں کی تلاش کرتے ہیں۔ ہر تلاش میں وقت لگتا ہے، کیونکہ ایک معاون درخت کا سائز حوالہ درخت کی اونچائی سے محدود ہوتا ہے۔ اپ ڈیٹ کرنا اپ ڈیٹ کی لاگت بھی اس حد کے اندر فٹ بیٹھتی ہے، کیونکہ ہمیں ہر وزٹ کیے گئے معاون درخت کے لیے صرف ایک کٹ اور ایک جوائن کرنا ہوتا ہے۔ ایک واحد کٹ یا جوائن آپریشن میں صرف مسلسل تعداد میں سرچز، اسپلٹس اور کنکیٹینٹس لگتے ہیں، جن میں سے ہر ایک معاون درخت کے سائز میں لوگرتھمک وقت لیتا ہے، لہذا ہماری اپ ڈیٹ لاگت ہے۔ مسابقتی تناسب ٹینگو ٹری مسابقتی ہیں، کیونکہ زیادہ سے زیادہ آف لائن بائنری سرچ ٹری کے ذریعے کیا گیا کام کم از کم k میں لکیری ہوتا ہے (ترجیحی چائلڈ سوئچز کی کل تعداد)، اور ٹینگو ٹری کے ذریعے کیا گیا کام زیادہ سے زیادہ ہوتا ہے۔ مزید دیکھیں اسپلے ٹری آپٹیمل بائنری سرچ ٹری ریڈ بلیک ٹری (ڈیٹا اسٹرکچر) حوالہ جات بائنری ٹری سرچ ٹری