درخت جستجوی دودویی (BST)
درخت جستجوی دودویی: قاعده چپ کوچک‌تر و راست بزرگ‌تر، جستجو و درج O(log n)، حذف و خطر درخت کج
BST چیست؟
درخت جستجوی دودویی (Binary Search Tree) درخت دودویی‌ای با یک قاعده طلایی برای هر گره:
- همه مقادیر زیردرخت چپ کوچک‌تر از مقدار گره
- همه مقادیر زیردرخت راست بزرگ‌تر از مقدار گره
این قاعده، جستجو را فوق‌العاده می‌کند: در هر گره، نیمی از داده را حذف می‌کنید — درخت متوازن: O(log n)!
جستجو در BST
برای پیدا کردن ۶۰ در درخت [۵۰، ۳۰، ۷۰، ۲۰، ۴۰، ۶۰، ۸۰]: از ریشه (۵۰) شروع → ۶۰ بزرگ‌تر است، برو راست (۷۰) → ۶۰ کوچک‌تر است، برو چپ (۶۰) ✓ — فقط ۳ مقایسه.
درج در BST
مثل جستجو پیش می‌رویم تا جایی که خالی پیدا شود و آنجا می‌گذاریم. درج هم O(log n) در درخت متوازن.
حذف در BST — سه حالت
- گره برگ: مستقیم حذف
- یک فرزند: فرزند جای والد را می‌گیرد
- دو فرزند: جایگزین = بزرگ‌ترین زیردرخت چپ (predecessor) یا کوچک‌ترین راست (successor)
Inorder = مرتب!
پیمایش inorder روی BST همیشه مقادیر را صعودی می‌دهد. این ویژگی برای تأیید درستی BST و تولید خروجی مرتب استفاده می‌شود.
خطر بزرگ: درخت کج!
اگر داده مرتب (مثلاً ۱، ۲، ۳، ۴، ۵) درج شود، BST به لیست پیوندی کج تبدیل می‌شود و همه عملیات O(n) می‌شوند!
| حالت درخت | جستجو/درج/حذف |
|---|---|
| متعادل | O(log n) ✓ |
| کج (بدترین) | O(n) ✗ |
راه‌حل: درخت‌های خودمتوازن‌شونده مثل AVL و Red-Black (مبحث بعدی) که بعد از هر درج/حذف، خودشان را متوازن می‌کنند.
مقایسه با جدول هش
| ویژگی | BST متوازن | جدول هش |
|---|---|---|
| جستجو/درج/حذف | O(log n) | O(1) میانگین |
| پیمایش مرتب | inorder طبیعی ✓ | نیاز به مرتب‌سازی |
| یافتن min/max | O(log n) ✓ | O(n) |
| حفظ ترتیب کلیدها | ✓ | خیر |
جمع‌بندی
- قاعده BST: چپ کوچک‌تر، راست بزرگ‌تر — برای همه گره‌ها
- درخت متوازن: جستجو/درج/حذف O(log n)
- inorder روی BST = خروجی مرتب صعودی
- داده مرتب = درخت کج = افت به O(n) ← نیاز به خودمتوازنی
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.