ساختار داده جستجو
در علوم کامپیوتر، یک ساختار داده جستجو[نیازمند منبع] (به انگلیسی: Search Data Structure) نوعی ساختمان دادهها است که امکان بازیابی کارآمد آیتمهای خاص را از مجموعهای از آیتمها فراهم میکند؛ مانند بازیابی یک رکورد یا ساختار (علم کامپیوتر) مشخص از یک پایگاه داده.
سادهترین، عمومیترین و در عین حال ناکارآمدترین ساختار دادهٔ جستجو، تنها یک فهرست ترتیبی نامرتب از همهٔ اعضاست. یافتن عضو مورد نظر در چنین فهرستی، با استفاده از روش جستجوی خطی، ناگزیر به تعداد عملیاتی متناسب با تعداد اعضا (n) نیاز دارد؛ چه در بدترین حالت و چه در حالت متوسط. ساختارهای دادهٔ جستجوی مفیدتر، امکان بازیابی سریعتر را فراهم میکنند؛ با این حال، تنها به انواع خاصی از جستجو محدود هستند. افزون بر این، از آنجا که هزینهٔ ساخت این ساختارها دستکم متناسب با n است، استفاده از آنها فقط زمانی مقرونبهصرفه خواهد بود که قرار باشد چندین جستجو روی یک پایگاه داده (یا پایگاه دادهای که بین دو جستجو تغییر چندانی نمیکند) انجام شود.
ساختارهای دادهٔ جستجوی ایستا برای پاسخدهی به تعداد زیادی درخواست (کوئری) بر روی یک پایگاه داده ثابت طراحی شدهاند؛ درحالیکه ساختارهای پویا امکان درج، حذف یا بهروزرسانی دادهها را میان درخواستهای متوالی فراهم میکنند. در حالت پویا، باید هزینهٔ اصلاح ساختار جستجو برای سازگار شدن با تغییرات پایگاه داده را نیز مدنظر قرار داد.
ردهبندی
[ویرایش]سادهترین نوع کوئری این است که یک رکورد را بیابیم که مقدار یک فیلد خاص (یعنی کلید) آن برابر با مقدار معینی (v) باشد. انواع رایج دیگر کوئری عبارتاند از: «یافتن عضوی با کمترین (یا بیشترین) مقدار کلید»، «یافتن رکوردی با بیشترین مقدار کلید که از v بزرگتر نباشد»، و «یافتن تمام اعضایی که مقدار کلید آنها بین دو حد مشخص vmin و vmax باشد».
در برخی از پایگاه دادهها، مقادیر کلید ممکن است نقاطی در یک (فضای چندبعدی) باشند. برای مثال، کلید میتواند یک موقعیت جغرافیایی (مانند عرض جغرافیایی و طول جغرافیایی) بر روی زمین باشد. در این حالت، انواع رایج کوئریها عبارتند از: «یافتن رکوردی با کلیدی که نزدیکترین به یک نقطهٔ معین v باشد»، یا «یافتن همهٔ آیتمهایی که کلید آنها در فاصلهٔ مشخصی از v قرار دارد»، یا «یافتن همهٔ آیتمها در یک ناحیهٔ معین R از این فضا».
یک حالت خاص رایج از گونهٔ اخیر، کوئریهای بازهای همزمان روی دو یا چند کلید ساده است؛ برای مثال: «یافتن همهٔ رکوردهای کارمندان با حقوق بین ۵۰٬۰۰۰ تا ۱۰۰٬۰۰۰ و تاریخ استخدام بین سالهای ۱۹۹۵ تا ۲۰۰۷».
یک مورد خاص رایج از حالت دوم، کوئریهای دامنه همزمان روی دو یا چند کلید ساده است؛ مانند «یافتن تمام رکوردهای کارمندان با حقوق بین ۵۰٬۰۰۰ و ۱۰۰٬۰۰۰ و استخدام بین سالهای ۱۹۹۵ و ۲۰۰۷».
کلیدهای مرتب منفرد
[ویرایش]- آرایه (در صورتی که مقادیر کلیدها در یک بازهٔ نسبتاً متراکم قرار داشته باشند)
- فهرست مرتب بر اساس اولویت؛ (نگاه کنید به جستجوی خطی)
- آرایه مرتبشده بر حسب کلید؛ (نگاه کنید به جستجوی دودویی)
- درخت جستجوی دودویی خود-متوازن
- جدول درهمسازی
یافتن کوچکترین عضو
[ویرایش]تحلیل حدی در بدترین حالت
[ویرایش]در این جدول، نماد مجانبی به این معناست که «در بدترین حالت، مقدار از چندبرابر ثابتی از بیشتر نمیشود.»
| ساختار داده | درج | حذف | تعادلیابی | دسترسی به اندیس | جستجو | یافتن کمینه | یافتن بیشینه | مصرف حافظه |
|---|---|---|---|---|---|---|---|---|
| آرایه نامرتب | O(1) | O(1) | N/A | O(1) | O(n) | O(n) | O(n) | O(n) |
| آرایه مرتب | O(n) | O(n) | N/A | O(1) | O(log n) | O(1) | O(1) | O(n) |
| پشته | O(1) | O(1) | O(n) | O(n) | ||||
| صف | O(1) | O(1) | O(n) | O(n) | ||||
| لیست پیوندینامرتب | O(1) | O(1)[۱] | N/A | O(n) | O(n) | O(n) | O(n) | O(n) |
| لیست پیوندی مرتب | O(n) | O(1)[۱] | N/A | O(n) | O(n) | O(1) | O(1) | O(n) |
| فهرست پرشی | ||||||||
| درخت جستجوی دودویی خود-متوازن | O(log n) | O(log n) | O(log n) | N/A | O(log n) | O(log n) | O(log n) | O(n) |
| هیپ | O(log n) | O(log n) | O(log n) | N/A | O(n) | O(1) برای هیپ کمینه، O(n) برای هیپ بیشینه[۲] | O(1) برای هیپ بیشینه، O(n) برای هیپ کمینه[۲] | O(n) |
| جدول درهمسازی | O(1) | O(1) | O(n) | N/A | O(1) | O(n) | O(n) | O(n) |
| تری (k = میانگین طول کلید) | O(k) | O(k) | N/A | O(k) | O(k) | O(k) | O(k) | O(k n) |
| درخت دکارتی | ||||||||
| درخت B | O(log n) | O(log n) | O(log n) | N/A | O(log n) | O(log n) | O(log n) | O(n) |
| درخت سرخ-سیاه | O(log n) | O(log n) | O(log n) | O(n) | ||||
| درخت گسترده | ||||||||
| درخت AVL | O(\log n) | |||||||
| درخت k-بعدی |
در برخی منابع، درج (insert) در یک آرایه نامرتب، به صورت O(n) بیان میشود؛ زیرا فرض بر این است که عنصر جدید باید در یک موقعیت خاص از آرایه قرار گیرد که این کار مستلزم جابهجایی تمامی عناصر بعدی به اندازهٔ یک خانه است. اما در یک آرایهٔ کلاسیک، آرایه برای نگهداری عناصر دلخواه و نامرتب استفاده میشود و محل دقیق هر عنصر اهمیتی ندارد؛ بنابراین درج معمولاً با افزایش اندازهٔ آرایه به اندازهٔ یک و قراردادن عنصر جدید در انتهای آرایه انجام میشود که این، عملیات O(1) است.[۳] در برخی منابع انگلیسی برای حالت درج در آرایهٔ نامرتب دو حالت بیان شده است که بسته به نوع پیادهسازی تفاوت دارد. جهت توضیح بیشتر به یادداشتهای جدول مراجعه شود.[۴]
همچنین، عملیات حذف (delete) گاهی به صورت O(n) بیان میشود، چرا که ممکن است فرض شود بعد از حذف باید عناصر بعدی جابهجا شوند. ولی در آرایهٔ نامرتب کلاسیک، ترتیب عناصر اهمیتی ندارد (هرچند عناصر بهطور ضمنی به ترتیب زمان درج مرتباند)، لذا حذف میتواند با جابهجایی عنصر مورد نظر با آخرین عنصر آرایه و سپس کاهش اندازهٔ آرایه به اندازهٔ یک انجام شود که این هم O(1) است.[۵]
این جدول صرفاً یک خلاصه تقریبی است؛ برای هر ساختار داده، حالتها و گونههای خاصی وجود دارد که ممکن است هزینهها را تغییر دهد. همچنین، با ترکیب دو یا چند ساختار داده میتوان به هزینههای کمتری رسید.
پانویس
[ویرایش]- 1 2 3 توماس اچ. کورمن، چارلز ای. لیزرسون و رونالد ال. ری وست (۱۹۹۰). مقدمه ای بر الگوریتمها. دپارتمان علوم و فناوری اطلاعات کالج پناستیت. شابک ۹۷۸−۰−۲۶۲−۵۳۰۹۱−۰
الگوریتم LIST-DELETE در زمان O(1) اجرا میشود؛ اما اگر فقط کلیدِ یک عنصر را داشته باشیم و بخواهیم آن را حذف کنیم، در بدترین حالت زمان Θ(n) لازم است، زیرا ابتدا باید تابع LIST-SEARCH را اجرا کنیم. - 1 2 3 توماس اچ. کورمن، چارلز ای. لیزرسون، رونالد ال. ری وست (۱۹۹۰). مقدمه ای بر الگوریتمها. دپارتمان علوم و فناوری اطلاعات کالج پناستیت. شابک ۹۷۸−۰−۲۶۲−۵۳۰۹۱−۰.
دو نوع هیپ دودویی وجود دارد: max-heap (هیپ بیشینه) و min-heap (هیپ کمینه). در هر دو نوع، مقادیر موجود در گرهها خاصیت هیپ را ارضا میکنند؛ بهطوریکه در هیپ بیشینه، بزرگترین عنصر در ریشه (root) قرار دارد و در هیپ کمینه، کوچکترین عنصر در ریشه است. عمل HEAP-MAXIMUM (در هیپ بیشینه) مقدار بیشینه را با بازگرداندن مقدار A[1] در زمان Θ(1)، و HEAP-MINIMUM (در هیپ کمینه) مقدار کمینه را به همین روش و با همان پیچیدگی زمانی بازمیگرداند. - 1 2 Allen Sherrod (2007). Data Structures and Algorithms for Game Developers. Cengage Learning. شابک ۹۷۸−۱−۵۸۴۵۰−۶۶۳−۸. درج یک عضو جدید در آرایهٔ نامرتب، تنها نیازمند قرار دادن عضو جدید در انتهای لیست است و به هیچ کار اضافهای نیاز ندارد؛ بنابراین درج در آرایهٔ نامرتب دارای پیچیدگی زمانی O(1) است.
- 1 2 Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. شابک ۹۷۸−۰−۲۶۲−۵۳۰۹۱−۰.
- 1 2 Algorithm - the time complexity of deletion in a unsorted array. پیدا کردن یک مقدار خاص در آرایهٔ نامرتب دارای پیچیدگی خطی O(n) است، اما خود حذف (پس از پیدا کردن)، در زمان ثابت انجام میشود: ابتدا عنصر مورد نظر را با عنصر انتهایی آرایه جابجا کرده، سپس اندازه آرایه را یک واحد کاهش میدهیم.