Radix tree
کمپیوٹر سائنس میں، ریڈکس ٹری (ریڈکس ٹرائی یا کمپیکٹ پریفیکس ٹری یا کمپریسڈ ٹرائی بھی) ایک ڈیٹا ڈھانچہ ہے جو اسپیس آپٹیمائزڈ ٹرائی (پریفیکس ٹری) کی نمائندگی کرتا ہے جس میں ہر نوڈ جو واحد بچہ ہے اس کے والدین کے ساتھ ضم ہوجاتا ہے۔ نتیجہ یہ ہے کہ ہر اندرونی نوڈ کے بچوں کی تعداد زیادہ سے زیادہ ریڈکس ٹری کے ریڈکس کی ہوتی ہے، جہاں ایک مثبت عدد اور 2 کی طاقت ہوتی ہے، جس میں ≤1 ہوتا ہے۔ باقاعدہ درختوں کے برعکس، کناروں کو عناصر کے سلسلے کے ساتھ ساتھ واحد عناصر کے ساتھ لیبل کیا جا سکتا ہے۔ یہ ریڈیکس کے درختوں کو چھوٹے سیٹوں کے لیے (خاص طور پر اگر تار لمبے ہوں) اور تاروں کے سیٹوں کے لیے جو لمبے سابقہ کا اشتراک کرتے ہیں، بہت زیادہ موثر بناتا ہے۔ باقاعدہ درختوں کے برعکس (جہاں پوری چابیاں ان کے آغاز سے لے کر عدم مساوات کے نقطہ تک مجموعی طور پر موازنہ کی جاتی ہیں)، ہر نوڈ پر موجود کلید کا موازنہ چکن آف بٹس سے کیا جاتا ہے، جہاں اس نوڈ پر اس چکن میں بٹس کی مقدار ریڈکس ٹرائی کا ریڈکس ہے۔ جب 2 ہوتا ہے، تو ریڈکس ٹرائی بائنری ہوتا ہے (یعنی اس نوڈ کے کلیدی کے 1 بٹ حصے کا موازنہ کریں)، جو ٹرائی کی گہرائی کو زیادہ سے زیادہ کرنے کی قیمت پر سپارنیس کو کم کرتا ہے-یعنی کلیدی میں غیر متفرق بٹ سٹرنگ کے تصادم کو زیادہ سے زیادہ کرتا ہے۔ جب 4 کی طاقت 2 ہوتی ہے، تو ریڈکس ٹرائی ایک-ایری ٹرائی ہوتا ہے، جو ممکنہ کم ہونے کی قیمت پر ریڈکس ٹرائی کی گہرائی کو کم کرتا ہے۔ اصلاح کے طور پر، کنارے کے لیبلز کو ایک سٹرنگ پر دو پوائنٹرز (پہلے اور آخری عناصر کے لیے) کا استعمال کرکے مستقل سائز میں محفوظ کیا جا سکتا ہے۔ نوٹ کریں کہ اگرچہ اس مضمون کی مثالیں سٹرنگز کو حروف کی ترتیب کے طور پر دکھاتی ہیں، لیکن سٹرنگ عناصر کی قسم کو من مانی طور پر منتخب کیا جا سکتا ہے ؛ مثال کے طور پر، ملٹی بائٹ کریکٹر انکوڈنگ یا یونیکوڈ کا استعمال کرتے وقت سٹرنگ کی نمائندگی کے بٹ یا بائٹ کے طور پر۔ ایپلی کیشنز ریڈکس ٹریز کلیدوں کے ساتھ ملحقہ صفوں کی تعمیر کے لیے مفید ہیں جن کا اظہار سٹرنگ کے طور پر کیا جا سکتا ہے۔ وہ آئی پی روٹنگ کے شعبے میں مخصوص اطلاق تلاش کرتے ہیں، جہاں چند مستثنیات کے ساتھ اقدار کی بڑی حدود کو شامل کرنے کی صلاحیت خاص طور پر آئی پی پتے کی درجہ بندی کی تنظیم کے لیے موزوں ہے۔ وہ معلومات کی بازیافت میں ٹیکسٹ دستاویزات کے الٹے انڈیکس کے لیے بھی استعمال ہوتے ہیں۔ آپریشنز ریڈکس ٹریز اندراج، حذف کرنے اور تلاش کی کارروائیوں کی حمایت کرتے ہیں۔ ذخیرہ شدہ ڈیٹا کی مقدار کو کم سے کم کرنے کی کوشش کرتے ہوئے اندراج ٹرائی میں ایک نئی تار کا اضافہ کرتا ہے۔ حذف کرنا ٹرائی سے ایک تار کو ہٹا دیتا ہے۔ تلاش کی کارروائیوں میں شامل ہیں (لیکن ضروری نہیں کہ ان تک محدود ہوں) درست تلاش، پیشرو تلاش کریں، جانشین تلاش کریں، اور سابقہ کے ساتھ تمام تار تلاش کریں۔ یہ تمام کارروائیاں O (k) ہیں جہاں k سیٹ میں موجود تمام تاروں کی زیادہ سے زیادہ لمبائی ہے، جہاں لمبائی کو ریڈکس ٹرائی کے ریڈکس کے برابر بٹس کی مقدار میں ماپا جاتا ہے۔ لک اپ آپریشن اس بات کا تعین کرتا ہے کہ آیا ٹرائی میں کوئی سٹرنگ موجود ہے۔ زیادہ تر آپریشن اپنے مخصوص کاموں کو سنبھالنے کے لیے اس نقطہ نظر میں کسی نہ کسی طرح ترمیم کرتے ہیں۔ مثال کے طور پر، وہ نوڈ جہاں سٹرنگ ختم ہوتی ہے اہمیت کا حامل ہو سکتا ہے۔ یہ عمل ٹرائز سے ملتا جلتا ہے سوائے اس کے کہ کچھ کنارے متعدد عناصر کو استعمال کرتے ہیں۔ مندرجہ ذیل فرضی کوڈ یہ فرض کرتا ہے کہ یہ طریقے اور اراکین موجود ہیں۔ ایج نوڈ ٹارگٹ نوڈ سٹرنگ لیبل ایجز ایجز فنکشن کا نوڈ سرنی ہے لیف () فنکشن لک اپ (سٹرنگ x) {// جڑ سے شروع کریں جس میں کوئی عنصر نہیں ملا نوڈ ٹریورس نوڈ: = جڑ ؛ انٹی عناصر فاؤنڈ: = 0 ؛// اس وقت تک ٹریورس کریں جب تک کہ کوئی پتی نہ مل جائے یا جاری رکھنا ممکن نہ ہو (ٹریورس نوڈ! = null & &! traverseNode.isLeaf () & & عناصر فاؤنڈ <x.length) {// x ایج میں ابھی تک نہ پائے جانے والے عناصر کی بنیاد پر تلاش کرنے کے لیے اگلا کنارے حاصل کریں اگلا کنارے: = traverseNode.edges سے کنارے کو منتخب کریں جہاں edge.label x.suffix (عناصر فاؤنڈ)/<<کا سابقہ ہے اگر (نیکسٹ ایج! = null) {// ٹریورس نوڈ کو تلاش کرنے کے لیے اگلے نوڈ کو سیٹ کریں: = nextEdge.targetNode ؛// کنارے کے عناصر پر محفوظ لیبل کی بنیاد پر پائے جانے والے انکریمنٹ عناصر فاؤنڈ + = nextEdge.label.length ؛} بصورت دیگر {// ٹرمینیٹ لوپ ٹریورس نوڈ: = null ؛}}// ایک میچ پایا جاتا ہے اگر ہم کسی لیف نوڈ پر پہنچ جاتے ہیں اور بالکل x.length عناصر کو استعمال کر چکے ہوتے ہیں تو واپسی (ٹریورس نوڈ! = null & & traverseNode.isLeaf () & & & عناصر فاؤنڈ = = x.length) ؛} اندراج ایک تار داخل کرنے کے لیے، ہم درخت کو اس وقت تک تلاش کرتے ہیں جب تک کہ ہم مزید پیش رفت نہ کر سکیں۔ اس موقع پر ہم یا تو ان پٹ سٹرنگ میں باقی تمام عناصر کے ساتھ لیبل شدہ ایک نیا باہر جانے والا کنارہ شامل کرتے ہیں، یا اگر پہلے سے ہی کوئی باہر جانے والا کنارہ باقی ان پٹ سٹرنگ کے ساتھ سابقہ کا اشتراک کر رہا ہے، تو ہم اسے دو کناروں میں تقسیم کرتے ہیں (پہلا مشترکہ سابقہ کے ساتھ لیبل کیا گیا ہے) اور آگے بڑھتے ہیں۔ یہ تقسیم کرنے والا مرحلہ اس بات کو یقینی بناتا ہے کہ کسی بھی نوڈ میں ممکنہ سٹرنگ عناصر سے زیادہ بچے نہ ہوں۔ اندراج کے کئی معاملات ذیل میں دکھائے گئے ہیں، حالانکہ مزید موجود ہو سکتے ہیں۔ نوٹ کریں کہ r صرف جڑ کی نمائندگی کرتا ہے۔ یہ فرض کیا جاتا ہے کہ کناروں کو خالی تاروں کے ساتھ لیبل کیا جا سکتا ہے تاکہ جہاں ضروری ہو تاروں کو ختم کیا جا سکے اور یہ کہ جڑ کا کوئی آنے والا کنارہ نہیں ہے۔ (خالی تار والے کناروں کا استعمال کرتے وقت اوپر بیان کردہ لک اپ الگورتھم کام نہیں کرے گا۔) حذف کرنا کسی درخت سے سٹرنگ x کو حذف کرنے کے لیے، ہم سب سے پہلے x کی نمائندگی کرنے والے پتے کا پتہ لگاتے ہیں۔ پھر، یہ فرض کرتے ہوئے کہ x موجود ہے، ہم متعلقہ لیف نوڈ کو ہٹا دیتے ہیں۔ اگر ہمارے لیف نوڈ کے والدین کے پاس صرف ایک اور بچہ ہے، تو اس بچے کا آنے والا لیبل والدین کے آنے والے لیبل سے منسلک ہوتا ہے اور بچے کو ہٹا دیا جاتا ہے۔ اضافی کارروائیاں تمام تاروں کو مشترکہ سابقہ کے ساتھ تلاش کریں: تاروں کی ایک صف واپس کرتا ہے جو ایک ہی سابقہ کے ساتھ شروع ہوتی ہے۔ پیشرو تلاش کریں: لیکسیگرافک ترتیب کے مطابق دی گئی تار سے کم سب سے بڑی تار کا پتہ لگاتا ہے۔ جانشین تلاش کریں: دی گئی تار سے بڑی سب سے چھوٹی تار کو لغت کے لحاظ سے تلاش کرتا ہے۔ تاریخ ڈیٹا اسٹرکچر کی ایجاد 1968 میں ڈونلڈ آر موریسن نے کی تھی، جن کے ساتھ یہ بنیادی طور پر وابستہ ہے، اور گرنٹ گوینبرجر نے۔ ڈونلڈ نوتھ، صفحات 498-500 دی آرٹ آف کمپیوٹر پروگرامنگ کے جلد III میں، ان کو "پیٹریشیا کے درخت" کہتے ہیں، غالبا موریسن کے مقالے کے عنوان میں مخفف کے بعد: "پیٹریشیا-الفانیومیرک میں کوڈ شدہ معلومات کو بازیافت کرنے کے لیے عملی الگورتھم"۔ آج، پیٹریشیا ٹرائز کو ریڈکس ٹری کے طور پر دیکھا جاتا ہے جس میں ریڈکس 2 کے برابر ہے، جس کا مطلب ہے کہ کلید کے ہر بٹ کا انفرادی طور پر موازنہ کیا جاتا ہے اور ہر نوڈ دو طرفہ (یعنی، بائیں بمقابلہ دائیں) شاخ ہے۔ دیگر ڈیٹا ڈھانچوں سے موازنہ (مندرجہ ذیل موازنہ میں، یہ فرض کیا جاتا ہے کہ چابیاں لمبائی k کی ہیں اور ڈیٹا ڈھانچہ n اراکین پر مشتمل ہے۔) متوازن درختوں کے برعکس، ریڈکس کے درخت او (لاگ این) کے بجائے او (کے) وقت میں تلاش، اندراج اور حذف کرنے کی اجازت دیتے ہیں۔ یہ ایک فائدہ کی طرح نہیں لگتا، کیونکہ عام طور پر k ± log n، لیکن ایک متوازن درخت میں ہر موازنہ ایک سٹرنگ کا موازنہ ہوتا ہے جس میں O (k) بدترین وقت کی ضرورت ہوتی ہے، جن میں سے بہت سے طویل عام سابقہ کی وجہ سے عملی طور پر سست ہوتے ہیں (اس صورت میں جہاں موازنہ سٹرنگ کے آغاز سے شروع ہوتا ہے)۔ ٹرائی میں، تمام موازنہ کے لیے مستقل وقت درکار ہوتا ہے، لیکن لمبائی میٹر کی تار کو تلاش کرنے کے لیے m موازنہ درکار ہوتا ہے۔ ریڈکس کے درخت ان کارروائیوں کو کم موازنہ کے ساتھ انجام دے سکتے ہیں، اور بہت کم نوڈس کی ضرورت ہوتی ہے۔ ریڈکس ٹری بھی ٹرائٹس کے نقصانات کا اشتراک کرتے ہیں، تاہم: چونکہ ان کا اطلاق صرف عناصر یا عناصر کے تاروں پر کیا جا سکتا ہے جس میں تاروں کی موثر طریقے سے ریورسیبل میپنگ ہو، ان میں متوازن سرچ ٹری کی مکمل عامیت کا فقدان ہے، جو کل ترتیب کے ساتھ کسی بھی ڈیٹا ٹائپ پر لاگو ہوتا ہے۔ سٹرنگز کے لیے ایک ریورسیبل میپنگ کا استعمال متوازن سرچ ٹریز کے لیے مطلوبہ کل آرڈر تیار کرنے کے لیے کیا جا سکتا ہے، لیکن اس کے برعکس نہیں۔ یہ بھی پریشانی کا باعث بن سکتا ہے اگر ڈیٹا ٹائپ صرف موازنہ آپریشن فراہم کرتا ہے، لیکن (ڈی) سیریلائزیشن آپریشن نہیں۔ عام طور پر کہا جاتا ہے کہ ہیش ٹیبلز میں O (1) داخل کرنے اور حذف کرنے کے اوقات کی توقع کی جاتی ہے، لیکن یہ صرف اس وقت درست ہے جب کلید کے ہیش کی گنتی کو مستقل وقت کا عمل سمجھا جائے۔ جب کلید کو ہیش کرنے کو مدنظر رکھا جاتا ہے، تو ہیش ٹیبل میں O (k) داخل کرنے اور حذف کرنے کے اوقات کی توقع کی جاتی ہے، لیکن بدترین صورت میں اس پر منحصر ہے کہ تصادم کو کس طرح سنبھالا جاتا ہے۔ ریڈکس کے درختوں میں بدترین صورت میں O (k) داخل اور حذف ہوتا ہے۔ ریڈکس کے درختوں کی جانشین/پیشرو کارروائیاں بھی ہیش ٹیبل کے ذریعے نافذ نہیں کی جاتی ہیں۔ متغیرات ریڈکس کے درختوں کی ایک عام توسیع نوڈس کے دو رنگوں کا استعمال کرتی ہے، 'سیاہ' اور 'سفید'۔ یہ چیک کرنے کے لیے کہ آیا دی گئی تار درخت میں محفوظ ہے، تلاش اوپر سے شروع ہوتی ہے اور ان پٹ تار کے کناروں کی پیروی کرتی ہے جب تک کہ مزید پیش رفت نہ ہو سکے۔ اگر سرچ سٹرنگ کا استعمال کیا جاتا ہے اور آخری نوڈ بلیک نوڈ ہے، تو سرچ ناکام ہو گئی ہے ؛ اگر یہ سفید ہے، تو سرچ کامیاب ہو گئی ہے۔ یہ ہمیں سفید نوڈس کا استعمال کرتے ہوئے ٹری میں مشترکہ سابقہ کے ساتھ تاروں کی ایک بڑی رینج شامل کرنے کے قابل بناتا ہے، پھر سیاہ نوڈس کا استعمال کرتے ہوئے انہیں داخل کرکے خلائی موثر انداز میں "مستثنیات" کے ایک چھوٹے سے سیٹ کو ہٹا دیتا ہے۔ ایچ اے ٹی ٹری ریڈکس ٹریز پر مبنی کیش سے آگاہ ڈیٹا ڈھانچہ ہے جو موثر سٹرنگ اسٹوریج اور بازیافت پیش کرتا ہے، اور تکرار کا حکم دیتا ہے۔ کارکردگی، وقت اور جگہ دونوں کے حوالے سے، کیش سے آگاہ ہیش ٹیبل سے موازنہ ہے۔ پیٹریشیا ٹرائی ریڈکس 2 (بائنری) ٹرائی کا ایک خاص ورژن ہے، جس میں ہر کلید کے ہر بٹ کو واضح طور پر ذخیرہ کرنے کے بجائے، نوڈس صرف پہلے بٹ کی پوزیشن کو محفوظ کرتے ہیں جو دو ذیلی درختوں میں فرق کرتا ہے۔ ٹریورسل کے دوران الگورتھم سرچ کلید کے انڈیکس شدہ بٹ کی جانچ کرتا ہے اور مناسب بائیں یا دائیں ذیلی درخت کا انتخاب کرتا ہے۔ پیٹریشیا ٹرائی کی قابل ذکر خصوصیات میں یہ شامل ہے کہ ٹرائی میں ذخیرہ شدہ ہر منفرد کلید کے لیے صرف ایک نوڈ داخل کرنے کی ضرورت ہوتی ہے، جس سے پیٹریشیا معیاری بائنری ٹرائی سے کہیں زیادہ کمپیکٹ ہو جاتا ہے۔ نیز، چونکہ اصل چابیاں اب واضح طور پر محفوظ نہیں ہیں اس لیے میچ کی تصدیق کے لیے انڈیکس شدہ ریکارڈ پر ایک مکمل کلیدی موازنہ کرنا ضروری ہے۔ اس سلسلے میں پیٹریشیا ہیش ٹیبل کا استعمال کرتے ہوئے انڈیکسنگ سے ایک خاص مشابہت رکھتی ہے۔ انکولی ریڈکس ٹری ایک ریڈکس ٹری ورژن ہے جو انکولی نوڈ کے سائز کو ریڈکس ٹری میں ضم کرتا ہے۔ معمول کے ریڈکس درختوں کی ایک بڑی خرابی جگہ کا استعمال ہے، کیونکہ یہ ہر سطح پر مستقل نوڈ سائز کا استعمال کرتا ہے۔ ریڈکس ٹری اور انکولی ریڈکس ٹری کے درمیان سب سے بڑا فرق چائلڈ عناصر کی تعداد کی بنیاد پر ہر نوڈ کے لیے اس کا متغیر سائز ہے، جو نئی اندراجات کو شامل کرتے ہوئے بڑھتا ہے۔ لہذا، انکولی ریڈکس ٹری اپنی رفتار کو کم کیے بغیر جگہ کے بہتر استعمال کی طرف لے جاتا ہے۔ ایک عام عمل یہ ہے کہ ایسے حالات میں جہاں والدین ڈیٹا سیٹ میں ایک درست کلید کی نمائندگی کرتے ہیں، صرف ایک بچے کے ساتھ والدین کو اجازت نہ دینے کے معیار میں نرمی کی جائے۔ ریڈکس ٹری کی یہ قسم اس سے زیادہ جگہ کی کارکردگی حاصل کرتی ہے جو کم از کم دو بچوں کے ساتھ صرف اندرونی نوڈس کی اجازت دیتی ہے۔ پریفیکس ٹری (جسے ٹرائی بھی کہا جاتا ہے) ڈیٹرمینیسٹک ایسائکلک فائنیٹ اسٹیٹ آٹومیٹن (ڈی اے ایف ایس اے) ٹرنری سرچ ٹرائزز ہیش ٹرائی ڈیٹرمینیٹک فائنیٹ آٹومیٹا جوڈی ایرے سرچ الگورتھم ایکسٹینڈیبل ہیشنگ ہیش ایرے میپڈ ٹرائی پریفیکس ہیش ٹری برسٹسورٹ لولی الگورتھم ہفمین کوڈنگ حوالہ جات بیرونی لنکس الگورتھم اور ڈیٹا اسٹرکچرز ریسرچ اینڈ ریفرنس میٹریل: پیٹریشیا، لائیڈ ایلیسن، موناش یونیورسٹی پیٹریشیا ٹری، این آئی ایس ٹی ڈکشنری آف الگورتھم اینڈ ڈیٹا اسٹرکچرز کریٹ بٹ ٹریز، ڈینیل جے برنسٹین ریڈکس ٹری اے پی آئی لینکس کرنل میں، جوناتھن کاربیٹ کارٹ کی طرف سے لینکس دانا نفاذ، جو دوسری چیزوں کے علاوہ پیج کیش کے لیے استعمال ہوتا ہے۔ جی این یو سی + + اسٹینڈرڈ لائبریری میں ریڈیکس ٹری پریکٹیکل الگورتھم ٹیمپلیٹ لائبریری کے نیال گیلاگر سی #نفاذ کے ذریعے، کنکرنٹ ریڈیکس ٹری کا جاوا نفاذ، رومن ایس کلیوجکوف پیٹریشیا ٹری سی + + ٹیمپلیٹ کلاس کے نفاذ کے ذریعے "بگ اینڈین پیٹریشیا ٹریز پر مبنی" ریڈو گروین ہاسکل معیاری لائبریری کے نفاذ کے ذریعے پیٹریشیا ٹرائز (وی سی + +> = 2003، جی سی سی جی + + 3. x) پر ایک سی + + لائبریری ہے۔ ویب براؤز ایبل سورس کوڈ۔ جاوا میں پیٹریشیا ٹرائی کا نفاذ، راجر کاپسی اور سام برلن کے کریٹ بٹ درختوں کے ذریعہ سی کوڈ سے فورک کیا گیا ڈینیل جے برنسٹین پیٹریشیا ٹرائی کے ذریعہ سی میں نفاذ، لبکپروپس میں پیٹریشیا ٹریز: او سی اے ایم ایل میں انٹیجرز پر موثر سیٹ اور نقشے، جین کرسٹوف فلیٹری ریڈکس ڈی بی (پیٹریشیا ٹرائی) کے ذریعہ سی میں نفاذ، جی بی ورسیانی لیبارٹ کے ذریعہ-انکولی ریڈکس درختوں کو سی میں نافذ کیا گیا، ارمون ڈیڈگر کے ذریعہ دوسرے شراکت داروں کے ساتھ (اوپن سورس، بی ایس ڈی 3-شق لائسنس) ایک کریٹ بٹ ٹری ریکس کا نیم نفاذ، اے این ایس آئی سی میں ریڈکس ٹری کا نفاذ سالواٹور سانفلیپو (آر ای ڈی آئی ایس کے تخلیق کار) کے ذریعہ