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

## [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.


---

İlk ve son karakteri 'X', arasındaki tüm karakterlerin 'Y' olduğu karakter dizilerine mükemmelkelime diyeceğiz. Mükemmel-kelimenin içerisindeki 'Y' harflerinin sayısı kelimenin mükemmellik derecesini göstermektedir. Örneğin 'XYYYX', 3. dereceden mükemmel-kelime iken;
'XYYYYYX', 5. dereceden mükemmel-kelimedir.
Mükemmel-cümle; mükemmel-kelimelerden şu şekilde oluşturulmaktadır:
- 1. dereceden mükemmel-kelime 1. dereceden mükemmel-cümle'dir.
- n. dereceden mükemmel-cümle; n. dereceden mükemmel-kelimenin sağına ve soluna (n - 1). dereceden mükemmel-cümlenin gelmesi ile oluşturulmaktadır.
Örneğin "XYXXYYXXYX", 2. dereceden mükemmel-cümledir. 3. dereceden mükemmelcümle ise "XYXXYYXXYXXYXYXXYYXXYYXXYYXXYX" dir. Sonsuz dereceli mükemmel-cümle için aşağıdakilerden hangileri doğrudur?
I) 50. harf 'Y' dir.
II) 55. harf 'Y' dir.
III) 60. harf 'X' dir.
IV) 70. harf 'X' dir.

Şıklar:
A) I ve II | B) I ve III | C) II ve IV | D) III ve IV | E) Hiçbiri

Cevap: C II ve IV

Çözüm:
f(x)'e x. dereceden mükemmel-cümlenin uzunluğu diyelim. x. dereceden mükemmel kelime x+2 harfden oluştuğundan:
- f(1) = 3
- f(2) = f(1) + 4 + f(1) = 3 + 4 + 3 = 10
- f(3) = f(2) + 5 + f(2) = 10 + 5 + 10 = 25
- f(4) = f(3) + 6 + f(3) = 25 + 6 + 25 = 56
- f(5) = f(4) + 7 + f(4) = 56 + 7 + 56 = 119
diyebiliriz.
g(x, n)'e de n. dereceden mükemmel-cümlenin x. harfi diyelim. Bu fonksiyonu şöyle parçalara bölebiliriz:
\[g(x, n) = \begin{cases} g(x, n-1), & x < f(n-1) + 1 \\ x = f(n-1) + 1, & x = f(n-1) + n + 2 \\ g(x-n-2-f(n-1), n-1), & x > f(n-1) + n + 2 \end{cases}\]
Yani her n için f(n-1)+1 ve f(n-1)+n+2 değerleri g(x, n)'i bulmada yardımcı olur. Bu değerler:
- n=5 → 57 ve 63
- n=4 → 26 ve 31
- n=3 → 11 ve 15
- n=2 → 4 ve 7'dir
Bizim bulmamızı x'den büyük en küçük f(n) değerine sahip n için g(x, n) değeri, bize x. harfin ne olduğunu verir. O zaman:
- g(50, 4) = g(19, 3) = g(4, 2) = 'X'. Yanlış
- g(55, 4) = g(24, 3) = g(9, 2) = g(2, 1) = 'Y'. Doğru
- g(60, 5) = 'Y' (57 ile 63 arasında). Yanlış
- g(70, 5) = g(7, 4) = g(7, 3) = g(7, 2) = 'X'. Doğru