Home / Veri Yapıları / İkili Ağaç Özellikleri

İkili Ağaç Özellikleri

Bir önceki yazımızda ikili ağaçlara giriş yapmıştık. Şimdi İkili Ağaç özelliklerini inceleyelim. İkili ağaçlar en fazla iki tane child node sahip olabildikleri için bir takım özel kurallara sahip olurlar.

1- l. Level’daki toplam düğüm sayısı 2l-1  kadardır

Örneğin root yani kök düğümün Level’ı 1’dir. n = 1 dersek 2^(1-1) = 1 olur. Zaten kök düğümünün yalnızca bir tane düğüm olabileceğinden bu formülün doğruluğunu da görmüş oluruz.

2- Bir ağaçtaki toplam yüksekliğe h dersek maksimum düğüm sayısı  2h – 1 olur.

Yaprak düğümlerin (leaf – en alttaki çocuğu olmayan düğümlerin) yüksekliği 1 kabul edilir. Yükseklik 2’nin kuvvetleri cinsinden artar. Bazı kitaplarda en altın yüksekliği 0 kabul edilir. Bu durumlarda formül 2h+1 – 1 olur.

3- N adet düğümden oluşan bir ikili ağacın tahmini yüksekliği Log2(N+1) olur.

Bu formülü direkt 2 numaralı maddeden çıkarıyoruz. Eğer yaprak düğümlere 1 yerine 0 değeri verseydik formül ⌈ Log2(N+1) ⌉ – 1 olurdu.

4- L Adet yaprağı (Leaf) bulunan bir ağacın ⌈ Log2L ⌉ + 1 level (Derece) değerindedir

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir