এখানে আমরা কিছু সার্চ ট্রি এবং তাদের পার্থক্য দেখব। অনেক ধরণের সার্চ ট্রি রয়েছে। প্রাকৃতিকভাবে তারা ভিন্ন। বেসিক সার্চ ট্রি হল বাইনারি সার্চ ট্রি (BST)। অন্যান্য সার্চ ট্রি হল AVL ট্রি, B ট্রি, রেড-ব্ল্যাক ট্রি, স্প্লে ট্রি ইত্যাদি।
এই ট্রিগুলো তাদের অপারেশনসের ভিত্তিতে তুলনা করা যায়। আমরা এই ট্রিগুলোর টাইম কমপ্লেক্সিটি দেখব
| Search Tree | Average Case | ||
|---|---|---|---|
| Insert | Delete | Search | |
| Binary Search Tree | O(log n) | O(log n) | O(log n) |
| AVL tree | O(log₂ n) | O(log₂ n) | O(log₂ n) |
| B Tree | O(log n) | O(log n) | O(log n) |
| Red-Black Tree | O(log n) | O(log n) | O(log n) |
| Splay Tree | O(log₂ n) | O(log₂ n) | O(log₂ n) |
| Search Tree | Worst Case | ||
|---|---|---|---|
| Insert | Delete | Search | |
| Binary Search Tree | O(n) | O(n) | O(n) |
| AVL tree | O(log₂ n) | O(log₂ n) | O(log₂ n) |
| B Tree | O(log n) | O(log n) | O(log n) |
| Red-Black Tree | O(log n) | O(log n) | O(log n) |
| Splay Tree | O(log₂ n) | O(log₂ n) | O(log₂ n) |
