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

## [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 “İlk” olarak verilen dengeli ikili arama ağacına 4 elemanı ekleniyor. Sonrasında ağacı dengeli hale getirmek için gerekli işlemler yapıldığında ağacın son hali yukarıdaki ağaçlardan hangisi olur?

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

Cevap: D IV

Çözüm:
4 elemanı 5'in soluna eklenir. 2'nin sağ altağacının derinliği solaltağacından 2 fazla olur ve 2 sola döndürülmesi gerekir. 2 sola döndürülmeden önce dengenin yeni ağaçta korunacağından emin olmak için 2'nin sağ altağacının sol altağacının derinliği 1 olmalıdır (2'nin sağı 6, onun solu 5, onun derinliği 2). Bunun için 6 sağa döndürülmelidir. 6 sağa dönerse, 2'nin sağı 5, onun solu 4, onun derinliği 1 olur ve 2'yi sola döndürüp dengeli ağacımızı oluşturabiliriz. Yani 2'nin sağ çocuğu 5, kök olur. 2, kökün sol çocuğu olur ve sağına 4 gelir. Kökün sağ çocuğu da 6 olur.