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

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

---

1'den 24'e kadar olan (24 hariç) tamsayılar küçükten büyüğe dengeli ağaca yerleştirildiğinde kök düğüm içeriği aşağıdakilerden hangisi olur?

Şıklar:
A) 8 | B) 8.12 | C) 12 | D) 8.16 | E) 12.16

Cevap: D 8.16

Çözüm:
1'den 24'e teker teker ekleyerek kökteki değişimi gözlemleyelim.
- 1 eklendiğinde kökteki eleman 1 olur.
- 2 eklendiğinde 1,2 olur.
- 3 eklendiğinde ortanca eleman yeni kökü oluştur ve kökteki eleman 2 olur.
- Yani biz elemanları her zaman en sağdaki düğüme ekleriz ve onun eleman sayısı 3 olduğunda ortancayı üst düğüme ekleriz. O yüzden kökün elemanlarını bilmemiz için her seviyedeki en sağdaki düğümün elemanlarını bilmemiz yeterli.
- Diğer düğümlerin, özellikler bozulmayacak şekilde yerleşebildiği bir ağaç düzeninin olduğunu gözlemleyebileceğimizden o ağaç şeklini bulmaya uğraşmamıza gerek yok. Şimdi kök ve alt seviyelerin en sağındaki düğümlerdeki değişimlere bakalım.
- 4 eklendiğinde 2 – 3 iken 2 – 3,4 şeklinde olur.
- 5 eklendiğinde 4 üste çıkar ve 2,4 – 5 şeklinde olur.
- 6,7 eklendiğinde ağaç şu aşamaları izler: 2,4 – 5,6,7  2,4,6 – 7  4 – 6 – 7.
- Şimdi yüksekliği 2 olan bir ağacı yükseltmek için 4 düğüm eklememiz gerektiğini öğrendik(4,5,6,7). İlk eklenen kök, 3.eklenen 1 sağı, 4.eklenen 2 sağı olur.
- O zaman 8,9,10,11 eklersek 4,8 – 10 – 11 şeklinde olur.
- Aynı şekilde 12,13,14,15 eklersek 4,8,12 – 14 – 15  8 – 12 – 14 – 15 olur.
- Biraz düşünmeyle her seviyeyi atlamak için 2 seviyenunarası kadar elemanın sağa eklenmesi gerektiğini anlayabiliriz.
- Yani 16,17,18,19,20,21,22,23 eklersek 8,16 – 20 – 22 – 23 elde ederiz(önceki durumlardan kök dışındaki düğümler için de kural bulunabilir.)
- 24'ü eklediğimizde cevap 8,16 kalır.
- Bu genel kural ile gidersek çok daha büyük sayılar için de cevap bulunabilir. 8 sayı sonra(32 için) kök 16 olur. 16 sayı sonra (48 için) 16, 32, 16 sonra(64 için) 32. Yani [2*+1-1,2*+1+2-1] için 2*,[2*+1+2-1,2*+1-1] için 2*,[2*+1 olur.