موضوع مقاله: ساختار داده جستجو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ساختار داده جستجو | مقدمه: در علوم کامپیوتر، یک ساختار داده جستجو (به انگلیسی: Search Data Structure) نوعی ساختمان داده‌ها است که امکان بازیابی کارآمد آیتم‌های خاص را از مجموعه‌ای از آیتم‌ها فراهم می‌کند؛ مانند بازیابی یک رکورد یا ساختار (علم کامپیوتر) مشخص از یک پایگاه داده. | ## بخش 1: ساختار داده جستجو | ساده‌ترین، عمومی‌ترین و در عین حال ناکارآمدترین ساختار دادهٔ جستجو، تنها یک فهرست ترتیبی نامرتب از همهٔ اعضاست. یافتن عضو مورد نظر در چنین فهرستی، با استفاده از روش جستجوی خطی، ناگزیر به تعداد عملیاتی متناسب با تعداد اعضا (n) نیاز دارد؛ چه در بدترین حالت و چه در حالت متوسط. ساختارهای دادهٔ جستجوی مفیدتر، امکان بازیابی سریع‌تر را فراهم می‌کنند؛ با این حال، تنها به انواع خاصی از جستجو محدود هستند. افزون بر این، از آنجا که هزینهٔ ساخت این ساختارها دست‌کم متناسب با n است، استفاده از آن‌ها فقط زمانی مقرون‌به‌صرفه خواهد بود که قرار باشد چندین جستجو روی یک پایگاه داده (یا پایگاه داده‌ای که بین دو جستجو تغییر چندانی نمی‌کند) انجام شود. ساختارهای دادهٔ جستجوی ایستا برای پاسخ‌دهی به تعداد زیادی درخواست (کوئری) بر روی یک پایگاه داده ثابت طراحی شده‌اند؛ درحالی‌که ساختارهای پویا امکان درج، حذف یا به‌روزرسانی داده‌ها را میان درخواست‌های متوالی فراهم می‌کنند. در حالت پویا، باید هزینهٔ اصلاح ساختار جستجو برای سازگار شدن با تغییرات پایگاه داده را نیز مدنظر قرار داد. رده‌بندی ساده‌ترین نوع کوئری این است که یک رکورد را بیابیم که مقدار یک فیلد خاص (یعنی کلید) آن برابر با مقدار معینی (v) باشد. | ## بخش 2: ساختار داده جستجو | انواع رایج دیگر کوئری عبارت‌اند از: «یافتن عضوی با کمترین (یا بیشترین) مقدار کلید»، «یافتن رکوردی با بیشترین مقدار کلید که از v بزرگ‌تر نباشد»، و «یافتن تمام اعضایی که مقدار کلید آن‌ها بین دو حد مشخص vmin و vmax باشد». در برخی از پایگاه داده‌ها، مقادیر کلید ممکن است نقاطی در یک (فضای چندبعدی) باشند. برای مثال، کلید می‌تواند یک موقعیت جغرافیایی (مانند عرض جغرافیایی و طول جغرافیایی) بر روی زمین باشد. در این حالت، انواع رایج کوئری‌ها عبارتند از: «یافتن رکوردی با کلیدی که نزدیک‌ترین به یک نقطهٔ معین v باشد»، یا «یافتن همهٔ آیتم‌هایی که کلید آن‌ها در فاصلهٔ مشخصی از v قرار دارد»، یا «یافتن همهٔ آیتم‌ها در یک ناحیهٔ معین R از این فضا». یک حالت خاص رایج از گونهٔ اخیر، کوئری‌های بازه‌ای همزمان روی دو یا چند کلید ساده است؛ برای مثال: «یافتن همهٔ رکوردهای کارمندان با حقوق بین ۵۰٬۰۰۰ تا ۱۰۰٬۰۰۰ و تاریخ استخدام بین سال‌های ۱۹۹۵ تا ۲۰۰۷». یک مورد خاص رایج از حالت دوم، کوئری‌های دامنه همزمان روی دو یا چند کلید ساده است؛ مانند «یافتن تمام رکوردهای کارمندان با حقوق بین ۵۰٬۰۰۰ و ۱۰۰٬۰۰۰ و استخدام بین سال‌های ۱۹۹۵ و ۲۰۰۷». اما در یک آرایهٔ کلاسیک، آرایه برای نگهداری عناصر دلخواه و نامرتب استفاده می‌شود و محل دقیق هر عنصر اهمیتی ندارد؛ بنابراین درج معمولاً با افزایش اندازهٔ آرایه به اندازهٔ یک و قراردادن عنصر جدید در انتهای آرایه انجام می‌شود که این، عملیات است. | ## بخش 3: ساختار داده جستجو | همچنین، عملیات حذف (delete) گاهی به صورت بیان می‌شود، چرا که ممکن است فرض شود بعد از حذف باید عناصر بعدی جابه‌جا شوند. ولی در آرایهٔ نامرتب کلاسیک، ترتیب عناصر اهمیتی ندارد (هرچند عناصر به‌طور ضمنی به ترتیب زمان درج مرتب‌اند)، لذا حذف می‌تواند با جابه‌جایی عنصر مورد نظر با آخرین عنصر آرایه و سپس کاهش اندازهٔ آرایه به اندازهٔ یک انجام شود که این هم است. این جدول صرفاً یک خلاصه تقریبی است؛ برای هر ساختار داده، حالت‌ها و گونه‌های خاصی وجود دارد که ممکن است هزینه‌ها را تغییر دهد. در هر دو نوع، مقادیر موجود در گره‌ها خاصیت هیپ را ارضا می‌کنند؛ به‌طوری‌که در هیپ بیشینه، بزرگ‌ترین عنصر در ریشه (root) قرار دارد و در هیپ کمینه، کوچک‌ترین عنصر در ریشه است. درج یک عضو جدید در آرایهٔ نامرتب، تنها نیازمند قرار دادن عضو جدید در انتهای لیست است و به هیچ کار اضافه‌ای نیاز ندارد؛ بنابراین درج در آرایهٔ نامرتب دارای پیچیدگی زمانی است.Thomas H. | ## جمع‌بندی | پیدا کردن یک مقدار خاص در آرایهٔ نامرتب دارای پیچیدگی خطی است، اما خود حذف (پس از پیدا کردن)، در زمان ثابت انجام می‌شود: ابتدا عنصر مورد نظر را با عنصر انتهایی آرایه جابجا کرده، سپس اندازه آرایه را یک واحد کاهش می‌دهیم.