Binom Ağaçları (Binom Trees, Çift Termili Ağaçlar)

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.

« Haber (Predicate) | Boyer Moore Dizgi Arama Algoritması (Boyer-Moore String Search) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Binom Ağaçları (Binom Trees, Çift Termili Ağaçlar)' isimli yazı 18 May 2009 tarihinde, saat: 23:12 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 439 defa okunmuştur.

Benzer yazıları algoritma analizi (teory of algorithms), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar