# İkili Arama Ağacı

Adres: https://softwaredictionary.org/tr/terimler/binary-search-tree
Kategori: Veri Yapıları
Son güncelleme: 2026-09-30
İngilizcesi: Binary Search Tree
Okunuşu: baynıri sörç tri

Kısaca: İkili arama ağacı, her düğümün sol alt ağacında küçük, sağ alt ağacında büyük değerler bulunan ve hızlı sıralı aramaya olanak tanıyan bir ikili ağaçtır.

## İkili arama ağacı (binary search tree) nedir?

İkili arama ağacı (BST), her düğümün en fazla iki çocuğunun olduğu bir ikili ağaçtır ve bir sıralama kuralı vardır: bir düğümün sol alt ağacındaki her değer düğümün değerinden küçük, sağ alt ağacındaki her değer ise büyüktür. Kural yalnızca kökte değil, her düğümde geçerlidir. Aramayı hızlı yapan bu sıralamadır, çünkü her karşılaştırma ağacın tüm bir dalını görmezden gelmeniz gerektiğini söyler.

Aramak için kökten başlayıp hedef küçükse sola, büyükse sağa gidersiniz; değeri bulana ya da boş bir yere ulaşana kadar. Ekleme aynı yolu izler ve yeni düğümü o boş yere ekler. Arama, ekleme ve silme her biri O(h) sürer; h ağacın yüksekliğidir. Dengeli bir ağaçta yükseklik yaklaşık log2(n)'dir ve bu O(log n) verir; ancak değerler sıralı eklenirse ağaç uzun bir zincire dönüşür, h n'ye çıkar ve her işlem O(n)'e düşer.

Her yanıtın daha yüksek ya da daha düşük olduğu bir tahmin oyunu gibi çalışır: her adım bir dalın tamamını eler. AVL ağaçları ve kırmızı-siyah ağaçlar gibi kendi kendini dengeleyen BST'ler, ekleme ve silmelerden sonra küçük rotasyonlarla düğümleri yeniden düzenleyerek yüksekliği O(log n)'de tutar; Java'nın `TreeMap` ve C++'ın `std::map` gibi sıralı koleksiyonlarının arkasında dururlar. Sol alt ağacı, sonra düğümü, sonra sağ alt ağacı ziyaret eden in-order gezinme her değeri sıralı döndürür; bu da fiyatı 10 ile 20 arasında olan her şey gibi aralık sorgularını verimli kılar.

BST çoğu zaman komşularıyla karıştırılır. Sade bir ikili ağacın hiçbir sıralama kuralı yoktur; heap ise yalnızca ebeveynleri çocuklarına göre sıralar, bu da en küçüğü ya da en büyüğü tepede tutar ama rastgele değerler için hızlı aramayı desteklemez. Hash tablosuyla karşılaştırıldığında dengeli bir BST tam aramada daha yavaştır (O(log n)'e karşılık ortalamada O(1)), ancak hash tablosunun yapmadığı bir şeyi yapar: anahtarları sıralı tutar.

## Önemli noktalar

- Her düğümün sol alt ağacı küçük, sağ alt ağacı büyük değerler tutar.
- Arama, ekleme ve silme O(h) sürer; h ağacın yüksekliğidir.
- Dengeli bir BST'nin yüksekliği yaklaşık log n'dir, dolayısıyla işlemler O(log n)'dir; dejenere olan O(n)'dir.
- AVL ve kırmızı-siyah ağaçlar gibi kendi kendini dengeleyen türler O(log n) işlemleri garanti eder.
- In-order gezinme tüm değerleri O(n) sürede sıralı ziyaret eder.

## Örnek: Python'da bir ikili arama ağacında arama yapmak

```python
class Node:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def contains(node, target):  # O(h), where h is the height of the tree
    while node is not None and node.value != target:
        # Smaller targets can only be on the left, larger ones on the right
        node = node.left if target < node.value else node.right
    return node is not None

# Root 8: its left subtree (3, 1, 6) is smaller, its right subtree (10) is larger
root = Node(8, Node(3, Node(1), Node(6)), Node(10))
print(contains(root, 6))  # True: 8 -> 3 -> 6
print(contains(root, 7))  # False: 8 -> 3 -> 6 -> empty right child
```

## Sık sorulan sorular

**İkili arama ağacının zaman karmaşıklığı nedir?**

Arama, ekleme ve silme O(h) sürer; h ağacın yüksekliğidir. Ağaç dengeliyken bu O(log n)'dir, ancak ağaç örneğin değerler sıralı eklendikten sonra uzun bir zincire dönüştüğünde O(n)'e düşer.

**İkili ağaç ile ikili arama ağacı arasındaki fark nedir?**

İkili ağaç yalnızca her düğümü en fazla iki çocukla sınırlar. İkili arama ağacı, soldaki torunların küçük, sağdaki torunların büyük olması kuralını ekler; hızlı aramayı mümkün kılan da budur.

**Kendi kendini dengeleyen ikili arama ağacı nedir?**

Yüksekliğinin log n ile orantılı kalması için ekleme ve silmelerden sonra rotasyonlarla kendini otomatik olarak yeniden yapılandıran bir BST'dir. AVL ağaçları ve kırmızı-siyah ağaçlar en bilinen örneklerdir ve her ikisi de O(log n) arama, ekleme ve silme garanti eder.

---

Software Dictionary: https://softwaredictionary.org/tr · https://softwaredictionary.org/tr/llms.txt