درخت مبنا ( radix tree ) یا درخت پاتریشیا ( Patricia tree ) یا درخت کریت بیت ( crit bit tree ) ، گروهی از داده ساختار های بر پایه ترای هستند که برای نگهداری مجموعه ای از رشته ها استفاده می شوند. برخلاف ترای معمولی، یال ها در درخت مبنا با مجموعه ای از کاراکترها برچسب گذاری می شوند. این برچسب می تواند رشته ای از کاراکترها، مجموعه از بیت ها به عنوان یک عدد صحیح یا یک IP address باشد یا به طور کلی مجموعه ای اختیاری از اشیا به ترتیب نوشتاری. گاهی اسامی درخت مبنا و درخت کریت بیت فقط به درخت هایی گفته می شود که اعداد صحیح را نگهداری می کنند و درخت پاتریشیا، برای ورودی های کلی تر استفاده می شود اما ساختار آن در همه موارد به همین صورت است.
آسان تر است که درخت مبنا را به عنوان یک ترای در نظر بگیریم که از لحاظ حافظه بهینه شده است، چرا که هر گره با یک بچه در درخت مبنا با فرزندش ادغام می شود. نتیجه این می شود که هر گره داخلی حداقل دو بچه دارد. برخلاف ترای معمولی، یال ها همون طور که می توانند با یک کاراکتر برچسب گذاری شوند، در این جا می توانند با رشته ای از کاراکترها برچسب گذاری می شوند. این برای مجموعه های کوچک ( به خصوص اگر طول رشته ها زیاد باشد ) یا برای مجموعه هایی که رشته هایشان حروف مشترک ابتدایی زیادی داشته باشند، بسیار کارآمدتر است.
این داده ساختار، عملیات های اصلی زیر را پشتیبانی می کند و همه آن ها از O ( k ) هستند که k حداکثر طول یک کلمه در آن گروه از رشته هاست:
• مراجعه: تعیین می کند که یک رشته در درخت هست یا نه. این عملیات کاملاً همانند درخت ها انجام می شود با این تفاوت که بعضی یال ها ممکن است نشانگر چندین کاراکتر باشند.
• درج: اضافه کردن یک رشته به درخت. درخت را تا زمانی که دیگر نتوانیم پیشروی بیشتری داشته باشیم، جستجو می کنیم. در این نقطه ما باید یک یال خروجی که با تمام کاراکترهای باقی مانده از رشته ورودی برچسب گذاری شده، اضافه کنیم. یا اگر از قبل یالی خروجی که در بخشی از حروف با باقی مانده کلمه اشتراک داشته باشد، وجود داشته باشد، آن را به دو یال تقسیم می کنیم ( که اولی با بخش مشترک آن، برچسب گذاری می شود ) و پیش می رویم. عمل تقسیم تضمین می کند که هیچ گرهی بیشتر از تعداد کاراکترهای رشته ای ممکن، بچه نداشته باشد.
• حذف: حذف یک رشته از درخت. ابتدا برگ متناظر را حذف می کنیم. سپس اگر پدر آن فقط یک بچه داشت، پدر را هم حذف کرده و دو یال لازم را با هم ادغام می کنیم.
• پیدا کردن جد: بزرگ ترین رشتهٔ کوچکتر از یک رشتهٔ داده شده را برحسب ترتیب واژه نگاری پیدا می کند.
• پیدا کردن جانشین: کوچک ترین رشتهٔ بزرگتر از رشتهٔ داده شده را بر حسب ترتیب واژه نگاری پیدا می کند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفآسان تر است که درخت مبنا را به عنوان یک ترای در نظر بگیریم که از لحاظ حافظه بهینه شده است، چرا که هر گره با یک بچه در درخت مبنا با فرزندش ادغام می شود. نتیجه این می شود که هر گره داخلی حداقل دو بچه دارد. برخلاف ترای معمولی، یال ها همون طور که می توانند با یک کاراکتر برچسب گذاری شوند، در این جا می توانند با رشته ای از کاراکترها برچسب گذاری می شوند. این برای مجموعه های کوچک ( به خصوص اگر طول رشته ها زیاد باشد ) یا برای مجموعه هایی که رشته هایشان حروف مشترک ابتدایی زیادی داشته باشند، بسیار کارآمدتر است.
این داده ساختار، عملیات های اصلی زیر را پشتیبانی می کند و همه آن ها از O ( k ) هستند که k حداکثر طول یک کلمه در آن گروه از رشته هاست:
• مراجعه: تعیین می کند که یک رشته در درخت هست یا نه. این عملیات کاملاً همانند درخت ها انجام می شود با این تفاوت که بعضی یال ها ممکن است نشانگر چندین کاراکتر باشند.
• درج: اضافه کردن یک رشته به درخت. درخت را تا زمانی که دیگر نتوانیم پیشروی بیشتری داشته باشیم، جستجو می کنیم. در این نقطه ما باید یک یال خروجی که با تمام کاراکترهای باقی مانده از رشته ورودی برچسب گذاری شده، اضافه کنیم. یا اگر از قبل یالی خروجی که در بخشی از حروف با باقی مانده کلمه اشتراک داشته باشد، وجود داشته باشد، آن را به دو یال تقسیم می کنیم ( که اولی با بخش مشترک آن، برچسب گذاری می شود ) و پیش می رویم. عمل تقسیم تضمین می کند که هیچ گرهی بیشتر از تعداد کاراکترهای رشته ای ممکن، بچه نداشته باشد.
• حذف: حذف یک رشته از درخت. ابتدا برگ متناظر را حذف می کنیم. سپس اگر پدر آن فقط یک بچه داشت، پدر را هم حذف کرده و دو یال لازم را با هم ادغام می کنیم.
• پیدا کردن جد: بزرگ ترین رشتهٔ کوچکتر از یک رشتهٔ داده شده را برحسب ترتیب واژه نگاری پیدا می کند.
• پیدا کردن جانشین: کوچک ترین رشتهٔ بزرگتر از رشتهٔ داده شده را بر حسب ترتیب واژه نگاری پیدا می کند.
wiki: درخت مبنا