İ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 alt ağacındaki tüm elemanlardan büyük, sağ alt ağ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 alt ağaç denilmektedir.

İkili arama ağacında, bir düğümün sol ağırlığı, düğümdeki eleman ile sol alt düğümdeki elemanın toplamının yarısı olarak tanımlansın. Aynı şekilde düğümün sağ ağırlığı, düğümdeki eleman ile sağ alt düğümdeki elemanın toplamının yarısı olarak tanımlansın. Mesela (a) ağacındaki 12 düğümünün sol ağırlığı, 12 düğümü ile sol alt düğümü 8 in toplamının yarısı olan 10’dur. Sol alt düğümü olmayan düğümün sol ağırlığı, üzerinde yazan sayının yarısı olsun. Sağ alt düğümü olmayan düğümün sağ ağırlığı benzer şekilde tanımlansın. Mesela (b) ağacında 14 düğümünün sol ağırlığı 7, sağ ağırlığı (14+15):2=14,5 tir.

Bir ikili arama ağacının tüm ağırlıkların toplamı ağacın yükü olarak tanımlansın. Mesela (a) ağacının yükü 10+7+12,5+9,5+6+11+13=69 dur.

Bir ikili arama ağacında tüm sol ağırlıklar toplamı, tüm sağ ağırlıklar toplamına eşit ise bu ağaca homojen ağırlıklı ağaç olarak tanımlansın.

Bir düğümün yüksekliği; kendi alt ağacındaki tüm düğümlerden en uzak düğüme giderken, kendisi ve en uzak düğüm dâhil, yol üzerinde geçilen düğüm sayısı olarak tanımlansın. Ağacın en tepesindeki (kök) düğümün yüksekliğine ise ağacın yüksekliği olarak tanımlansın.

Düğümün sol gerilimi, düğümdeki eleman ile sol alt düğümdeki elemanın toplamı olarak tanımlansın. Aynı şekilde düğümün sağ gerilimi, düğümdeki eleman ile sağ alt düğümdeki elemanın toplamı olarak tanımlansın. Mesela (a) ağacındaki 12 düğümünün sol gerilimi, 12 düğümü ile sol alt düğümü 8’in toplamı olan 20’dir. Sol alt düğümü olmayan düğümün, sol gerilimi yoktur. Benzer şekilde sağ alt düğümü olmayan düğümün sağ gerilimi yoktur. Mesela (b) ağacında 14 düğümünün sol gerilimi yok, sağ gerilimi ise 14+15=29 dur.

Soru 1: 1,2,3,4,5,6,7,8,9 rakamları ile oluşturulabilecek en tepesindeki (kök) düğümü 5 olan ve yüksekliği en fazla olan ağacın yükü kaçtır?

Soru 2: (b) ağacına homojen ağırlıklı ağaç denilebilmesi için hangi düğümlerdeki sayılar değiştirilebilir? (Değiştirme işlemi her seferinde bir düğüm seçilip derecesi artırılarak ya da azaltılarak kademeli olarak yapılacak)

Sonraki soruları yukarıdaki ağaçlara göre çözünüz

Yukarıdaki ikili arama ağaçlarına göre sol veya sağ gerilimi (n) olan bir düğümden başlayan bir işlem, herhangi bir düğümün sol veya sağ gerilimi (n-1) ya da (n-2) olan başka bir ağacın düğümüne gidiyor. Sonra o ağaçtan da aynı kurala göre başka bir ağacın düğümüne gidiyor. 3 sayısına ulaşıldığı zaman işlem bitmiş oluyor.

Örneğin:
Örnek (IV) için 5 düğümünün sol gerilimi n=7’dir. Bu düğümden, sol gerilimi 6 olan örnek (II) deki 4 düğümüne veya sağ gerilimi 6 olan Örnek (III) teki 2 düğümüne gidilebilir. Bu şekilde işlem 6’dan 5’e veya 6’dan 4’e şeklinde devam edebilir. (Bir ikili arama ağacına birden fazla uğranabilir. Fakat art arda uğranamaz.)

Soru 3: Sol veya sağ gerilimi 8 olan bir ağaç üzerindeki düğümden başlayan bir işlem kaç farklı yolla oluşturulabilir?

Soru 4: Bir işlemdeki gerilimler sırasıyla 10-8-7-5-3 ise, bu işlem hangi ağaçlar olabilir?