एक बाइनरी सर्च ट्री एक बाइनरी ट्री है जिसमें एक क्रमबद्ध अपरिवर्तनीय है : प्रत्येक नोड के लिए, इसके बाएं उप-वृक्ष में सभी कुंजियां छोटी होती हैं, और इसके दाएं उप-वृक्ष में सभी कुंजियां बड़ी होती हैं। यह आपको प्रत्येक चरण पर समस्या को आधा करके खोज करने देता है।
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
| ऑपरेशन | संतुलित | सबसे खराब (अपमानित) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
सबसे खराब स्थिति तब होती है जब कुंजियों को क्रमबद्ध क्रम में सम्मिलित किया जाता है — ट्री ऊंचाई n की एक लिंक्ड सूची में अपमानित हो जाता है।
BST आपको क्रमबद्ध, गतिशील डेटा देते हैं जिसमें लॉगरिदमिक ऑपरेशन होते हैं — डेटाबेस इंडेक्स और क्रमबद्ध मैप का वैचारिक पूर्वज।
अपमान समस्या स्व-संतुलन वृक्षों को प्रेरित करती है, साक्षात्कार में एक मुख्य अनुवर्ती विषय।