İkili arama ağacı (BST) nedir ve işlem karmaşıklıkları nelerdir?

Question

Accepted Answer

**İkili arama ağacı**, bir sıralama değişmezine sahip olan ikili bir ağaçtır: her düğüm için, **sol alt ağacındaki tüm anahtarlar daha küçük**, ve **sağ alt ağacındaki tüm anahtarlar daha büyük**. Bu, her adımda sorunu yarıya indirerek arama yapmanızı sağlar.

## Değişmez

```text
        8
       / \
      3    10
     / \     \
    1   6     14     left < node < right at every node
```

## Arama ve ekleme

```python
def search(node, key):
    while node:
        if key == node.val: return node
        node = node.left if key < node.val else node.right  # go one way
    return None

def insert(node, key):
    if node is None: return Node(key)
    if key < node.val: node.left  = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node
```

## Karmaşıklık

| İşlem | Dengeli | En kötü durum (bozulmuş) |
|---|---|---|
| arama | O(log n) | O(n) |
| ekleme | O(log n) | O(n) |
| silme | O(log n) | O(n) |

**En kötü durum**, anahtarlar sıralı sırayla eklendiğinde oluşur — ağaç, yüksekliği `n` olan bağlantılı bir listeye dönüşür.

## Dengeler

- **Güçlü yanları:** sıralı ağaç geçişi O(n)'de; aralık sorguları ve halef/öncül destekler.
- **Zayıf yanları:** kendi başına denge garantisi yoktur — O(log n)'de kalmak için AVL veya red-black çeşidi gereklidir.

## Neden önemli

BST'ler size sıralı, dinamik veri ve logaritmik işlemler sağlar — veritabanı endeksleri ve sıralı haritaların kavramsal öncülü.

Bozulma sorunu, mülakatlarda önemli bir devam konusu olan **kendinden dengeli ağaçlar**a ilham verir.