Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde kullanılan bir veri yapısı türüdür. Bu yapıda ağacın her elemanı binom dağılımındaki sayılar kadar çocuk düğüm (node) sahibi olur.

Daha basit bir tabirle her eklenen yeni düğüm ağacın o ana kadar olan bir kopyasıdır.

binomagaci

Yukarıdaki şekilde 5 farklı binom ağacı gösterilmiştir. İlk ağaçtan (B0) tek bir düğüm bulunmaktadır. İkinci ağaç olan B1 ağacının çocuğu, B0’ı içermelidir. Bu durumda B1 ağacı şekilde görüldüğü şekilde tek çocuklu olur.

B2 ağacında eklenen yeni çocuk ise B1’in tamamı olmalıdır.

Benzer şekilde B3 ağacında eklenen 3. çocuk B2 ağacının tamamı ve B4 olarak eklenen yeni ağaç ise B3’ün tamamından oluşmaktadır.

Bu özyineli (recursive) yapı aşağıdaki şekilde daha net görülmektedir:

binomagaciaciklama

Yukarıdaki şekilde kutu içerisine alınan alt ağaçlar (sub tree) bir önceki ağacın kopyası niteliğindedir.

Bu ağaca binom ağacı denmesinin sebebi ağaçtaki her seviyenin sayılarının binom dağılımı ile aynı olmasıdır.

binomtree_seviye

Yukarıdaki şekilde bu durum net olarak görülmektedir. Yani B4 ağacı binom dağılımındaki 4. terimi yada diğer bir ifadeyle binom üçgeninin 4. satırını göstermektedir.

Bir Cevap Yazın

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


iki + = 5