5 Türlü İkili Ağacın Açıklanması [Çizimlerle]

Bilgisayar biliminde, çeşitli veri yapıları, verilerin farklı biçimlerde düzenlenmesine yardımcı olur. Bunlar arasında ağaçlar, hiyerarşik bir ağaç yapısını simüle eden yaygın olarak kullanılan soyut veri yapılarıdır. Bir ağacın genellikle bir kök değeri ve alt düğümleri tarafından üst düğümlerinden oluşturulan alt ağaçları vardır. Ağaçlar doğrusal olmayan veri yapılarıdır.

Genel bir ağaç veri yapısı, tutabileceği alt düğüm sayısı konusunda herhangi bir sınırlamaya sahip değildir. Ancak, ikili ağaçta durum böyle değildir. Bu makale, belirli bir ağaç veri yapısı - ikili ağaç ve ikili ağaç türleri hakkında bilgi edinecektir .

İkili Ağaç Veri Yapısı Nedir?

İkili ağaç , her ebeveyn için en fazla iki çocuğu olan ağaç tipi doğrusal olmayan bir veri yapısıdır . İkili ağaçtaki her düğümün , veri öğesiyle birlikte bir sol ve sağ referansı vardır. Bir ağacın hiyerarşisinin en üstündeki düğüme kök düğüm denir. Diğer alt düğümleri tutan düğümler, ana düğümlerdir.

Bir üst düğümün iki alt düğümü vardır: sol alt ve sağ alt. Hashing, ağ trafiği için veri yönlendirme, veri sıkıştırma, ikili yığınlar hazırlama ve ikili arama ağaçları ikili ağaç kullanan uygulamalardan bazılarıdır.

İkili Ağaçlar ve İkili Ağaç Türleri ile ilgili Terminolojiler

• Düğüm: Bir ağaçtaki bir sonlandırma noktasını temsil eder.
• Kök: Bir ağacın en üstteki düğümü.
• Ebeveyn: Kendi başına en az bir alt düğümü olan bir ağaçtaki (kök dışında) her düğüme ebeveyn düğüm denir.
• Çocuk: Kökten uzaklaşırken doğrudan bir ana düğümden gelen bir düğüm, alt düğümdür.
• Yaprak Düğümü: Bunlar harici düğümlerdir. Onlar çocuğu olmayan düğümlerdir.
• Dahili Düğüm: Adından da anlaşılacağı gibi, bunlar en az bir çocuğu olan iç düğümlerdir.
• Ağacın Derinliği: Ağacın düğümünden köke kadar olan kenar sayısıdır.
• Ağacın Yüksekliği: Düğümden en derin yaprağa kadar olan kenar sayısıdır. Ağacın yüksekliği de kök yüksekliği olarak kabul edilir.

Artık ikili ağaç ve ikili ağaç türleri ile ilgili terminolojilere aşina olduğunuza göre, ikili ağaç bileşenlerini anlamanın zamanı geldi . İkili yapı ve bileşenler hakkında derinlemesine bilgi edinmek için veri bilimi kurslarımıza göz atın.

İkili Ağaç Bileşenleri

Üç ikili ağaç bileşeni vardır . Her ikili ağaç düğümü, kendisiyle ilişkilendirilmiş bu üç bileşene sahiptir. Bu üç ikili ağaç bileşenini anlamak, programcılar için temel bir kavram haline gelir:

1. veri öğesi
2. Sol alt ağaca işaretçi
3. Sağ alt ağaca işaretçi

Kaynak

Bu üç ikili ağaç bileşeni bir düğümü temsil eder. Veriler ortada bulunur. Sol işaretçi, sol alt ağacı oluşturan alt düğümü işaret eder. Sağdaki işaretçi, sağdaki alt düğümü göstererek sağ alt ağacı oluşturur.

Okuyun: Veri Bilimi için En İyi Tahmin Soruları ve Bilgilendirici Yöntemler

İkili Ağaç Türleri

Çeşitli ikili ağaç türleri vardır ve bu ikili ağaç türlerinin her birinin kendine has özellikleri vardır. İşte ikili ağaç türlerinin her biri ayrıntılı olarak:

1. Tam İkili Ağaç

Sıfır çocuğu veya iki çocuğu olan özel bir ikili ağaç türüdür. Bu, o ikili ağaçtaki tüm düğümlerin ya kendi üst düğümünün iki alt düğümüne sahip olması gerektiği ya da ana düğümün kendisinin yaprak düğüm veya dış düğüm olduğu anlamına gelir.

Diğer bir deyişle, tam ikili ağaç, harici düğüm dışındaki her düğümün iki çocuğu olduğu benzersiz bir ikili ağaçtır. Tek bir çocuğu tuttuğunda, böyle bir ikili ağaç tam bir ikili ağaç olmayacaktır. Burada yaprak düğüm sayısı, iç düğüm sayısı artı bire eşittir. Denklem, L=I+1 gibidir; burada L, yaprak düğümlerinin sayısıdır ve I, iç düğümlerin sayısıdır.

İşte tam bir ikili ağacın yapısı:

2. İkili Ağacı Tamamlayın

Tam bir ikili ağaç, ağacın en alt seviyesi hariç, tüm ağaç seviyelerinin tamamen düğümlerle doldurulduğu başka bir özel ikili ağaç türüdür. Ayrıca, bu ikili ağacın son veya en alt seviyesinde, her düğüm muhtemelen sol tarafta bulunmalıdır. İşte tam bir ikili ağacın yapısı:

3. Mükemmel İkili Ağaç

Tüm iç düğümlerin kesinlikle iki çocuğu varsa ve her dış veya yaprak düğüm bir ağaç içinde aynı düzeyde veya aynı derinlikteyse, ikili ağacın 'mükemmel' olduğu söylenir. Yüksekliği 'h' olan mükemmel bir ikili ağacın 2h – 1 düğümü vardır. İşte mükemmel bir ikili ağacın yapısı:

4. Dengeli İkili Ağaç

Ağaç yüksekliği O(logN) ise, bir ikili ağacın 'dengeli' olduğu söylenir, burada 'N' düğüm sayısıdır. Dengeli bir ikili ağaçta, her düğümün sol ve sağ alt ağaçlarının yüksekliği en fazla bir tane değişmelidir. Bir AVL Ağacı ve bir Kırmızı-Siyah Ağaç, dengeli bir ikili arama ağacı oluşturabilen bazı yaygın veri yapısı örnekleridir. İşte dengeli bir ikili ağaç örneği:

5. Dejenere İkili Ağaç

Her dahili düğümün yalnızca tek bir çocuğu varsa, ikili ağacın dejenere ikili ağaç veya patolojik ikili ağaç olduğu söylenir. Bu tür ağaçlar, performans açısından bağlantılı bir listeye benzer. İşte dejenere bir ikili ağaç örneği:

İkili Ağacın Faydaları

• İkili ağaçta arama işlemi diğer ağaçlara göre daha hızlıdır.
• Öğeleri sıralı bir şekilde sağlamak için yalnızca iki geçiş yeterlidir
• Maksimum ve minimum öğeleri almak kolaydır
• Grafik geçişi ayrıca ikili ağaçlar kullanır
• İkili ağaçlar kullanılarak farklı postfix ve önek ifadelerinin dönüştürülmesi mümkündür

Ayrıca Okuyun: Makine Öğreniminde Karar Ağaçları: İşlevler, Sınıflandırma, Artıları ve Eksileri

Çözüm

İkili ağaç, veri yapısında en yaygın olarak kullanılan ağaçlardan biridir. İkili ağaç türlerinin her birinin kendine has özellikleri vardır. Bu veri yapılarının uygulamalı bilgisayar biliminde özel gereksinimleri vardır. İkili ağaç türleri hakkındaki bu makalenin yardımcı olduğunu umuyoruz. upGrad, veri bilimi, makine öğrenimi, büyük veri ve daha pek çok konuda çeşitli kurslar sunar.

Veri bilimi hakkında bilgi edinmek istiyorsanız, IIIT-B & upGrad'ın çalışan profesyoneller için oluşturulmuş ve 10'dan fazla vaka çalışması ve proje, uygulamalı uygulamalı atölye çalışmaları, endüstri uzmanlarıyla mentorluk, 1 Endüstri danışmanlarıyla bire bir, en iyi firmalarla 400+ saat öğrenim ve iş yardımı.