एक बाइनरी सर्च ट्री एक बाइनरी ट्री हो जसमा अर्डरिङ इनभेरियन्ट छ: प्रत्येक नोडको लागि, यसको बायाँ सबट्रीमा सबै कुञ्जीहरू सानो हुन्छन्, र यसको दायाँ सबट्रीमा सबै कुञ्जीहरू ठूलो हुन्छन्। यसले तपाइंलाई प्रत्येक पदमा समस्या आधा गरेर खोजन दिन्छ।
8
/ \
3 10
/ \ \
1 6 14 left < node < right at every node
def search(node, key):
while node:
if key == node.val: return node
node = node.left if key < node.val else node.right # go one way
return None
def insert(node, key):
if node is None: return Node(key)
if key < node.val: node.left = insert(node.left, key)
else: node.right = insert(node.right, key)
return node
| Operation | Balanced | Worst (degenerate) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
सबैभन्दा खराब केस तब हुन्छ जब कुञ्जीहरू क्रमबद्ध क्रममा घुसाइन्छन् — ट्री उचाइ n को लिङ्क गरिएको सूचिमा पतन हुन्छ।
BST हरूले तपाइंलाई अर्डर गरिएको, गतिशील डेटा logarithmic अपरेशनहरू सहित दिन्छन् — डाटाबेस इन्डेक्स र अर्डर गरिएको म्यापको सैद्धान्तिक पूर्वज।
डिजेनेरेशन समस्याले self-balancing trees को प्रेरणा दिन्छ, यो साक्षात्कारमा महत्त्वपूर्ण अनुवर्ती विषय हो।