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

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

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

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

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

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

تعریف

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

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

افزایش و کاهش اندازه

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

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

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

چندین راه دیگر برای تغییر اندازه درخت آرایه درهم

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

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

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

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

جستارهای وابسته

منابع

Sitarski, Edward (September 1996), Algorithm Alley, "HATs: Hashed array trees", Dr. Dobb's Journal 21 (11)
Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (Technical Report CS-99-09), Resizable Arrays in Optimal Time and Space (PDF), Department of Computer Science, University of Waterloo {{citation}}: Check date values in: |date= و |year= / |date= mismatch (help)

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