BST ekleme
- Algoritmalar kursu
- Orta seviye
- Ders 30/80
- 4 dk
Yeni bir değeri kurala göre ağaca yerleştirmeyi öğrenirsin.
BST ekleme
BST'ye eleman eklerken özelliği koruruz: değer kökten küçükse sol alt ağaca, büyükse sağ alt ağaca recursive olarak eklenir. Boş düğüme ulaşılınca yeni düğüm oluşturulur.
Eklenen değer zaten varsa genellikle hiçbir şey yapılmaz (yinelenen yok) veya sağa eklenir. Bu seçim uygulamaya bağlıdır.
Ekleme O(log n) (dengeliyse); dengesizse O(n).
Yinelenenler
BST'de yinelenen değerleri nasıl ele alacağımız bir tasarım kararıdır. Yaygın üç yaklaşım vardır.
Birincisi: yinelenenleri reddet (en yaygın). İkincisi: sağ alt ağaca ekle (küçük veya eşit sağda). Üçüncüsü: düğümde bir sayaç tut.
Bu kursta yinelenenleri reddet yaklaşımını kullanacağız: eşit değer geldiğinde hiçbir şey yapma.
Uygulama BST ekleme
insert(node, val) yaz. Küçükse sol, büyükse sağ; None ise yeni düğüm. root = None; for v in [5,3,7]: root = insert(root, v); print(root.val, root.left.val, root.right.val) ile 5 3 7 yazdır.
Başlangıç kodu
def insert(node, val):
# BST'ye ekleÖrnek çözüm
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(node, val):
# BST'ye ekle
if node is None:
return Node(val)
if val < node.val:
node.left = insert(node.left, val)
elif val > node.val:
node.right = insert(node.right, val)
return node
root = None
for v in [5, 3, 7]:
root = insert(root, v)
print(root.val, root.left.val, root.right.val)Beklenen çıktı
5 3 7
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Ekleme yönü
if val < node.val:
node.left = insert(node.____, val)if val < node.val:
node.left = insert(node.left, val)Açıklama: left doğru.
2 BST ekleme: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Küçük |
Sola git |
Büyük |
Sağa git |
Eşit |
Dur |
Boş |
Yeni düğüm |
3 Ekleme ne kadar sürer (dengeli)?
- O(1)
- O(n)
- O(log n) Doğru cevap
- O(n^2)
Açıklama: O(log n)