درخت بی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات: تبدیل به هٔ |
جز ربات:اصلاح فاصلهٔ مجازی |
||
خط ۱:
{{اشتباه نشود|درخت دودویی}}
[[پرونده:B-tree.png|thumb|400px|یک درخت بی از مرتبهٔ ۵]]
در [[علوم کامپیوتر]]، یک '''درخت بی''' یا بی‌تری {{انگلیسی|B-tree}} [[داده‌ساختاری درختی]] است که داده‌ها را به صورت مرتب‌شده نگه می‌دارد و جستجو، درج و حذف را در [[زمان مصرفی]] لگاریتمی میسر می‌سازد. بر خلاف [[درخت‌های جستجوی دودویی متوازن]] {{انگلیسی|Balanced binary search tree}}، این داده‌ساختار برای سیستم‌هایی که بلاک‌های عظیم اطلاعات را خوانده و می‌نویسند بهینه‌سازی شده است. این داده‌ساختار
در درخت بی، گره‌های درونی(و نه برگ‌ها) می‌توانند یک شمارهٔ متغیر از محدوده‌ای ازپیش‌تعریف‌شده مربوط به گره‌های فرزند را اختیار کنند. زمانی که داده‌ها درج شده و یا از یک گره حذف می‌شوند، شمارهٔ گره‌های فرزند آن‌ها تغییر می‌کند. به منظور نگه‌داری محدودهٔ ازپیش‌تعریف‌شده، ممکن است گره‌های درونی به هم متصل شده و یا از هم جدا شوند. به دلیل اینکه محدوده‌ای از گره‌های فرزند مجاز هستند، درخت بی، همانند دیگر [[درخت‌های جستجوی متوازن]], نیازی ندارد که به صورت متناوب اقدام به برقراری توازن کند، اما به دلیل اینکه گره‌ها کاملاً پر نیستند، ممکن است مقداری حافظه هدر رود. حدود بالا و پایین شمارهٔ گره‌های فرزند، برای یک پیاده‌سازی خاص، به طور خاص تعیین شده‌اند. برای مثال در یک درخت بیِ ۳-۲ (غالباً تنها با عنوان '''[[درخت ۳-۲]]''' مورد اشاره قرار می‌گیرد)، هر گره ممکن است تنها ۲ یا ۳ گرهٔ فرزند داشته‌باشد.
خط ۱۹:
== ساختارهای گره ==
عناصر هر گرهٔ درونی به عنوان مقادیری که [[زیردرخت]]
گره‌های درونی-- نه برگ‌ها-- در یک درخت بی معمولا" به عنوان نمایندهٔ مجموعهٔ مرتبی از عناصر و اشاره‌گرهای فرزندان در نظر گرفته می‌شوند. هر گرهٔ درونی شامل یک '''بیشینه ''' از ''U'' فرزند بوده و به جز ریشه، همگی یک '''کمینه ''' از ''L'' فرزند دارند. برای همهٔ گره‌های درونی به جز ریشه، تعداد عناصر، یکی کمتر تعداد اشاره‌گرهای فرزندان می‌باشد؛ تعداد عناصر بین ''L-1'' و ''U-1''. می‌باشد. مقدار ''U'' باید 2''L'' و یا 2''L''-1 باشد؛ بنابراین هر گرهٔ درونی حداقل نیمه‌پر است. این رابطه بین ''U'' و ''L'' ایجاب می‌کند که دو گرهٔ نیمه‌پر بتوانند به منظور ایجاد یک گرهٔ مطلوب به هم وصل شوند، و یک گرهٔ کامل بتواند به دو گرهٔ مطلوب منشعب شود. این ویژگی‌ها، حذف و درج مقادیر جدید را در یک درخت بی ممکن می‌سازد و امکان حفظ ویژگی‌های درخت بی را به درخت می‌دهد.
| |||