BST arama

Değeri O(log n) ortalamada aramayı öğrenirsin.

BST arama

BST'de arama, ikili arama mantığıyla yapılır. Hedef kökten küçükse sol alt ağaca, büyükse sağ alt ağaca bakılır. None'a ulaşılırsa değer yoktur.

Her adımda arama alanı yarıya iner; dengeli BST'de O(log n). Bu, sıralı dizide ikili aramayla aynı mantıktır.

BST'nin avantajı: ekleme ve silme de aynı hızda yapılır; diziye göre esnektir.

Arama maliyeti

Dengeli BST'de arama O(log n)'dir çünkü her adımda arama alanı yarıya iner. Bu, sıralı dizide ikili arama ile aynıdır.

Ancak dengesiz BST (ör. sıralı veri eklenirse) zincir gibi olur ve arama O(n)'e düşer. Bu yüzden dengeleme önemli.

AVL veya kırmızı-siyah ağaçlar otomatik denge sağlar; böylece arama her zaman O(log n) kalır.

Uygulama BST arama

search(node, target) yaz. Küçükse sol, büyükse sağ, eşitse True, None ise False. root = Node(5); root.left = Node(3); print(search(root, 3)) ile True yazdır.

Örnek çözümü göster

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def search(node, target):
    # BST'de ara
    if node is None:
        return False
    if node.val == target:
        return True
    if target < node.val:
        return search(node.left, target)
    return search(node.right, target)
root = Node(5)
root.left = Node(3)
print(search(root, 3))

Kendini test et

BST arama: kavramları eşleştir

Küçük

Sol
Büyük

Sağ
Eşit

Bulundu
None

Yok
Dengesiz BST'de arama maliyeti?
- O(1)
- O(n^2)
- O(log n)
- O(n)
Cevabı göster

O(n) — O(n)

Bulundu

if node.val == target: return ____

Cevabı göster

if node.val == target: return True

Sıradaki ders: Özet - BST

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler