نگهداری درخت دودویی متوازن IPR در یک محیط پردازش موازی با حافظه اشتراکی

درخت جستجوی دودویی به عنوان یکی از پرکاربردترین ساختارهای نگهداری داده مطرح است. این ساختمان داده کارامد، دارای کاربردهای فراوانی در سیستمهای ذخیره و بازیابی اطلاعات می باشد و به عنوان یک شاخص استاندارد، جهت پیاده سازی عملیات لغتنامه ای مورد استفاده قرار می گیرد. روشهای متفاوتی جهت متوازن سازی این نوع درخت پیشنهاد شده است، ولی در این بین، روش کاهش طول مسیر داخلی یا درخت،IPR متوازن ترین شکل درخت جستجوی دودویی را ایجاد می کند. ما در اینجا، الگوریتم هایی برای انجام عملیات موازی جستجو و درجk کلید به صورت همزمان، در درخت ،IPR ارائه داده ایم که جهت پیاده سازی در یک محیط پردازش موازی با حافظه اشتراکی، مناسب است. برای بررسی میزان کارایی و تعیین مرتبه زمانی الگوریتم ها از مدل محاسباتی موازیEREW PRAM استفاده شده ، است. نتایج بیانگر آن است که عملیات مذکور با هزینه بهینه، و به کارگیریk پردازشگر در زمان O(log k+log n) قابل اجرا است، که nتعداد گره های موجود را در درخت ،IPRمشخص می کند . جهت جلوگیری از تداخل و دسترسی همزمان به حافظه اشتراکی، PRAM یک روش زمانبندی عملی پردازشگرها، پیشنهاد کرده ایم، که احتیاج به حافظه اضافی ندارد و در مرتبه زمانی الگوریتم ها، نیز بی تاثیر است.

کلیدواژه ها:

درخت ، IPR درخت جستجوی متوازن ، رایانش ، موازی ، عملیات لغتنامه ایPRAM