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

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


---

Yukarıda bir ikili arama ağacı gösterilmiştir. T1, T2, T3 ve T4 altagaçlarının yükseklikleri aynıdır. Haliyle Z düğümünün sol ve sağ altagaçlarının yükseklik farkı 2'dir. Bu ağacı dengeli hale getirmek için hangi işlem yapılmalıdır?

Şıklar:
A) Z düğümüne sağa döndürme işlemi yapılır. | B) Z düğümüne iki kere art arda sağa döndürme işlemi yapılır. | C) Önce Y düğümüne sola döndürme, sonra da Z düğümüne sağa döndürme işlemi yaplır. | D) Önce Y düğümüne sağa döndürme, sonra da Z düğümüne sola döndürme işlemi yapılır. | E) Hiçbiri

Cevap: C Önce Y düğümüne sola döndürme, sonra da Z düğümüne sağa döndürme işlemi yaplır.

Çözüm:
Ağacın dengeli olabilmesi için kök düğümün iki tarafında da eşit sayıda T olması gerekir. Kök düğümüne uygulanan sağa döndürme işleminde, yeni oluşacak olan sağ alt ağaçtaki T sayısı, eski kök düğümün sağ alt ağacı ve sol altagaçının sağ altagaçındaki toplam T sayısına eşittir. Dengeli ağaç oluşturabilmek için bu sayıyı 2 yapmamız gerekir. Z doğrudan sağa döndürülürse bu sayı 3 olur (X+1=3). O yüzden önce Y sol döndürülerek kökün sol altagaçının sağ altagaçındaki T sayını 1'e eşitlemek gerekir.