درخت مبنا
درخت مبنا (radix tree) یا درخت پاتریشیا (Patricia tree) یا درخت کریت بیت (crit bit tree)، گروهی از داده ساختار‌های بر پایه ترای هستند که برای نگهداری مجموعه‌ای از رشته‌ها استفاده می‌شوند. برخلاف ترای معمولی، یال‌ها در درخت مبنا با مجموعه‌ای از کاراکترها برچسب‌گذاری می‌شوند. این برچسب می‌تواند رشته‌ای از کاراکترها، مجموعه از بیت‌ها به عنوان یک عدد صحیح یا یک باشد یا به‌طور کلی مجموعه‌ای اختیاری از اشیا به ترتیب نوشتاری. گاهی اوقات اسامی درخت مبنا و درخت کریت بیت فقط به درخت‌هایی اطلاق می‌شود که اعداد صحیح را نگهداری می‌کنند و درخت پاتریشیا، برای ورودی‌های کلی تر استفاده می‌شود اما ساختار آن در همه موارد به همین صورت است.
آسان تر است که درخت مبنا را به عنوان یک ترای در نظر بگیریم که از لحاظ حافظه بهینه شده است، چرا که هر گره با یک بچه در درخت مبنا با فرزندش ادغام می‌شود. نتیجه این می‌شود که هر گره داخلی حداقل دو بچه دارد. برخلاف ترای معمولی، یال‌ها همون طور که می‌توانند با یک کاراکتر برچسب‌گذاری شوند، در این جا می‌توانند با رشته‌ای از کاراکترها برچسب‌گذاری می‌شوند. این برای مجموعه‌های کوچک ( به خصوص اگر طول رشته‌ها زیاد باشد) یا برای مجموعه‌هایی که رشته هایشان حروف مشترک ابتدایی زیادی داشته باشند، بسیار کارآمدتر است.
این داده ساختار، عملیات‌های اصلی زیر را پشتیبانی می‌کند و همه آن‌ها از formula_1 هستند که formula_2 حداکثر طول یک کلمه در آن گروه از رشته هاست:
یک تعمیم متداول درخت مبنا، از گره‌های دورنگی استفاده می‌کند. سیاه و سفید. برای بررسی اینکه آیا یک رشته در درخت هست یا نه، جستجو از بالا آغاز می‌شود و یال‌های رشته ورودی را تا زمانی که دیگر نتوان جلوتر رفت، دنبال می‌کند. اگر جستجوی رشته تمام شده باشد و گره نهایی سیاه بوده باشد، جستجو ناموفق بوده‌است و اگر سفید بود، جستجو موفق. این روش ما را قادر می سازد که با استفاده از گره‌های سفید، طیف وسیعی از رشته‌ها با حروف ابتدایی مشترک را به یک درخت اضافه کنیم. سپس گروه کوچکی از استثنائات را با استفاده از درج آن‌ها با گره سیاه، با یک روش کارآمد از لحاظ فضا، حذف کنیم.
همانطور که ذکر شد، درخت مبنا برای ساخت آرایه‌های شرکت پذیر با کلیدهایی که به صورت رشته بیان می‌شوند، مفید است. و همچنین کاربرد ویژه‌ای در حوزه IP Addressها دارد، جایی که توانایی شامل شدن محدوده بزرگی از کلیدها با تعداد کمی استثنا، به‌طور ویژه‌ای برای سازماندهی سلسله مراتبی IP Addressها مناسب است. درخت مبنا همچنین در شاخص‌های وارونهٔ پرونده‌های متنی در بازیابی اطلاعات مورد استفاده قرار می‌گیرد.
اولین بار دونالد موریسون در 1968 چیزی که خودش درخت پاتریشیا نامید را توصیف کرد. نام آن در واقع مخفف "الگوریتم عملی برای بازیابی اطلاعات کدشده به صورت الفبای عددی" ( Practical Algorithm To Retrieve Information Coded In Alphanumeric)  می باشد. گرنوت گوهنبرگر در همان زمان به‌طور مستقل این داده ساختار را طراحی و توصیف کرد.
برخلاف درخت‌های متوازن، درخت مبنا اجازهٔ مراجعه، درج و حذف را در formula_1 به نسبت formula_4 را می‌دهد. زمانی که formula_5 این یک برتری به نظر نمی‌آید اما در یک درخت متوازن، هر مقایسه یک رشته در بدترین حالت formula_1 زمان نیاز دارد که خیلی از آن‌ها در عمل برای اشتراکات طولانی حروف ابتدایی کند هستند. در یک درخت، همهٔ مقایسه‌ها نیازمند زمان ثابتی است اما درخت مبنا formula_7 مقایسه برای جستجوی رشته‌ای به طول formula_7 نیاز دارد. درخت‌های مبنا می‌توانند این عملیاتها را با تعداد مقایسه کمتر و نیازمندی به تعداد گره‌های کمتر انجام دهند.
درخت مبنا از مزیت‌های درخت‌ها نیز بهره می برند. اگرچه آن‌ها می‌توانند برای رشته‌ای از عناصر یا عناصری با یک نگاشت (mapping) برگشت پذیر کارآمد به رشته‌ها به کار روند، اما فاقد عمومیت فوق العادهٔ درخت‌های متوازن جستجو می‌باشند که برای هر نوع دادهٔ دارای ترتیب می‌تواند استفاده شود. یک نگاشت برگشت پذیر به رشته ها، می‌تواند برای تولید ترتیب موردنیاز برای درخت متوازن جستجو استفاده شود اما نه همه جا. همچنین این می‌تواند گیج‌کننده باشد که برای یک نوع داده ای فقط عملیات مقایسه تعریف شده باشد و نه یک ترتیب مشخص.
اغلب گفته می‌شود که جداول درهم سازی ( ) عمل درج و حذف را در formula_9 انجام می دهند، اما این فقط وقتی درست است که فرض کنیم محاسبهٔ درهم سازی یک کلید، عملیاتی با زمان ثابت است. اگر درهم‌سازی یک کلید نیز محاسبه شود، جداول درهم‌سازی عمل درج و حذف را در formula_1 انجام می دهند که با توجه با شیوه ای که برای حل برخوردها اعمال می‌شود، در بدترین حالت حتی زمان بیشتری هم می‌گیرد. درخت مبنا کران بالای اجرای formula_1 برای درج و حذف دارد. همچنین عملیات‌های یافتن جد و جانشین نیز در جداول درهم‌سازی پیاده‌سازی نمی‌شود.
HAT-trie یک داده ساختار آگاه از حافظه پنهان مبتنی بر درخت مبناست که نگهداری، بازیابی و از سرگیری ترتیبی کارآمدی را برای رشته‌ها فراهم می‌کند. اما عملکرد آن با احترام به زمان و حافظه مصرفی آن، قابل مقایسه با جداول درهم‌سازی بهینه در استفاده از حافظه پنهان است.