Bilgisayar Olimpiyatı 2017, 1. Aşama, Soru 13

## [13 – 15] Sorular İçin Açıklama
2–3 dengeli ağacının aşağıdaki özelliklere sahip olduğu bilinmektedir;
Ö1: Ağaçtaki her düğüm en az 1. en çok 2 eleman içerir.
Ö2: Aynı düğümdeki elemanlar soldan sağa, küçükten büyüğe doğru yerleştirilir.
Ö3: Ağacın en alt seviyesindeki düğümler yaprak düğüm olarak isimlendirilir. Yaprak düğümlerin çocukları (altlarında düğüm) yoktur.
Ö4: Yaprak düğümlerin dışındaki bütün düğümlerin en az 2 (sol, sağ), en çok 3 (sol, orta, sağ) çocuk düğümü vardır.
Ö5: Yaprak düğümlerin dışındaki herhangi bir düğümün sol, sağ ve varsa orta altağaçlarının yükseklikleri (altağacın en üstündeki ve en altındaki düğümlerin arasındaki seviye farkı) eşittir. Bu özellikleri nedeniyle bu yapı “dengeli ağaç” olarak isimlendirilir.
Ö6: Herhangi bir düğümdeki bir eleman; solundaki altağacın tüm elemanlarından büyük, sağındaki altağacın tüm elemanlarından küçüktür.
2–3 dengeli ağaca eleman ekleme işlemi en üstteki düğümden (kök düğüm) başlanarak aşağıdaki seviyelere doğru ilerlenerek gerçekleştirilir. Aşağıdaki şekilde sırasıyla 5, 18, 27, 14 ve 9 sayılarının eklenmesiyle oluşturulmuş bir 2–3 dengeli ağaç görülmektedir. İlk etapta 5 sayısı ağacın kök düğümüne yerleştirilmiştir. Ardından gelen 18 sayısı Ö1 ve Ö2 özelliklerine uygun olarak kök düğüme, 5’in sağına yerleştirilir. Sonrasında kök düğüme eklenen 27 sayısı Ö1 özelliğinin bozulmasına yol açtığından düzeltme işlemi yapılır ve 5, 18, 27 üçlüsünden ortanca olan 18 bir seviye yukarı taşınarak yeni kök düğüm ilan edilir. Ö6’ya uygun olarak; 5, 18’den küçük olduğundan sol altağacı ve 27, 18’den büyük olduğundan sağ altağacı oluşturur. 14 eklenirken 18’den küçük olduğundan sol altağaca; 5’in sağına eklenir. Aynı şekilde 9 da 18’den küçük olduğundan sol altağaca; 5‘in sağına, 14’ün soluna yerleştirilir ve Ö1 özelliğinin tekrar bozulduğu görülür. Yeriden bir düzeltme işlemi yapılarak 5, 9, 14 üçlüsünden ortanca olan 9 bir seviye yukarı taşınarak kök düğüme; 18’in soluna (Ö2 özelliği) yazılır. 5, 9’dan küçük olduğu için sol altağacı; 14, 9’dan büyük, 18’den küçük olduğu için orta altağacı; 27, 18’den büyük olduğu için sağ altağacı oluşturur.
[GÖRSEL]
Şeklin sonunda görünen beş elemanlı 2–3 dengeli ağaç iki seviyeden oluşmaktadır. Seviye0’da sırasıyla 9 ve 18 sayılarından oluşan kök düğüm; Seviye1’de ise sırasıyla 5, 14 ve 27 sayılarını içeren üç yaprak düğüm görülmektedir. Ağaca yeni elemanlar eklendikçe Seviye2, Seviye3, ... gibi yeni seviyeler oluşacaktır. Bu haliyle ağaç üzerinde yukarıdan aşağıya seviye-sıralı tarama işlemi uygulandığında sırasıyla Seviye0 ve Seviye1’deki elemanlardan oluşan 9, 18, 5, 14, 27 çıkış dizisi elde edilecektir. Aynı seviyede bulunan elemanlar soldan sağa doğru taranarak diziye eklenir. 2–3 dengeli ağacının yüksekliği ağacın toplam seviye sayısının bir eksiği olup şekildeki örnek için 1’e eşittir.

---

Yüksekliği 4 olan dengeli ağacın sahip olabileceği en çok ve en az eleman sayıları arasındaki fark kaçtır?

Şıklar:
A) 92 | B) 145 | C) 187 | D) 211 | E) 243

Cevap: D 211

Çözüm:
Yüksekliği 4 olan en az elemanlı dengeli ağaçta seviye O'da 1 eleman, seviye 1'de 1 elemana sahip onun 2 çocuğu, seviye 2'de 1 elemana sahip onların 4 çocuğu, ..., seviye 4'te 1 elemana sahip 16 yaprak düğüm vardır. Yani her seviyede 2 katına çıkacak şekilde toplamda 1 + 2 + 4 + 8 + 16 = 31 düğüm ve her birinin 1 elemanı vardır. Yüksekliği 4 olan en çok elemanlı dengeli ağaçta seviye O'da 2 elemanlı 1 düğüm, seviye 1'de ikişer elemana sahip onun 3 çocuğu, seviye 2'de ikişer elemana sahip onların 9 çocuğu, ..., seviye 4'te ikişer elemana sahip 81 yaprak düğüm vardır. Yani her seviyede 3 katına çıkacak şekilde toplamda 1 + 3 + 9 + 27 + 81 = 121 düğüm ve her birinin 2 elemanı vardır. O zaman toplam 242 elemanı vardır. Aralarındaki eleman farkı ise 242-31=211 olur.