Veri Yapısında İkili Ağaç: Özellikler, Türler, Temsil ve Yararlar

Farklı veri yapısı türleri arasında, diğer türlerin çoğundan daha fazla kullanıma sahip olan ikili ağaçlar bulunur. En dikkate değer uygulamaları arasında eşler arası programlama, arama, kriptografi, diğerlerinden daha yüksek bant genişliğine sahip ağ yönlendiricileri ve 3D video oyunları bulunur. Şimdi veri bilimindeki ikili ağaçların ne olduğunu, türlerinin neler olduğunu ve nasıl temsil edildiğini ayrıntılı olarak tartışacağız.

İkili ağaçlar nelerdir?

Daha önce normal ağaçlar üzerinde çalıştıysanız ve hatta temellerini biliyorsanız, bu ağaçlarda farklı düğümlerin sahip olmasına izin verilen çocuk sayısı söz konusu olduğunda herhangi bir kısıtlama olmadığını bilirsiniz. İkili ağaçlar bu anlamda biraz farklıdır. İkili ağaçlardaki her ebeveyn veya düğümün en fazla iki çocuğu olabilir.

İkili ağaçtaki tüm düğümlerin üç ana bileşeni vardır:

• bir veri öğesi
• doğru bir referans
• sol referans

Ağacın tepesinde bulunan düğüme kök düğüm denir. Ebeveyn düğümleri, çocukları olanlardır. Alt düğümler ve üst düğümler, referanslar aracılığıyla birbirine bağlanır. Çocuğu olmayan düğümlere yaprak düğümler denir.

İkili ağaçlardaki düğümlerin bir çocuğu, iki çocuğu olabileceği veya hiç çocuğu olmadığı açıktır. İkili ağaçlar kuyruklar, diziler, yığınlar ve bağlantılı listeler gibi doğrusal veri yapıları değildir. Bunun yerine hiyerarşik veri yapılarıdır.

Kontrol edin: Yeni Başlayanlar için Veri Bilimi Proje Fikirleri

İkili ağaçlardaki düğümlerin önemli özellikleri

Bu özelliklerin daha iyi anlaşılması, ikili ağaçlarla ilgili bu tartışmadan en iyi şekilde yararlanmanıza yardımcı olacaktır. Farklı düğümlerin derinliği, kökü belirli bir düğüme bağlayan yolda bulunan düğümlerin sayısı olarak tanımlanır. Bu nedenle kök düğümün derinliği 0'dır. Öte yandan, bir ikili ağaçtaki farklı düğümlerin yüksekliği, belirli bir düğümü kök düğüme bağlayan yolda bulunan düğümlerin sayısıdır. Bu nedenle yaprak düğümlerinin yüksekliği 0'dır.

Açıkça görebileceğiniz gibi, bir düğümün derinliği, kök düğümden başlayıp daha sonra o düğüme ulaşmak için aşağı inilerek ölçülür. Öte yandan, yüksekliği hesaplamaya gelince, söz konusu düğümden başlıyoruz ve ardından kök düğüme doğru yolculuk yapıyoruz. Her iki durumda da 0'dan başlıyoruz. Yüksekliği ve derinliği 0'dan değil 1'den ölçen insanlar da var, bu yanlış değil ve sadece farklı insanların tercih ettiği şey.

Şimdi bir düğümün maksimum derinliği, bir ikili ağacın derinliği olarak tanımlanır. Benzer şekilde, bir düğümün maksimum yüksekliği, bir ikili ağacın yüksekliği olarak tanımlanır. Yani bir ikili ağacın yüksekliği ve derinliği her zaman aynıdır.

Daha fazla bilgi edinin: Python'da Veri Yapıları ve Algoritma

İkili arama ağacı nedir?

İkili arama ağacı, diğer tüm ikili ağaç türleri arasında en yaygın olanıdır. Diğer herhangi bir ikili ağaç biçiminden farklı ve daha kullanışlı özelliklere sahip özel bir ikili ağaçtır. İkili arama ağacı veya BST tam olarak nedir? Adından da anlaşılacağı gibi, ağaçtaki verileri aramak için bir ikili arama ağacı kullanılır.

Bir BST, verimli aramaları kolaylaştırmasına izin veren özelliklerle birlikte gelir. BST, sırasıyla sağ alt ağaçtaki düğümlerden ve sol alt ağaçtaki düğümlerden daha küçük ve daha büyük olan düğüm anahtarına sahip olan bir ikili ağaçtır.

İkili ağaçların temsili

1. Bağlantılı temsil

Bağlantılı gösterimdeki ikili ağaçlar bellekte bağlantılı listeler olarak saklanır. Bu listeler, bitişik veya komşu bellek konumlarında depolanmayan ve ağaçlarla ilişkili ebeveyn-çocuk ilişkisi yoluyla birbirine bağlanan düğümlere sahiptir.

Bu gösterimde, her düğümün üç farklı bölümü vardır –

• sağ düğüme işaret eden işaretçi,
• sol düğümü işaret eden işaretçi,
• veri öğesi.

Bu daha yaygın temsilidir. Tüm ikili ağaçlar, kök düğümün yönünü gösteren bir kök işaretçiden oluşur. Null veya 0'a işaret eden bir kök düğüm gördüğünüzde, boş bir ikili ağaçla karşı karşıya olduğunuzu bilmelisiniz. Sağ ve sol işaretçiler, ağacın sağ ve sol alt öğelerinin adresini saklar.

2. Sıralı gösterim

Bağlantılı gösterimden daha basit olmasına rağmen, verimsizliği onu ikisinin daha az tercih edilen bir ikili ağaç gösterimi haline getirir. Verimsizlik, farklı ağaç elemanlarının depolanması için gereken alan miktarında yatmaktadır. Sıralı gösterim, ağaç öğelerinin depolanması için bir dizi kullanır.

Bir ikili ağacın sahip olduğu düğüm sayısı, kullanılan dizinin boyutunu tanımlar. İkili ağacın kök düğümü, dizinin ilk dizininde bulunur. Belirli bir düğümün depolandığı dizin, düğümün sağ ve sol alt öğelerinin depolanacağı dizinleri tanımlayacaktır. Boş bir ağacın ilk dizini olarak null veya 0 bulunur.

İkili ağaç türleri

1. Tam ikili ağaçlar: Tam ikili ağaçlar, düğümlerinin iki çocuğu olan veya hiç olmayan ikili ağaçlardır. Başka bir deyişle, bir ikili ağaç, yapraklar dışında tüm diğer düğümlerinin iki çocuğu olduğunda tam bir ikili ağaç olur.
2. Tam ikili ağaçlar: Tam ikili ağaçlar, tüm farklı seviyeleri tamamen dolu olanlardır. Bunun tek istisnası, anahtarları ağırlıklı olarak solda olan son seviyeleri olabilir. İkili bir yığın genellikle tam bir ikili ağaç örneği olarak alınır.
3. Mükemmel ikili ağaçlar: Mükemmel ikili ağaçlar, yaprakları aynı seviyede bulunan ve iç düğümleri iki çocuk taşıyan ikili ağaçlardır. Mükemmel bir ikili ağacın yaygın bir örneği, atalardan kalma bir soy ağacıdır.
4. Patolojik dejenere ikili ağaçlar: Dejenere ağaçlar, iç düğümlerinin bir çocuğu olan ikili ağaçlardır. Performans seviyeleri bağlantılı listelere benzer. İkili ağaç türleri hakkında daha fazla bilgi edinin.

Okuyun: R'de En Sık Kullanılan Altı Veri Yapısı

İkili ağaçların faydaları

1. Veri depolamanın hiyerarşik yolunu izlemenin ideal bir yolu
2. Verilen veri setinde var olan yapısal ilişkileri yansıtır.
3. Ekleme ve silme işlemlerini bağlantılı listelerden ve dizilerden daha hızlı yapın
4. Verileri tutmanın ve taşımanın esnek bir yolu
5. Mümkün olduğu kadar çok düğüm depolamak için kullanılır
6. Öğelere erişim söz konusu olduğunda bağlantılı listelerden daha hızlı ve dizilerden daha yavaştır.

Çözüm

Bu blogda, veri yapılarındaki ikili ağaçların ne olduğunu tartıştık ve türlerinden, temsillerinden ve faydalarından bahsettik. Ağaçların iki ana kullanımı, veri aramak ve depolamak içindir ve bu nedenle, Veri Bilimi ve ilgili alanların çalışmasının ayrılmaz bir parçasıdır.

Veri yapılarında, veri biliminde ikili ağaçlar hakkında bilgi edinmek istiyorsanız, IIIT-B & upGrad'ın çalışan profesyoneller için oluşturulan ve 10'dan fazla vaka çalışması ve proje, pratik uygulamalı atölye çalışmaları sunan Veri Biliminde Yönetici PG Programına göz atın. endüstri uzmanlarıyla mentorluk, endüstri danışmanlarıyla 1'e 1, en iyi firmalarla 400+ saat öğrenim ve iş yardımı.