کدام ساختار داده توسط Map استفاده می شود؟

مشاهده بحث

بهبود مقاله

ذخیره مقاله

مانند مقاله

نقشه چیست؟

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

نقشه بخشی از کتابخانه STL است که جفت‌های ارزش کلید را در آن ذخیره می‌کند و هیچ دو مقداری کلیدهای یکسانی ندارند اما کلیدهای مختلف می‌توانند مقادیر مشابهی را ذخیره کنند. نقشه کلیدها را به ترتیب مرتب شده ذخیره می کند.

اینها برخی از توابع هستند که نقشه با پیچیدگی های زمانی خود استفاده می کند:

  • insert() – پیچیدگی زمانی O (Log N)
  • حذف() – پیچیدگی زمانی O (Log N)
  • پاک کردن() – پیچیدگی زمانی O (Log N)
  • پیدا کردن() – پیچیدگی زمانی O (Log N)

کدام ساختار داده توسط نقشه استفاده می شود؟

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

این دو روش اما

برای پیاده سازی داخلی نقشه از آن استفاده می کند درخت سرخ سیاه.

برای متعادل کردن درخت پس از درج/حذف، هر دو الگوریتم از مفهوم چرخش استفاده می کنند که در آن گره های درخت چرخانده می شوند تا تعادل مجدد را انجام دهند. در حالی که در هر دو الگوریتم عملیات درج/حذف است O (log N)، در مورد درخت قرمز-سیاه چرخش مجدد تعادل است O (1) عملیات در حالی که با AVL این یک است O(log N) عملیات، کارآمدتر کردن درخت قرمز-سیاه در این جنبه از مرحله تعادل مجدد و یکی از دلایل احتمالی است که بیشتر مورد استفاده قرار می گیرد.

چیستدرخت سرخ سیاه؟

درخت قرمز-سیاه نوعی درخت جستجوی باینری خود متعادل کننده است که در آن هر گره یک بیت اضافی دارد و آن بیت اغلب به عنوان رنگ تفسیر می شود. (قرمز یا سیاه) که برای اطمینان از متعادل ماندن درخت در حین درج و حذف استفاده می شود.

برای کسب اطلاعات بیشتر در مورد درخت قرمز-سیاه لطفا به مقاله در ” مراجعه کنید.درخت سرخ سیاه

نمودار درخت قرمز-سیاه

نمودار درخت قرمز-سیاه

به این blog امتیاز دهید

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

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد.