موضوع مقاله: درخت مبنا | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت مبنا | مقدمه: برخلاف ترای معمولی، یال‌ها در درخت مبنا با مجموعه‌ای از کاراکترها برچسب‌گذاری می‌شوند. | ## بخش 1: درخت مبنا | این برچسب می‌تواند رشته‌ای از کاراکترها، مجموعه از بیت‌ها به عنوان یک عدد صحیح یا یک IP address باشد یا به‌طور کلی مجموعه‌ای اختیاری از اشیا به ترتیب نوشتاری. گاهی اسامی درخت مبنا و درخت کریت بیت فقط به درخت‌هایی گفته می‌شود که اعداد صحیح را نگهداری می‌کنند و درخت پاتریشیا، برای ورودی‌های کلی تر استفاده می‌شود اما ساختار آن در همه موارد به همین صورت است. نگاه کلی آسان‌تر است که درخت مبنا را به عنوان یک ترای در نظر بگیریم که از لحاظ حافظه بهینه شده‌است، چرا که هر گره با یک بچه در درخت مبنا با فرزندش ادغام می‌شود. برخلاف ترای معمولی، یال‌ها همون طور که می‌توانند با یک کاراکتر برچسب‌گذاری شوند، در این‌جا می‌توانند با رشته‌ای از کاراکترها برچسب‌گذاری می‌شوند. این برای مجموعه‌های کوچک (به خصوص اگر طول رشته‌ها زیاد باشد) یا برای مجموعه‌هایی که رشته‌هایشان حروف مشترک ابتدایی زیادی داشته باشند، بسیار کارآمدتر است. این داده ساختار، عملیات‌های اصلی زیر را پشتیبانی می‌کند و همه آن‌ها از هستند که حداکثر طول یک کلمه در آن گروه از رشته هاست: مراجعه: تعیین می‌کند که یک رشته در درخت هست یا نه. این عملیات کاملاً همانند درخت‌ها انجام می‌شود با این تفاوت که بعضی یال‌ها ممکن است نشانگر چندین کاراکتر باشند. در این نقطه ما باید یک یال خروجی که با تمام کاراکترهای باقی‌مانده از رشته ورودی برچسب‌گذاری شده، اضافه کنیم. یا اگر از قبل یالی خروجی که در بخشی از حروف با باقی‌مانده کلمه اشتراک داشته باشد، وجود داشته باشد، آن را به دو یال تقسیم می‌کنیم (که اولی با بخش مشترک آن، برچسب‌گذاری می‌شود) و پیش می‌رویم. عمل تقسیم تضمین می‌کند که هیچ گرهی بیشتر از تعداد کاراکترهای رشته‌ای ممکن، بچه نداشته باشد. | ## بخش 2: درخت مبنا | سپس اگر پدر آن فقط یک بچه داشت، پدر را هم حذف کرده و دو یال لازم را با هم ادغام می‌کنیم. پیدا کردن جد: بزرگ‌ترین رشتهٔ کوچکتر از یک رشتهٔ داده شده را برحسب ترتیب واژه نگاری پیدا می‌کند. پیدا کردن جانشین: کوچک‌ترین رشتهٔ بزرگتر از رشتهٔ داده شده را بر حسب ترتیب واژه نگاری پیدا می‌کند. برای بررسی اینکه آیا یک رشته در درخت هست یا نه، جستجو از بالا آغاز می‌شود و یال‌های رشته ورودی را تا زمانی که دیگر نتوان جلوتر رفت، دنبال می‌کند. اگر جستجوی رشته تمام شده باشد و گره نهایی سیاه بوده باشد، جستجو ناموفق بوده‌است و اگر سفید بود، جستجو موفق. این روش ما را قادر می‌سازد که با استفاده از گره‌های سفید، طیف وسیعی از رشته‌ها با حروف ابتدایی مشترک را به یک درخت اضافه کنیم. سپس گروه کوچکی از استثنائات را با استفاده از درج آن‌ها با گره سیاه، با یک روش کارآمد از لحاظ فضا، حذف کنیم. کاربردها همان‌طور که ذکر شد، درخت مبنا برای ساخت آرایه‌های شرکت پذیر با کلیدهایی که به صورت رشته بیان می‌شوند، مفید است. درخت مبنا همچنین در شاخص‌های وارونهٔ پرونده‌های متنی در بازیابی اطلاعات مورد استفاده قرار می‌گیرد. تاریخچه اولین بار دونالد موریسون در ۱۹۶۸ چیزی که خودش درخت پاتریشیا نامید را توصیف کرد. | ## بخش 3: درخت مبنا | مقایسه با دیگر داده ساختارها برخلاف درخت‌های متوازن، درخت مبنا اجازهٔ مراجعه، درج و حذف را در به نسبت را می‌دهد. زمانی که این یک برتری به نظر نمی‌آید اما در یک درخت متوازن، هر مقایسه یک رشته در بدترین حالت زمان نیاز دارد که خیلی از آن‌ها در عمل برای اشتراکات طولانی حروف ابتدایی کند هستند. در یک درخت، همهٔ مقایسه‌ها نیازمند زمان ثابتی است اما درخت مبنا مقایسه برای جستجوی رشته‌ای به طول نیاز دارد. درخت‌های مبنا می‌توانند این عملیاتها را با تعداد مقایسه کمتر و نیازمندی به تعداد گره‌های کمتر انجام دهند. اگرچه آن‌ها می‌توانند برای رشته‌ای از عناصر یا عناصری با یک نگاشت (mapping) برگشت‌پذیر کارآمد به رشته‌ها به کار روند، اما فاقد عمومیت فوق العادهٔ درخت‌های متوازن جستجو می‌باشند که برای هر نوع دادهٔ دارای ترتیب می‌تواند استفاده شود. یک نگاشت برگشت‌پذیر به رشته‌ها، می‌تواند برای تولید ترتیب موردنیاز برای درخت متوازن جستجو استفاده شود اما نه همه جا. همچنین این می‌تواند گیج‌کننده باشد که برای یک نوع داده ای فقط عملیات مقایسه تعریف شده باشد و نه یک ترتیب مشخص. اغلب گفته می‌شود که جداول درهم سازی ( Hash tables) عمل درج و حذف را در انجام می‌دهند، اما این فقط وقتی درست است که فرض کنیم محاسبهٔ درهم سازی یک کلید، عملیاتی با زمان ثابت است. اگر درهم‌سازی یک کلید نیز محاسبه شود، جداول درهم‌سازی عمل درج و حذف را در انجام می‌دهند که با توجه با شیوه ای که برای حل برخوردها اعمال می‌شود، در بدترین حالت حتی زمان بیشتری هم می‌گیرد. گونه‌های دیگر HAT-trie یک داده ساختار آگاه از حافظه پنهان مبتنی بر درخت مبناست که نگهداری، بازیابی و از سرگیری ترتیبی کارآمدی را برای رشته‌ها فراهم می‌کند. | ## جمع‌بندی | اما عملکرد آن با احترام به زمان و حافظه مصرفی آن، قابل مقایسه با جداول درهم‌سازی بهینه در استفاده از حافظه پنهان است.