बायनरी सर्च ट्री हा एक बायनरी ट्री आहे ज्यामध्ये क्रमबद्ध अपरिवर्तनीय आहे: प्रत्येक नोडसाठी, त्याच्या डाव्या सबट्रीमधील सर्व की लहान आहेत, आणि त्याच्या उजव्या सबट्रीमधील सर्व की मोठी आहेत. हे आपल्याला प्रत्येक पायरीवर समस्या अर्धभाग करून शोधण्याची अनुमती देते.
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 आपल्याला लॉगरिदमिक ऑपरेशन्स असलेले क्रमबद्ध, गतिशील डेटा देते — डेटाबेस इंडेक्स आणि ऑर्डर केलेल्या नकाशांचा वैचारिक पूर्वज.
हास समस्या स्व-संतुलन ट्री ला प्रेरित करते, जे मुलाखत मधील मुख्य पाठ्य विषय आहे.