BST ekleme

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.

Örnek çözümü göster

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)

Kendini test et

Ekleme yönü

if val < node.val:
    node.left = insert(node.____, val)

Cevabı göster

if val < node.val:
    node.left = insert(node.left, val)

BST ekleme: kavramları eşleştir

Küçük

Sola git
Büyük

Sağa git
Eşit

Dur
Boş

Yeni düğüm
Ekleme ne kadar sürer (dengeli)?
- O(1)
- O(n)
- O(log n)
- O(n^2)
Cevabı göster

O(log n) — O(log n)

Sıradaki ders: BST arama

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler