Meydan okuma 2
- Algoritmalar kursu
- Orta seviye
- Ders 78/80
- 4 dk
BST'ye eleman ekleyip arama yaparsın.
Meydan okuma 2: BST
Bu meydan okumada BST'ye eleman ekleyip arama yapacaksın. Ağacı listelerle temsil edeceğiz.
Değerler: [5, 3, 7, 2, 4]. Arama: 4. Çıktı: True.
BST; sol daha küçük, sağ daha büyük ilkesiyle sıralı arama sağlar; ortalama O(log n).
Uygulama BST ekle ve ara
bst_search(tree, val) yaz. Ağaçta val var mı kontrol et. print(bst_search(build_bst([5, 3, 7, 2, 4]), 4)) ile True yazdır.
Başlangıç kodu
def bst_search(tree, val):
# BST araÖrnek çözüm
def bst_search(tree, val):
# BST ara
if tree is None:
return False
if tree[0] == val:
return True
if val < tree[0]:
return bst_search(tree[1], val)
return bst_search(tree[2], val)
def bst_insert(tree, val):
if tree is None:
return [val, None, None]
if val < tree[0]:
tree[1] = bst_insert(tree[1], val)
else:
tree[2] = bst_insert(tree[2], val)
return tree
def build_bst(values):
root = None
for v in values:
root = bst_insert(root, v)
return root
print(bst_search(build_bst([5, 3, 7, 2, 4]), 4))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Ağaç düğümü
Soru
[val, ____, right]
Cevap
[val, left, right]Açıklama: left doğru.
2 Meydan okuma 2: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
BST |
Sıralı ağaç |
left |
Daha küçük |
right |
Daha büyük |
search |
Arama |