ویکی‌پدیا

درخت بی: تفاوت میان نسخه‌ها

نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
خط ۱۸:
در [[علوم کامپیوتر]]، یک '''درخت بی''' یا بی‌تری {{انگلیسی|B-tree}} [[داده‌ساختاری درختی]] است که داده‌ها را به صورت مرتب‌شده نگه می‌دارد و جستجو، درج و حذف را در [[زمان مصرفی]] لگاریتمی میسر می‌سازد. بر خلاف [[درخت‌های جستجوی دودویی متوازن]] {{انگلیسی|Balanced binary search tree}}، این داده‌ساختار برای سیستم‌هایی که بلاک‌های عظیم اطلاعات را خوانده و می‌نویسند بهینه‌سازی شده است. این داده‌ساختار معمولاً در [[پایگاه‌های داده]] و [[سیستم پرونده]] استفاده می‌شود.
 
در درخت بی، گره‌های درونی (و نه برگ‌ها) می‌توانند یک شمارهٔ متغیر از محدوده‌ای ازپیش‌تعریف‌شده مربوط به گره‌های فرزند را اختیار کنند. زمانی که داده‌ها درج شده و یا از یک گره حذف می‌شوند، شمارهٔ گره‌های فرزند آن‌ها تغییر می‌کند. به منظور نگه‌داری محدودهٔ ازپیش‌تعریف‌شده، ممکن است گره‌های درونی به هم متصل شده و یا از هم جدا شوند. به دلیل اینکه محدوده‌ای از گره‌های فرزند مجاز هستند، درخت بی، همانند دیگر [[درخت‌های جستجوی متوازن]]، نیازی ندارد که به صورت متناوب اقدام به برقراری توازن کند، اما به دلیل اینکه گره‌ها کاملاً پر نیستند، ممکن است مقداری حافظه هدر رود. حدود بالا و پایین شمارهٔ گره‌های فرزند، برای یک پیاده‌سازی خاص، به طور خاص تعیین شده‌اند. برای مثال در یک درخت بیِ ۳–۲ (غالباً تنها با عنوان '''[[درخت ۳-۲]]''' مورد اشاره قرار می‌گیرد)، هر گره ممکن است تنها ۲ یا ۳ گرهٔ فرزند داشته‌باشد.
 
یک درخت بی با استلزام اینکه همهٔ [[برگ‌ها]] در یک عمق قرار داشته باشند، به صورت متوازن نگه داشته‌می‌شود. این عمق از طریق عناصری که به درخت اضافه می‌شوند کم‌کم افزایش می‌یابد، ولی افزایش در عمق سراسری، کم اتفاق می‌افتد و وجود یک گرهٔ اضافیِ دورتر از ریشه را نتیجه می‌دهد.
خط ۳۶:
عناصر هر گرهٔ درونی به عنوان مقادیری که [[زیردرخت]]‌های آن را تقسیم می‌کند، عمل می‌کنند. به عنوان مثال، اگر یک گرهٔ درونی سه فرزند (یا زیر درخت) داشته باشند، آنگاه این گره باید دو مقدار یا عنصر جداییِ ''a''<sub>1</sub> و ''a''<sub>2</sub> داشته باشد. همهٔ مقادیر زیردرخت چپ کمتر از ''a''<sub>1</sub>، همهٔ مقادیر زیردرخت وسطی بین مقادیر ''a''<sub>1</sub> و ''a''<sub>2</sub>، و همهٔ مقادیر زیردرخت راست بزرگتر از ''a''<sub>2</sub> خواهد بود.
 
گره‌های درونی—نه برگ‌ها—در یک درخت بی معمولاً به عنوان نمایندهٔ مجموعهٔ مرتبی از عناصر و اشاره‌گرهای فرزندان در نظر گرفته می‌شوند. هر گرهٔ درونی شامل یک '''بیشینه''' از ''U'' فرزند بوده و به جز ریشه، همگی یک '''کمینه''' از ''L'' فرزند دارند. برای همهٔ گره‌های درونی به جز ریشه، تعداد عناصر، یکی کمتر تعداد اشاره‌گرهای فرزندان می‌باشد؛ تعداد عناصر بین ''L-1'' و ''U-1''. می‌باشد. مقدار ''U'' باید 2''L'' و یا 2''L''-۱ باشد؛ بنابراین هر گرهٔ درونی حداقل نیمه‌پر است. این رابطه بین ''U'' و ''L'' ایجاب می‌کند که دو گرهٔ نیمه‌پر بتوانند به منظور ایجاد یک گرهٔ مطلوب به هم وصل شوند، و یک گرهٔ کامل بتواند به دو گرهٔ مطلوب منشعب شود. این ویژگی‌ها، حذف و درج مقادیر جدید را در یک درخت بی ممکن می‌سازد و امکان حفظ ویژگی‌های درخت بی را به درخت می‌دهد.
برگ‌ها نیز همین شرایط را برای تعداد عناصر دارند، با این تفاوت که نه فرزندی دارند و نه اشاره‌گر فرزند.
 
خط ۲۳۱:
* [[Rudolf Bayer|R. Bayer]] and E. McCreight, ''ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES'', Mathematical and Information Sciences Report No. 20, Mathematical and Information Sciences Laboratory, BOEING SCIENTIFIC RESEARCH LABORATORIES, July 1970.
''Summary:''
* [[دانلد کنوت]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.2.4: Multiway Trees, pp.&nbsp;481–491. Also, pp.&nbsp;476–477 of section 6.2.3 (Balanced Trees) discusses 2-3 trees.
* [[توماس اچ کورمن]]، [[Charles E. Leiserson]], [[رونالد ریوست]]، and [[کلیفورد استین]]. ''[[مقدمه‌ای بر الگوریتم‌ها]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 18: B-Trees, pp.&nbsp;434–454.
''Other''
{{پانویس}}
برگرفته از «https://fa.wikipedia.org/wiki/درخت_بی»