BST da element qidirish

BST da qidiruv — Binary Search algoritmiga o'xshash. Har qadamda qidiruv maydoni yarmiga kamayadi.

Algoritm:

1. root None bo'lsa → topilmadi
2. Izlangan = root.data → topildi!
3. Izlangan < root.data → chapda qidirish
4. Izlangan > root.data → o'ngda qidirish

def qidirish(root, data):
    if root is None:
        return False
    if root.data == data:
        return True
    elif data < root.data:
        return qidirish(root.left, data)
    else:
        return qidirish(root.right, data)

Misol — 7 ni qidirish:

# BST: 10 → 5 → 15 → 3 → 7

# 7 < 10 → chapga (5 ga)
# 7 > 5  → o'ngga (7 ga)
# 7 == 7 → Topildi!  (faqat 3 qadam)

Ishlatamiz:

root = None
for x in [10, 5, 15, 3, 7]:
    root = kiritish(root, x)

print(qidirish(root, 7))   # True
print(qidirish(root, 4))   # False

Muhim qoidalar:

• BST qidirish O(log n) — har qadamda yarmi chetlanadi
• None ga yetilsa — element yo'q
• Binary Search kabi ishlaydi, lekin massiv emas, daraxt ustida

📝 Vazifa

BST da element qidirish

Sonlarni kiritib BST yarating, keyin qidiruv sonini kiriting. Topilsa "Topildi", topilmasa "Topilmadi" chiqaring.