💻#سازنده_جهان_دیجیتال

7️⃣ ساختمان داده، قسمت هفتم

🔣درخت پیشوندی

🔴 درخت پیشوندی Trie که به آن (Prefix Tree) نیز می‌گویند، یک ساختار درخت مانند است که برای حل مسائل مرتبط با رشته‌ها (Strings) بسیار موثر است. این ساختمان داده امکان بازیابی سریع را فراهم می‌کند و اغلب برای جست‌و‌جوی کلمات در دیکشنری، پیشنهاد خودکار در موتورهای جست‌و‌جو و حتی مسیریابی IP یا  IP routing مورد استفاده قرار می‌گیرد.

🔴 در ادامه تصویری از چگونگی ذخیره‌سازی سه کلمه «thus» ،«top» و «their» در درخت پیشوندی نمایش داده شده است.

🔴 کلمات به صورت بالا به پایین در درخت پیشوندی ذخیره شده‌اند و گره‌های سبز رنگ s ،p و r نشانگر حروف پایانی در واژگان thus ،top و their هستند.

⬅️جدول درهم‌سازی

🟡درهم‌سازی (Hashing) فرآیند مورد استفاده برای شناسایی اشیا و ذخیره‌سازی هر شی در اندیس‌های یکتا از پیش محاسبه شده است که به آن‌ها «کلید» (key) گفته می‌شود. بنابراین، شی به شکل جفت کلید-مقدار (key-value) و مجموعه‌ای از چنین آیتم‌هایی که به آن دیکشنری گفته می‌شود ذخیره‌سازی می‌شود. هر شی با استفاده از آن کلید قابل جست‌و‌جو است.

🟡 ساختمان داده‌های متفاوتی بر پایه درهم‌سازی وجود دارند، اما پر استفاده‌ترین آن‌ها جدول درهم‌سازی است. جدول درهم‌سازی معمولا با استفاده از آرایه‌ها پیاده‌سازی می‌شود.

🟡 کارایی ساختمان داده درهم‌سازی بستگی به سه فاکتور زیر دارد:
• تابع درهم‌سازی (hash function)
• اندازه جدول درهم‌سازی
• روش مدیریت تصادم (Collision Handling Method)


#️⃣#IDSchools
#️⃣#IDS
#️⃣#IDS_Math

✉️@IDSchools
✉️@IDS_Math