درخت بی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز اصلاح متن با استفاده از AWB |
|||
خط ۶۶:
## میانهٔ منحصربه‌فرد از بین عناصر برگ و عنصر جدید انتخاب می‌شود.
## میانه به عنوان مقدار جدایی عمل می‌کند و مقادیر کمتر از میانه در گرهٔ چپ جدید و مقادیر بزرگتر از میانه در گرهٔ راست جدید قرار داده می‌شوند.
## این مقدارِ جدایی به گرهٔ پدر اضافه می‌شود، که این کار ممکن است باعث تقسیم شدن پدر شود، و این روند به همین ترتیب ادامه می‌یابد.
اگر این تقسیم شدن‌ها تا ریشه ادامه یابد، ریشهٔ جدیدی با یک مقدارِ جدایی یکتا و دو فرزند ایجاد می‌کند و دلیل این‌که حد پایین برای اندازهٔ گره‌های درونی برای ریشه اعمال نمی‌شود نیز همین می‌باشد. بیشینهٔ تعداد عناصر در یک گره ''U''-1 می‌باشد. زمانی که گره‌ای تقسیم می‌شود، یک عنصر به پدر انتقال می‌یابد، ولی یک عنصر هم اضافه می‌شود. بنابراین، باید امکان‌پذیر باشد که بیشینهٔ تعداد عناصر ( ''U''-1 ) به دو گرهٔ مجاز تقسیم شود. اگر این عدد فرد باشد، آنگاه ''U''=2''L'' بوده و یکی از گره‌های جدید شامل U''-2)/2 = ''L''-1'') عنصر و از این‌رو یک گرهٔ مجاز خواهد بود. دیگری هم که یک عنصر بیشتر دارد و از این‌رو گره‌ای مجاز خواهد بود. اگر ''U''-1 زوج باشد، آنگاه ''U''=2''L''-1، بوده و لذا 2''L''-2 عنصر در گره وجود دارد. نصف این عدد ''L''-1می باشد که کمینهٔ تعداد عناصری است که می‌تواند در هر گره وجود داشته‌باشد.
یک الگوریتم بهبودیافته، بر پایهٔ پیمایشی منفرد به سمت پایین از ریشه به گره‌ای که قرار است عمل درج در آن انجام شود و تقسیم کردن هر گرهٔ کاملی که در این مسیر با آن مواجه می‌شود، استوار است. این الگوریتم از نیاز به فراخوانی مجدد پدر به داخل حافظه جلوگیری به عمل می‌آورد، که این فراخوانی در صورتی که گره‌ها در حافظهٔ ثانویه قرار داشته‌باشند ممکن است پرهزینه باشد. به هرحال، برای استفاده از این الگوریتم بهبودیافته، ما باید قادر باشیم بدون افزودن یک عنصر جدید، عنصری را به پدر منتقل کنیم و ''U''-2 عنصر باقی‌مانده را به دو گرهٔ قابل قبول تقسیم نماییم. این امر مستلزم آن است که به جای ''U'' = 2''L'' داشته باشیم: ''U'' = 2''L''-1، که به عنوان دلیل بعضی از کتب درسی در قرار دادن این استلزام در تعریف درخت بی، به شمار می‌رود.
خط ۷۷:
* مکان‌یابی و حذف عنصر مورد نظر و سپس بازسازی درخت به منظور بازیابی ویژگی‌های آن.
یا
* انجام یک پیمایش به سمت پایین در درخت؛ با این تفاوت که پیش از مشاهدهٔ یک گره، درخت را بازسازی می‌کنیم تا فقط یک بار با کلیدی که قرار است حذف شود برخورد کنیم. بدین ترتیب این عنصر می‌تواند بدون نیاز به بازسازی بیشتر حذف شود.
الگوریتم زیر از راهبرد اخیر استفاده می‌کند.
خط ۸۳:
دو مورد خاص وجود دارند که به هنگام حذف یک عنصر باید در نظر گرفته شوند:
# عنصری که در یک گرهٔ درونی قرار دارد ممکن است یک جداکننده برای فرزندانش باشد.
# حذف یک عنصر، ممکن است آن را کمتر از کمینهٔ تعداد عناصر و فرزندان قرار دهد.
هرکدام از این موارد با مرتبهٔ درخت سروکار دارند.
خط ۹۲:
==== حذف از یک گرهٔ درونی ====
هر عنصر در یک گرهٔ درونی به عنوان یک مقدار جدایی برای دو زیردرخت عمل می‌کند، و وقتی عنصری حذف می‌شود، دو حالت رخ می‌دهد. حالت اول این‌که، هردو فرزندِ راستی و چپیِ عنصری که حذف شده، کمترین تعداد عناصر را دارند یعنی ''L''-1.آن‌ها می‌توانند در یک گره با 2''L''-2 عنصر به هم بپیوندند، این عدد از تجاوز نمی‌کند و لذا گرهٔ حاصل، یک گرهٔ قابل قبول خواهد بود. تا زمانی که مطمئن شویم این درختِ بی، داده‌های تکراری ندارد، باید به طور تکراری، با تحقیق در گرهٔ جدید، در صورت وجود عنصر مورد نظر در آن، آن عنصر را حذف کنیم.
حالت دوم این‌که، یکی از دو فرزند، حاوی تعداد بیشتری از کمینهٔ تعداد عناصر می‌باشد. پس یک جداکنندهٔ جدید باید برای آن زیردرخت‌ها یافت شود. توجه داشته باشید که بزرگ‌ترین عنصر در زیردرخت چپ، بزرگ‌ترین عنصری است که از جداکننده کوچک‌تر می‌باشد. به همین ترتیب، کوچک‌ترین عنصردر زیردرخت راست، کوچک‌ترین عنصری‌است که از جداکننده بزرگتر می‌باشد. هر دوی این عناصر در برگ قرار دارند، و هرکدام می‌توانند جداکنندهٔ جدیدی برای دو زیردرخت باشند.
خط ۲۴۲:
== منابع ==
{{
''Original papers:''
* [[Rudolf Bayer|R. Bayer]], ''Binary B-Trees for Virtual Memory'', Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego, California, November 11-12, 1971.
| |||