Veri Yapısında 5 İkili Ağaç Türü Açıklandı

İkili ağaç, her düğümü en fazla 2 çocuk içeren, doğrusal olmayan bir ağaç veri yapısıdır. İkili ad 2 sayısını akla getirir, böylece herhangi bir ikili ağacın bir sol ve sağ çocuğu olabilir.

Bir işaretçi, genellikle ağacın kökü olarak bilinen en üstteki düğüme bir ikili ağacı gösterir. İkili ağaçtaki her düğüm veri, sol çocuğa bir işaretçi ve sağ çocuğa bir işaretçi içerir. İşaretçiler, bir ikili ağaç uygulamak için kullanılır. Kök işaretçi, ağaçtaki ilk düğümü gösterir. İkili bir ağaç oluşturmak için önce bir düğüm oluşturmanız gerekir.

Veri yapısında ikili ağacın ne olduğunu öğrendikten sonra , ikili ağaç üzerinde gerçekleştirilen temel işlemleri de bilmeniz gerekir.Bir öğe eklemek, bir öğeyi kaldırmak, bir öğeyi aramak ve ikili ağaçta gezinmek gibi işlevleri gerçekleştirebilirsiniz.

Veri yapısındaki herhangi bir ikili ağaç , hesaplamada iki farklı şekilde kullanılır.İlk olarak, her bir düğümle bağlantılı belirli etiketlere veya değerlere bağlı olarak düğümlere erişmek için kullanılırlar. İkincisi, ilgili bir dallanmış yapıya sahip veri temsilleri olarak kullanılırlar.

Çeşitliikili ağaç türlerini incelemeden önce , ikili ağaçtakullanılan terminolojileri tanıyalım .

Düğüm: İkili ağaçta bir veri değeri tutar.

Kök: Herhangi bir ikili ağaçta en üstteki düğüm, ağacın kökü olarak adlandırılır.

Boyut: İkili ağaçtaki düğüm sayısını gösterir.

Ebeveyn düğümü: Bir çocuğu olan ikili ağaçtaki bir düğüm.

Alt düğüm: İkili ağacın kökünden uzaklaşan bir üst düğümden kaynaklanan bir düğümdür.

Dahili düğüm: İkili ağaçta en az bir çocuğu olan düğümdür.

Yaprak düğüm: Çocuğu olmayan düğümdür.Alternatif olarak harici bir düğümdür.

Bir düğüm ağacının derinliği: Belirli bir düğüm bağlamında hesaplanır.Belirli bir düğümden köke kadar olan kenar sayısı olarak adlandırılır.

Bir ağacın iç yol uzunluğu: Bir ikili ağaçtaki her bir iç düğümün seviyelerinin toplamını ifade eder.

Bir ağacın dış yol uzunluğu: Bir ikili ağaçtaki her bir dış düğümün seviyelerinin toplamı olarak tanımlanır.

Bir ağaçtaki düğümün yüksekliği: Belirli bir düğümden ikili ağacın en derin yaprak düğümüne kadar olan kenar sayısıdır.Kökün yüksekliği her zaman ikili ağaçtaki diğer düğümlerden daha fazla olacaktır.

Şimdi 5çeşit ikili ağacın detaylarını inceleyelim .

İkili Ağaç Türleri

1. Tam İkili Ağaç

Veri yapısındaki bu ikili ağaç , -Uygun ikili ağaç ve Katı ikili ağaç adlarıyla da bilinir.Veri yapısındaki en temel ikili ağaç türlerinden biridir . Tam bir ikili ağaç, her düğümün iki çocuğu olması veya hiç çocuğu olmaması gereken bir ikili ağaç olarak tanımlanır.

Alternatif olarak, yaprak düğümler dışında her düğümün iki çocuktan oluştuğu ikili bir ağaç olarak karakterize edilir. Kök düğümün adresinin depolandığı düğümlere, kökün çocuk düğümleri denir. Çocuk içermeyen bu düğümlere yaprak düğümler denir.

Bir ağacın ikili ağaç olup olmadığını kontrol etmek için tüm düğümleri dolaşmanız gerekir. Herhangi bir düğümün bir çocuğu varsa, kod "Yanlış" döndürür. Tüm düğümlerin 0 veya 2 çocuğu varsa "True" döndürür.

İşte tam bir ikili ağacın özellikleri:

• Yaprak düğüm sayısı, iç düğüm sayısı + 1'e eşittir. Örneğin, iç düğüm sayısı 4 ise, yaprak düğüm sayısı 5'e eşittir.
• Bir ikili ağaçtaki maksimum düğüm sayısı ve düğüm sayısı eşittir. 2h+1 -1 olarak temsil edilir.
• Tam bir ikili ağaçtaki minimum düğüm sayısı 2h-1'dir.
• Tam bir ikili ağacın minimum yüksekliği log 2 (n+1) – 1'dir.
• Tam bir ikili ağacın maksimum yüksekliği h = (n+1)/2'dir.

2. Mükemmel İkili Ağaç

Mükemmel bir ikili ağaç , her düğümün 0 veya 2 çocuğa sahip olması gereken ve her yaprak düğümün seviyesinin aynı olması gerekenikili ağaç türlerinden biridir .Başka bir deyişle,veri yapısındaki mükemmel ikili ağaçlar, tüm iç düğümlerin iki dala sahip olduğu ve dalsız düğümlerin (yaprak düğümleri) aynı düzeyde bulunduğu ağaçlar olarak tanımlanır.

Bu bağlamda, bir düğümün seviyesi, kök düğümden olan mesafe veya yüksekliktir. Mükemmel bir ikili ağacı, son seviyenin de tamamen dolu olduğu tam bir ikili ağaç olarak düşünebilirsiniz.

Dünyanın en iyi Üniversitelerinden çevrimiçi olarakveri bilimi kurslarıöğrenin. Kariyerinizi hızlandırmak için Yönetici PG Programları, Gelişmiş Sertifika Programları veya Yüksek Lisans Programları kazanın.

3. Tam İkili Ağaç

Eksiksiz bir ikili ağaç , ağacın tüm seviyelerinin tamamen doldurulduğu veri yapısındaki ikili ağaç türlerinden biridir .İkili ağacın son seviyesi tamamen dolu olabilir veya olmayabilir. Ancak her düğüm, düğümün son seviyesinde en soldaki konumda bulunmalıdır. Düğümler soldan dahil edilmelidir.

Düğüm sayısı ile ağacın yüksekliği arasındaki en iyi oranı sundukları için temelikili ağaç türlerinden biridir .

Tam bir ikili ağacın temel özellikleri şunlardır:

• Maksimum düğüm sayısı 2 h+1 – 1'dir.
• Minimum düğüm sayısı 2 saattir .
• Minimum yükseklik log 2 (n+1) – 1'dir.

4. Dengeli İkili Ağaç

Dengeli ikili ağaçlarda, bir ağacın yüksekliği, toplam düğüm sayısının log 2'sidir . Ağacın yüksekliğinin h olduğunu ve ağacın toplam düğüm sayısının n olduğunu varsayalım. Yüksekliği hesaplamak için denklem h = log(n) şeklindedir. Sağ alt ağaç ile sol alt ağaç arasındaki maksimum yükseklik farkı "1" olmalıdır.

Fark, 0 ve -1 gibi başka değerlere sahip olabilir. Bu tür ikili ağaçlara AVL ağaçları da denir.Dengeli ikili ağaçların iyi bilinen örneklerinden biri Kırmızı-Siyah ağacıdır.

Dengeli bir ikili ağaç çalıştırmak için aşağıdaki kodu uygulayabilirsiniz.

özel sınıf Düğümü {

özel int değeri;

özel Düğüm kaldı;

özel Düğüm hakkı;

}

genel boole isBalanced(Düğüm n) {

eğer (dengeli ağaçYüksekliği(n) > -1)

doğru dönüş;

yanlış dönüş;

}

public int dengeliağaçYüksekliği(Düğüm n) {

eğer (n == boş)

0 dönüşü;

int h1 = dengeliağaçYüksekliği(n.sağ);

int h2 = dengeliağaçYüksekliği(n.sol);

eğer (h1 == -1 || h2 == -1)

-1 döndürür;

eğer (Math.abs(h1 – h2) > 1)

-1 döndürür;

eğer (h1 > h2)

h1 + 1'i döndürür;

h2 + 1'i döndürür;

}

ABD - Veri Bilimi Programlarımıza göz atın

5. Dejenere İkili Ağaç

Dejenere ikili ağaç, daha az kullanılanikili arama ağacı türlerinden biridir .Her düğümün yalnızca bir çocuğu olduğu, yani sol veya sağ çocuğu olan ikili bir ağaçtır. Hiçbir düğümün hem sol hem de sağ çocukları olmamalıdır.

Popüler ABD - Veri Bilimi Makalelerimizi okuyun

Çözüm

Çeşitli uygulamalar için kullanmak istiyorsanız,veri yapısında ikili ağacın ne olduğunu anlamak önemlidir .İkili ağaçlarda farklı işlevlerin uygulanması, verileri verimli bir şekilde düzenlemenize ve depolamanıza yardımcı olabilir.

Birden fazla ikili ağaç türünü incelemek, zaman karmaşıklığında işlemleri daha etkili bir şekilde gerçekleştirmenize yardımcı olur.İkili ağaç veri yapısı da dahil olmak üzere veri bilimi temelleri , veri bilimi yolculuğunuza kolayca başlamanıza yardımcı olur.Ardından, becerilerinizi ve portföyünüzü geliştirmek için gelişmiş veri bilimi projeleri üzerinde çalışabilirsiniz.

upGrad'da Makine Öğrenimi Yolculuğunuza Başlayın

Veri Bilimi öğrenmek istiyorsanız, upGrad'ın Veri Bilimi Yüksek Lisans programını takip edebilirsiniz. Bu 24 aylık kurs, Python, ML Modellerini Dağıt, Spark kullanarak BD işleme, Predictive Analytics & Statistics ve Denetimli ve Denetimsiz ML Modelleri gibi beceriler kazandırıyor. Kurs, hırslı yöneticiler, MBA mezunları, mühendisler ve çeşitli alanlardaki profesyoneller için uygundur.

Bu kursu tamamlamak, Veri Mühendisi, Büyük Veri Analisti, Makine Öğrenimi Mühendisi ve Veri Bilimcisi olarak çalışmanıza yardımcı olacaktır.