BST arama
- Algoritmalar kursu
- Orta seviye
- Ders 31/80
- 4 dk
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.
Başlangıç kodu
def search(node, target):
# BST'de araÖrnek çözüm
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))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 BST arama: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Küçük |
Sol |
Büyük |
Sağ |
Eşit |
Bulundu |
None |
Yok |
2 Dengesiz BST'de arama maliyeti?
- O(1)
- O(n^2)
- O(log n)
- O(n) Doğru cevap
Açıklama: O(n)
3 Bulundu
if node.val == target: return ____if node.val == target: return TrueAçıklama: True doğru.