BST kuralı

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.

Örnek çözümü göster

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))

Kendini test et

BST'de sol alt ağaç değerleri nasıldır?
- Düğümden büyük
- Düğümden küçük
- Eşit
- Rastgele
Cevabı göster

Düğümden küçük — Düğümden küçük

Arama yönü

if target ____node.val: go left

Cevabı göster

if target <node.val: go left

BST kuralı: kavramları eşleştir

Sol alt

Küçükler
Sağ alt

Büyükler
Inorder

Artan sıra
Dengeli

O(log n)

Sıradaki ders: BST ekleme

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler