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

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

---

Dengeli ağaca seviye-sıralı tarama uygulandığında 6, 3, 8, 1, 2, 4, 5, 7, 9 çıkış dizisi elde edilmektedir. Aşağıdakilerden hangisi bu dengeli ağaca eklenen elemanların sıralaması olabilir?

Şıklar:
A) 7, 1, 6, 8, 4, 2, 9, 3, 5 | B) 7, 3, 5, 1, 9, 6, 4, 8, 2 | C) 1, 3, 8, 6, 2, 5, 9, 4, 7 | D) 4, 8, 2, 1, 9, 3, 7, 5, 6 | E) Hiçbiri

Cevap: C 1, 3, 8, 6, 2, 5, 9, 4, 7

Çözüm:
1, 3, 8, 6, 2, 5, 9. 4, 7 sırasıyla eleman eklendiğinde ağacın seviye sıralı taraması sırayla:
• 1
• 13
• 318
• 3168
• 31268
• 361258
• 3612589
• 36124589
• 638124579
• Yani C şıklı olabilecek ekleme sıralarından biridir. Diğer hiçbir şık verilen çıkış dizisini elde edemez.