درخت آرایه درهم

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم رایانه درخت آرایه درهم داده ساختاری از نوع آرایه پویا می‌باشد که توسط ادوارد سیتارسکی در سال ۱۹۹۶ ارائه شد.

این نوع داده ساختار بر خلاف آرایه‌های پویا ی ساده که داده‌های خود را در یک قسمت از حافظه به صورت پشت سرهم نگه می‌دارند، از یک آرایه از حافظه‌های مجزا (یا برگ‌ها) برای نگه داری عناصر اطلاعات استفاده می‌کند. هدف اولیه این داده ساختار کاهش عملیات کپی کردن درایه ها به علت تغییر خودکار اندازهٔ آرایه و بهبود الگوهای استفاده از حافظه است.

در حالی که آرایه‌های پویا ی ساده که بر پایهٔ گسترش هندسی کار می‌کنند و از حافظهٔ خطی (Ω(n)) استفاده می‌کنند که n تعداد درایه‌های آرایه می‌باشد، درخت آرایه درهم فقط از حافظه‌ای از مرتبه (Square root of n)O استفاده می‌کند. بهینه‌سازی الگوریتم می‌تواند به طور کامل عملیات کپی کردن درایه‌ها را هنگام تغییر اندازهٔ آرایه حذف کند ولی با این کار فضای زیادی هدر خواهد شد.

در این نوع داده ساختار دسترسی به داده‌ها در زمان ثابت O(1) امکان‌پذیر است، اگرچه از آرایه‌های پویای معمولی کمی کند تر عمل می‌کند. در این الگوریتم هزینه سرشکن درج یک سری از اشیا به انتهای درخت آرایه درهم از O(1) خواهد بود. برخلاف نامش این نوع داده ساختار از توابع درهم سازی استفاده نمی‌کند.

A cartoon centipede reads books and types on a laptop.
یک درخت آرایه درهم کامل با ۱۶ درایه .

تعریف[ویرایش]

بنا به تعریف ادوارد سیتارسکی، درخت آرایه درهم یک لیست راهنمای سطح بالا دارد که شامل آرایه‌ای از برگ‌ها به تعداد توان دوم اندازه اش می‌باشد. تمامی آرایه‌های برگی، هم اندازه با لیست راهنمای سطح بالا می‌باشند. این ساختار از لحاظ ظاهری شباهت بسیاری به جدول درهم سازی با برخوردهای زنجیره‌ای بر اساس آرایه دارد که همین تشابه علت نام گذاری اش هم می‌باشد.

یک درخت آرایه درهم کامل می‌تواند square of m درایه را در خود نگه دارد که m اندازهٔ لیست راهنمای سطح بالا می‌باشد. استفاده از توان دوم این قابلیت را می‌دهد که آدرس دهی فیزیکی از طریق عملیات بیتی به جای عملیات حسابی خارج قسمت و باقی‌مانده با سرعت بیشتری انجام شود و هم چنین تضمین می‌کند هزینه سرشکن عملیات درج با وجود کپی کردن گاه‌و‌بیگاه سراسری به هنگام توسعه، هم چنان از O(1) خواهد بود.

افزایش و کاهش اندازه[ویرایش]

در آرایه پویای معمولی که از رویهٔ گسترش هندسی استفاده می‌کند، وقتی آرایه پر می‌شود، یک قطعه از حافظه به اندازهٔ دو برابر اندازهٔ فعلی به صورت پشت سرهم گرفته می‌شود و کل داده‌ها به مکان جدید انتقال می‌یابند. این روش تضمین می‌کند که هنگامی که آرایه توسعه یافته به نیمه ظرفیت جدیدش انتقال می‌یابد، هزینهٔ سر شکن عملیات از O(1) و هزینهٔ استفاده از حافظه از O(n) خواهد بود.

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

بقیهٔ برگ‌های اضافی تا زمانی که به آن ها احتیاجی نباشد، اضافه نمی‌شوند. بدین صورت فقط از حافظه‌ای از مرتبه (Square root of n)O استفاده می‌کنیم.

چندین راه دیگر برای تغییر اندازه درخت آرایه درهم[ویرایش]

زمانی که یک هشتم یک درخت آرایه درهم پر شد، می‌توانیم آن را به یک درخت آرایه درهم جدید با اندازه کوچکتر منتقل کنیم به صورتی که نیمی از آرایه جدید پر شود؛ راهکار دیگر آزاد کردن آرایه‌های برگی استفاده نشده است بدون آنکه اندازه برگ‌ها را تغییر بدهیم. بهینه‌سازی‌های اضافی شامل اضافه کردن برگ بدون تغییر اندازه و گسترش لیست راهنما به هنگام نیاز (احتمالاً از طریق گسترش هندسی) می‌شوند.

این کار می‌تواند به طور کامل عملیات کپی کردن درایه‌ها را حذف کند و حافظه‌ای از مرتبه O(n) با یک ضریب کوچک اشغال کند و عملیات جایگزینی را تنها زمانی انجام می‌دهد که داده‌ها به آستانه بالایی خود رسیده باشند.

داده ساختارهای مربوطه[ویرایش]

برودنیک الگوریتمی بر اساس آرایه پویا ارائه کرد که هزینه استفاده از حافظه آن همانند درخت آرایه درهم بود. پیاده‌سازی برودنیک آرایه‌های برگی پیشین را با استفاده از تابعی پیچیده تر نسبت به درخت آرایه درهم برای محاسبات آدرسی حفظ می‌کند.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  • ویکی‌پدیای انگلیسی