BST kuralı
- Algoritmalar kursu
- Orta seviye
- Ders 29/80
- 4 dk
Sol çocuk küçük, sağ çocuk büyük kuralıyla dizilen ikili arama ağacını öğrenirsin.
BST özelliği
İkili arama ağacı (binary search tree, BST), her düğümün sol alt ağacındaki tüm değerlerin düğüm değerinden küçük, sağ alt ağacındaki tüm değerlerin büyük olduğu bir ikili ağaçtır.
Bu özellik sayesinde arama, ekleme ve silme O(log n) olur (dengeliyse). Inorder dolaşım artan sıra verir.
BST, sıralı veri üzerinde hızlı arama için temel bir yapıdır. Dengesizse O(n)'e düşer.
BST özelliği
BST özelliği recursivetir: her alt ağaç da bir BST'dir. Sol alt ağacın tüm değerleri kökten küçük, sağ alt ağacın tüm değerleri kökten büyüktür.
Bu, aramada ikili arama mantığını uygular: hedef kökten küçükse sola, büyükse sağa gidilir. Her adımda arama alanı yarıya iner.
Dengeli BST'nin yüksekliği log n; her arama en çok bu kadar adımda biter.
Uygulama BST kontrolü
is_bst(node, lo, hi) yaz. Düğüm değeri (lo, hi) aralığında mı, recursive kontrol. root = Node(5); root.left = Node(3); print(is_bst(root, -9999, 9999)) ile True yazdır.
Başlangıç kodu
def is_bst(node, lo, hi):
# BST kontrolüÖrnek çözüm
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def is_bst(node, lo, hi):
# BST kontrolü
if node is None:
return True
if not (lo < node.val < hi):
return False
return is_bst(node.left, lo, node.val) and is_bst(node.right, node.val, hi)
root = Node(5)
root.left = Node(3)
print(is_bst(root, -9999, 9999))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 BST'de sol alt ağaç değerleri nasıldır?
- Düğümden büyük
- Düğümden küçük Doğru cevap
- Eşit
- Rastgele
Açıklama: Düğümden küçük
2 Arama yönü
if target ____node.val: go leftif target <node.val: go leftAçıklama: < doğru.
3 BST kuralı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Sol alt |
Küçükler |
Sağ alt |
Büyükler |
Inorder |
Artan sıra |
Dengeli |
O(log n) |