İkili Arama Ağaçları Nedir?

İkili Arama Ağaçları (BST), her düğümün en fazla iki çocuğa sahip olduğu ve sol alt ağacındaki tüm düğümlerin anahtar değerinin, anahtar değerinden küçük olduğu, sağ alt ağacındaki tüm düğümlerin anahtar değerinin ise anahtar değerinden büyük olduğu özel bir ikili ağaç veri yapısıdır.

Kısa cevap

İkili Arama Ağaçları, elemanları sıralı bir şekilde tutarak arama, ekleme ve silme işlemlerini ortalama O(log n) sürede gerçekleştiren bir veri yapısıdır.

Adım adım çözümlü örnekler

Aşağıdaki sayıları sırasıyla bir İkili Arama Ağacına ekleyerek ağacın son halini gösteriniz: 50, 30, 70, 20, 40, 60, 80

1. 50 kök düğüm olur.
2. 30, 50'den küçük olduğu için soluna eklenir.
3. 70, 50'den büyük olduğu için sağına eklenir.
4. 20, 50'den küçük, 30'dan küçük olduğu için 30'un soluna eklenir.
5. 40, 50'den küçük, 30'dan büyük olduğu için 30'un sağına eklenir.
6. 60, 50'den büyük, 70'den küçük olduğu için 70'in soluna eklenir.
7. 80, 50'den büyük, 70'den büyük olduğu için 70'in sağına eklenir.
Sonuç: Kök: 50, Sol: 30 (Sol: 20, Sağ: 40), Sağ: 70 (Sol: 60, Sağ: 80)

İkili Arama Ağacında 40 sayısını arayınız.

1. Kökten (50) başlanır. 40 < 50, sola gidilir.
2. Mevcut düğüm 30'dur. 40 > 30, sağa gidilir.
3. Mevcut düğüm 40'dır. Aranan sayı bulundu.

Bilgi kartları

Mini test

S1.Aşağıdaki İkili Arama Ağacı'nda 70 sayısını aramak için hangi yolu izlersiniz?

Doğru cevap: B. 70, 50'den büyük olduğu için sağa gidilir. Mevcut düğüm 70'dir. Aranan sayı bulundu.

S2.Bir İkili Arama Ağacı'nda en küçük eleman nerede bulunur?

Doğru cevap: C. Ağacın en soluna doğru ilerledikçe değerler küçülür ve en soldaki yaprak en küçük elemanı temsil eder.

S3.Aşağıdaki sayılardan hangisi 50 değerinden sonra BST'ye eklenirse ağaç dengesizleşme eğiliminde olur? (Önceki örnekteki ağaç yapısını düşünün)

Doğru cevap: C. 65 sayısı, 50'den büyük ve 70'den küçük olduğu için 70'in soluna eklenir. Mevcut ağaç yapısında 70'in solunda zaten 60 olduğu için 65, 70'in soluna eklendiğinde ağaç dengesizleşmez. Ancak, eğer sürekli olarak kökten büyük sayılar eklenirse (örneğin 60, 70, 80, 90...), ağaç tek taraflı uzayarak (sağa doğru) dengesizleşir.

📄Bu konuyu PDF çalışma kağıdı olarak indirKonu özeti + 10 soru + cevap anahtarı — sınıfta paylaş, yazdır.↓

Sık yapılan hatalar

✗

BST'de sol düğüm her zaman sağ düğümden küçüktür. — Doğrusu: BST'de sol alt ağacındaki tüm düğümlerin anahtar değeri, anahtar değerinden küçüktür; sağ alt ağacındaki tüm düğümlerin anahtar değeri ise anahtar değerinden büyüktür.

✗

BST'de arama işlemi her zaman O(log n) sürer. — Doğrusu: BST'de arama işlemi, ağaç dengeli ise ortalama O(log n) sürer, ancak ağaç dengesiz ise en kötü durumda O(n) sürebilir.

Sıkça sorulan sorular

İkili Arama Ağacı (BST) nedir?

Her düğümün en fazla iki çocuğa sahip olduğu ve düğüm değerlerinin belirli bir düzene göre sıralandığı bir ağaç veri yapısıdır. Sol alt ağacındaki tüm değerler anahtar değerinden küçük, sağ alt ağacındaki tüm değerler ise anahtardan büyüktür.

BST'nin avantajları nelerdir?

Elemanları sıralı tutması sayesinde arama, ekleme ve silme işlemlerini ortalama O(log n) sürede gerçekleştirebilir. Bu, listeler gibi veri yapılarına göre daha verimlidir.

BST'nin dezavantajları nelerdir?

Ağacın dengesiz olması durumunda (örneğin, elemanlar sıralı olarak eklenirse) performans O(n)'e düşebilir. Dengeyi korumak için AVL ağaçları veya Kırmızı-Siyah ağaçları gibi daha gelişmiş veri yapıları gerekebilir.

İlgili konular