درخت جستجو در مدل I/O. قسمت سوم: داده‌ساختارهای پویا در الگوریتم‌ها (جلسه پنجم)

در حالت عادی (مدل RAM نه I/O)، می‌توانیم از BST برای مرتب کردن عناصر استفاده کنیم. یعنی عناصر را یکی یکی به BST اضافه کنیم و با پیمایش درخت یک لیست مرتب از عناصر در زمان بهینه N log N به دست می‌آید.

اما مثلاً B-tree را با شروع از یک درخت M/B عنصری، به این هزینه می‌رسد:

sum_{i=0}^{N} log_(B) (M/B+Bi) = N log_(B) N/B

که با جواب بهینه در ضریب زیر متفاوت است:

B log_(B) M/B

که مقدار زیادی است.

یک راه حل ساختن B-tree از پایین به بالا است که با مرتب کردن عناصر امکان پذیر است. اما این کار را نمی‌شود با مثلاً persistent B-tree انجام داد. ما دنبال یک روش داده‌ساختارهای پویا در حالت کلی هستیم.

Buffer-tree:

یک B-tree با درجه رأس M/B و تعداد عناصر در هر برگ B در نظر می‌گیریم که هر گره یک بافر با اندازه‌ی M دارد.

هر وقت بافر یک گره پر می‌شود، عناصر را به عمق بعدی درخت می‌فرستیم. هر بلوک در هر عمق تعداد ثابتی بار پردازش می‌شود پس برای خالی کردن بافر، M/B زمان لازم است.

(زمان‌ها مثل قبل)

به روز رسانی: به حذف و درج‌ها زمان بدهید. با این کار بعداً می‌توانید اگر حذف و درج هر دو در بافر بودند آنها را حذف کنید و هیچ وقت در ساختار درختی اضافه نکنید. قبل از اینکه به ریشه اضافه کنید صبر کنید B عنصر جمع شود (بار اول مثلاً). هر وقت بافرها پر شدند آنها را خالی کنید.

برای مرتب سازی با این درخت، اول عناصر بافر را مرتب کنید، بعد آنها را با عناصر درخت که مرتب هستند ادغام کنید. این کار می‌تواند باعث پر شدن بافر شود که باید آن را در فرزندان تخلیه کنید. این کار را به صورت بازگشتی برای فرزندان هم انجام بدهید.

خالی کردن بافر با اندازه x زمان O(x/B+M/B) می‌برد که به O(x/B) تا I/O نیاز دارد.

ممکن است در این فرایند تعداد عناصر در بافر از M بیشتر باشند (وقتی که از گره بالایی آمده ولی هنوز اضافه نشده) ولی فقط Mتای آنها حداکثر نامرتب هستند.

وقتی بافر یک گره برگ خالی شد، نیاز به متوازن کردن است. (چون یک عمق اضافه شده)

همیشه این حالت برای درخت حفظ می‌کنیم که همه‌ی مسیرهای از ریشه تا برگ بافرشان خالی باشد. با این کار راحت می‌توانیم متوازن کنیم. (با ترکیب و تجزیه گره‌ها)

برای این کار باید به ترتیب BFS بافرها را خالی کنیم.

کاربرد buffer-tree در ساخت صف اولویت:

کوچکترین عنصر، در سمت چپ‌ترین مسیر قرار دارد، پس با O(1/B log_{M/B} N/B) تا I/O می‌توان به آن رسید.

فقط باید قبل از پرس‌و‌جو، بافرهای گره‌های این مسیر را تخلیه کنیم که برای اینکه زمان خالی کردن بافرها خیلی زیاد نشود، مجبوریم کل بافرهای درخت را خالی کنیم.

اما به صورت سرشکنی همچنان در همان زمان می‌شود عنصر را حذف کرد.