درخت جست‌وجوی دودویی
Binary Search Treeدر Binary Search Tree مقدارهای کوچک‌تر در زیر‌درخت چپ و مقدارهای بزرگ‌تر در زیر‌درخت راست قرار می‌گیرند؛ بنابراین درخت متعادل اجازه می‌دهد جست‌وجو هر بار فقط یک شاخه را ادامه دهد.
اول این مفهوم را در ذهن نگه دار
در Binary Search Tree مقدارهای کوچک‌تر در زیر‌درخت چپ و مقدارهای بزرگ‌تر در زیر‌درخت راست قرار می‌گیرند؛ بنابراین درخت متعادل اجازه می‌دهد جست‌وجو هر بار فقط یک شاخه را ادامه دهد.
چطور کار می‌کند؟ ساده و مرحله‌ای
مزیت BST به ارتفاع درخت وابسته است.
BST ساده ممکن است کاملاً کج شود و عملکرد به O(n) برسد؛ AVL و Red-Black برای کنترل ارتفاع ساخته شده‌اند.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
Invariant اصلی ساختار را مشخص کن.
مسیر read/update را در ساختار دنبال کن.
بعد از mutation قبل از return invariant را دوباره برقرار کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای درخت جست‌وجوی دودویی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
avg O(log n), worst O(n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی عملیات غالب برنامه با نقاط قوت این ساختار هماهنگ است از آن استفاده کن.
- علاوه بر Big-O، هزینه حافظه را هم مقایسه کن.
کجا معمولاً اشتباه می‌کنیم؟
- پیچیدگی را بدون فهم representation حفظ نکن.
- بدترین شکل ساختار یا هزینه resize/rebalance را نادیده نگیر.
مدل یک پاسخ حرفه‌ای
حتماً بگو O(log n) مربوط به حالت متعادل است. BST ساده در بدترین حالت برای search/insert/delete می‌تواند O(n) باشد.
درخت جست‌وجوی دودویی چه مسئله‌ای را حل می‌کند؟
در Binary Search Tree مقدارهای کوچک‌تر در زیر‌درخت چپ و مقدارهای بزرگ‌تر در زیر‌درخت راست قرار می‌گیرند؛ بنابراین درخت متعادل اجازه می‌دهد جست‌وجو هر بار فقط یک شاخه را ادامه دهد.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا avg O(log n), worst O(n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
پیچیدگی را بدون فهم representation حفظ نکن.