Bilgisayar Olimpiyatı 2015, 1. Aşama, Soru 21

## [18 – 23] Sorular için Açıklama
İkili arama ağaçları, her bir düğümün en fazla iki çocuğunun (sol ve sağ) olduğu ağaçlardır.
Ayrıca ikili arama ağaçlarında her bir düğümdeki eleman; sol altağacındaki tüm elemanlardan büyük, sağ altağacındaki tüm elemanlardan da küçüktür. Bir düğüm ve onun altında (çocukları, çocuklarının çocukları, . .) yer alan tüm düğümlerin 
oluşturduğu ağaca o düğümden başlayan altağaç denilmektedir.
[GÖRSEL]
Yukarıdaki ağaçlar; ikili arama ağacına örnek olarak verilmiştir. Dikkat edilirse, her bir düğümdeki eleman bu düğümün kendisine bağlı sol altağacında bulunan tüm elemanlardan büyük, sağ altağacında bulunan tüm elemanlardan ise küçüktür. İkili arama ağacına yeni bir eleman eklenmek istenirse, en üstteki (kök) düğümden başlanılarak eklenmek istenilen elemana göre ağaç üzerinde sola ya da sağa doğru ilerlenir. Boş bir yer bulunduğunda ekleme işlemi yapılır. Örneğin; yukarıda (b)’deki ağaca 11 elemanı eklenmek istenirse (c)’deki ağaç elde edilmektedir.
Bir düğümün yüksekliği; kendi altağacındaki tüm düğümlerden en uzağındaki düğüme giderken, kendisi dahil, yol üzerinden geçilen düğüm sayısı olarak tanımlanmaktadır. Ağacın en tepesindeki (kök) düğümün yüksekliğine ise ağacın yüksekliği denilmektedir. Örneğin (b) şeklinde 22 elemanlı düğümün yüksekliği, kendi altağacında, en uzakta 16 elemanlı düğüm olduğu için 4’tür. 14 elemanlı düğümün yüksekliği ise 2, 16 elemanlı düğümün yüksekliği ise 1’dir. Bir ağaçta her bir düğümün sol çocuğunun yüksekliği ile sağ çocuğunun yüksekliği farkı -1, O veya 1 ise o ağaca dengeli ağaç denilmektedir. (a) numaralı şekildeki ağaç dengeli ağaçtır. (b) ve (c) numaralı şekillerde ise 22 numaralı düğümün sol çocuğunun yüksekliği 3 iken; sağ çocuğu olmadığından (boş ağaç) yüksekliği O’dır. Aradaki fark 3 olduğundan bu ağaçlar dengeli değildir.
[GÖRSEL]
İkili arama ağaçlarını dengeli hale getirmek için bazı düğümlere döndürme işlemi yapılmaktadır.
(d) numaralı şekilde Y elemanlı düğüme sağa döndürme işlemi yapılında (e) numaralı şekle dönüşmektedir. Benzer şekilde (e) numaralı şekilde X elemanlı düğüme sola döndürme işlemi yapıldığında (d) numaralı şekle dönüşmektedir. Bir düğüme, sağa veya sola döndürme işlemi yapıldığında, sadece kendisi, sol altağacı ve sağ altağacı döndürme işleminden etkilenir. Örneğin (d) numaralı şekilde X düğümüne döndürme işlemi uygulandığında; sadece T1, T2 ve X döndürme işleminden etkilenecektir.
(d) ve (e) numaralı şekillerde, T1, T2 ve T3 altağaçları temsil etmektedir.
Burada “T1'deki değerler < X < T2'deki değerler < Y < T3'teki değerler” şartı sağlanmaktadır.
Dengeli ikili arama ağacına eleman eklendiğinde eğer ağacın dengesi bozuluyorsa, dengeli ikili arama ağacı özelliğini korumak için çeşitli döndürme işlemleri yapılarak ağaç tekrar dengeli hale getirilir. Ağaç dengeli hale getirilirken “ikili arama ağacı” olma özelliğinin korunduğuna dikkat ediniz.


---

15 adet elemanı bulunan dengeli bir ikili arama ağacının yüksekliği en fazla kaç olur?

Şıklar:
A) 3 | B) 4 | C) 5 | D) 2 | E) 6

Cevap: C 5

Çözüm:
f(x) fonksiyonu x yüksekliğinde bir dengeli ağacı elde etmek için gereken en az eleman sayısı olsun.
f(1) = 1 ve f(2) = 2 olduğunu biliyoruz. Sonraki her x değeri için sol altağacının yüksekliği x-1 (x yüksekliğini sağlamak için), sağ alt ağacının derinliği x-2 olmalıdır (dengeli olduğu için daha az olamaz). Yani f(x) = f(x-1) + f(x-2) + 1 diyebiliriz. O zaman:
- f(3) = f(2) + f(1) + 1 = 2 + 1 + 1 = 4
- f(4) = f(3) + f(2) + 1 = 4 + 2 + 1 = 7
- f(5) = f(4) + f(3) + 1 = 7 + 4 + 1 = 12
- f(6) = f(5) + f(4) + 1 = 12 + 7 + 1 = 20
olur.
Yani 15 eleman ile en fazla 5 yüksekliğinde bir dengeli ağaç oluşturabiliriz.