यहां हम कुछ सर्च ट्रीज और उनके अंतर देखेंगे। कई अलग-अलग सर्च ट्रीज हैं। वे प्रकृति में भिन्न हैं। बुनियादी सर्च ट्री बाइनरी सर्च ट्री (BST) है। कुछ अन्य सर्च ट्रीज AVL ट्री, B ट्री, रेड-ब्लैक ट्री, स्प्ले ट्री आदि हैं।
इन ट्रीज की तुलना उनके ऑपरेशन्स के आधार पर की जा सकती है। हम इन ट्रीज की समय जटिलता देखेंगे।
| सर्च ट्री | औसत केस | ||
|---|---|---|---|
| इन्सर्ट | डिलीट | सर्च | |
| बाइनरी सर्च ट्री | O(log n) | O(log n) | O(log n) |
| AVL ट्री | O(log₂ n) | O(log₂ n) | O(log₂ n) |
| B ट्री | O(log n) | O(log n) | O(log n) |
| रेड-ब्लैक ट्री | O(log n) | O(log n) | O(log n) |
| स्प्ले ट्री | O(log₂ n) | O(log₂ n) | O(log₂ n) |
| सर्च ट्री | वर्स्ट केस | ||
|---|---|---|---|
| इन्सर्ट | डिलीट | सर्च | |
| बाइनरी सर्च ट्री | O(n) | O(n) | O(n) |
| AVL ट्री | O(log₂ n) | O(log₂ n) | O(log₂ n) |
| B ट्री | O(log n) | O(log n) | O(log n) |
| रेड-ब्लैक ट्री | O(log n) | O(log n) | O(log n) |
| स्प्ले ट्री | O(log₂ n) | O(log₂ n) | O(log₂ n) |
