একটি বাইনারি সার্চ ট্রি একটি বাইনারি ট্রি যার একটি অর্ডারিং ইনভেরিয়েন্ট রয়েছে: প্রতিটি নোডের জন্য, এর বাম সাবট্রির সমস্ত কী ছোট, এবং এর ডান সাবট্রির সমস্ত কী বড়। এটি আপনাকে প্রতিটি ধাপে সমস্যাকে অর্ধেক করে সার্চ করতে দেয়।
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
| অপারেশন | ব্যালেন্সড | সর্বনিম্ন (ডিজেনারেট) |
|---|---|---|
| সার্চ | O(log n) | O(n) |
| ইনসার্ট | O(log n) | O(n) |
| ডিলিট | O(log n) | O(n) |
সর্বনিম্ন কেস ঘটে যখন কী সর্টেড অর্ডারে ইনসার্ট করা হয় — ট্রি উচ্চতা n এর একটি লিংকড লিস্টে ডিজেনারেট হয়ে যায়।
BST আপনাকে লগারিদমিক অপারেশন সহ সর্টেড, ডায়নামিক ডেটা দেয় — ডাটাবেস ইনডেক্স এবং অর্ডারড ম্যাপের কনসেপ্টুয়াল পূর্বপুরুষ।
ডিজেনারেশন সমস্যা সেলফ-ব্যালেন্সিং ট্রি অনুপ্রাণিত করে, যা ইন্টারভিউতে একটি মূল ফলো-আপ টপিক।