برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: بنا به تعریف ادوارد سیتارسکی، درخت آرایه درهم یک لیست راهنمای سطح بالا دارد که شامل آرایه‌ای از برگ‌ها به تعداد توان دوم اندازه‌اش می‌باشد. تمامی آرایه‌های برگی، هم‌اندازه با لیست راهنمای سطح بالا می‌باشند. این ساختار از لحاظ ظاهری شباهت بسیاری به جدول درهم سازی با برخوردهای زنجیره‌ای بر اساس آرایه دارد که همین تشابه علت نام‌گذاری‌اش هم می‌باشد. یک درخت آرایه درهم کامل می‌تواند درایه را در خود نگه دارد که m اندازه لیست راهنمای سطح بالا می‌باشد. استفاده از توان دوم این قابلیت را می‌دهد که آدرس‌دهی فیزیکی از طریق عملیات بیتی به جای عملیات حسابی خارج قسمت و باقی‌مانده با سرعت بیشتری انجام شود و هم‌چنین تضمین می‌کند هزینه سرشکن عملیات درج با وجود کپی کردن گاه‌و‌بیگاه سراسری به هنگام توسعه، هم‌چنان از o (۱) خواهد بود. در آرایه پویای معمولی که از رویه گسترش هندسی استفاده می‌کند، وقتی آرایه پر می‌شود، یک قطعه از حافظه به اندازه دو برابر اندازه فعلی به صورت پشت سرهم گرفته می‌شود و کل داده‌ها به مکان جدید انتقال می‌یابند. این روش تضمین می‌کند که هنگامی‌که آرایه توسعه‌یافته به نیمه ظرفیت جدیدش انتقال می‌یابد، هزینه سر شکن عملیات از o (۱) و هزینه استفاده از حافظه از o (n) خواهد بود. زمانی که یک درخت آرایه درهم پر است، لیست راهنما و برگ‌های آن باید دو برابر اندازه قبلی شوند تا برای عملیات درج اضافی فضای خالی داشته باشد. داده‌های موجود در داده ساختار قبلی به مکان‌های جدید انتقال می‌یابند. فقط یک برگ جدید گرفته می‌شود و به آرایه اصلی اضافه می‌شود که باعث می‌شود تنها یک چهارم از ظرفیت جدیدش اشغال شود. بقیه برگ‌های اضافی تا زمانی که به آن‌ها احتیاجی نباشد، اضافه نمی‌شوند. بدین صورت فقط از حافظه‌ای از مرتبه () o استفاده می‌کنیم. زمانی که یک هشتم یک درخت آرایه درهم پر شد، می‌توانیم آن را به یک درخت آرایه درهم جدید با اندازه کوچک‌تر منتقل کنیم به صورتی که نیمی از آرایه جدید پر شود؛ راهکار دیگر آزاد کردن آرایه‌های برگی استفاده نشده‌است بدون آنکه اندازه برگ‌ها را تغییر بدهیم. بهینه‌سازی‌های اضافی شامل اضافه کردن برگ بدون تغییر اندازه و گسترش لیست راهنما به هنگام نیاز (احتمالا از طریق گسترش هندسی) می‌شوند. این کار می‌تواند به‌طور کامل عملیات کپی کردن درایه‌ها را حذف کند و حافظه‌ای از مرتبه o …
برداشت:
در علوم رایانه درخت آرایه درهم داده‌ساختاری از نوع آرایه پویا می‌باشد که توسط ادوارد سیتارسکی در سال ۱۹۹۶ ارائه شد . این نوع داده ساختار بر خلاف آرایه‌های پویای ساده که داده‌های خود را در یک قسمت از حافظه به صورت پشت سرهم نگه می‌دارند ، از یک آرایه از حافظه‌های مجزا (یا برگ‌ها) برای نگهداری عناصر اطلاعات استفاده می‌کند . هدف اولیه این داده ساختار کاهش عملیات کپی کردن درایه‌ها به علت تغییر خودکار اندازهٔ آرایه و بهبود الگوهای استفاده از حافظه است . بهینه‌سازی الگوریتم می‌تواند به‌طور کامل عملیات کپی کردن درایه‌ها را هنگام تغییر اندازهٔ آرایه حذف کند ولی با این کار فضای زیادی هدر خواهد شد . برخلاف نامش این نوع داده ساختار از توابع درهم سازی استفاده نمی‌کند .