Açıklanan Veri Yapısındaki 4 Ağaç Türü: Özellikler ve Uygulamalar

Veri Yapısında Ağaç Nedir?

Ağaç, hiyerarşik verileri temsil eden bir veri yapısı türüdür. Kenarlarla birbirine bağlanan düğümlerden oluşan doğrusal olmayan bir yapıya sahiptir. Doğrusal bir veri yapısında işlemler gerçekleştiren diğer veri yapısı türleri arasında, veri boyutundaki artışla karmaşıklık artar. Ancak ağaç veri yapısı , doğrusal olmayan verilere daha hızlı erişim sağlar. Çeşitli veri yapılarının ve bunlarla ilişkili algoritmaların mevcudiyeti, görev performansının kolay ve verimli bir yolu haline gelmiştir.

Veri yapısındaki ağaçlarla ilgili birkaç terminoloji şunlardır:

• Düğüm : düğüm, bir anahtar veya değer içeren ve alt düğümlerine işaret eden bir ağaç veri yapısındaki bir varlıktır.
• Alt düğüm : Bir alt düğüm, herhangi bir düğümün alt öğesidir.
• Yaprak düğümler: Herhangi bir alt düğümü olmayan ve bir ağaçta en alttaki düğüm olan düğümler. Bunlara dış düğümler de denir.
• Kök : Ağacın en tepe noktasıdır.
• Dahili düğüm : En az bir alt düğüme sahip düğüm.
• Kenar: Kenar , bir ağaçtaki herhangi iki düğüm arasındaki bağlantıyı ifade eder.
• Bir düğümün yüksekliği: Düğümden en derin yaprağa kadar olan kenar sayısı.
• Bir düğümün derinliği : Kökten düğüme kadar olan kenarların sayısı.
• Bir ağacın yüksekliği : Kök düğümün yüksekliği.
• Bir düğümün derecesi : Bu düğümün toplam şube sayısı.
• Orman: Ayrık ağaçlar topluluğu.

ağaç türleri

1. İkili ağaç

İkili ağaç , her ana düğümün en fazla iki alt düğüme sahip olduğu bir tür ağaç veri yapısıdır . Adından da anlaşılacağı gibi, ikili iki anlamına gelir, bu nedenle her düğüm 0, 1 veya 2 düğüme sahip olabilir. Şekil 1'de bir ikili ağaç veri yapısı gösterilmektedir. Ağaçtaki Düğüm 1, her alt düğüm için bir tane olmak üzere iki işaretçi içerir. Düğüm 2'de yine iki alt düğüm için iki işaretçi bulunur. Düğüm 3, 5 ve 6 yaprak düğümlerdir ve bu nedenle hem sol hem de sağ kısımlarda boş göstericilere sahiptir.

Şekil 1: Bir ikili ağacın temsili ( https://www.javatpoint.com/binary-tree ).

İkili bir ağacın özellikleri

• Her I seviyesindeki maksimum düğüm sayısı 2 i'dir .
• Şekil 1'deki ağacın yüksekliği 3'tür, yani maksimum düğüm sayısı (1+2+4+8) =15 olacaktır.

• h yüksekliğinde, olası maksimum düğüm sayısı (20 + 21 + 22+….2h) = 2h+1 -1'dir.

• h yüksekliğinde, mümkün olan minimum düğüm sayısı h+1'e eşittir.

• Minimum sayıda düğüm, maksimum yüksekliğe sahip bir ağacı temsil eder ve bunun tersi de geçerlidir.

İkili ağaçlar bile aşağıdaki ağaç türlerine ayrılabilir:

• Tam İkili ağaç: Özel bir ikili ağaç türüdür. Bu ağaç veri yapısında, her bir üst düğüm veya bir dahili düğüm, ya iki çocuğa sahiptir ya da hiçbir alt düğüme sahip değildir.
• Mükemmel ikili ağaç: Bu tür ağaç veri yapısında , her dahili düğümün tam olarak iki alt düğümü vardır ve tüm yaprak düğümler aynı seviyededir.
• Tam ikili ağaç: Birkaç farkla tam ikili ağacınkine benzer.
• Her seviye tamamen doldurulur.
• Yaprak düğümleri ağacın soluna doğru eğilir.
• Son yaprak düğümünün doğru kardeşe sahip olması bir gereklilik değildir, yani tam bir ikili ağaç tam bir ikili ağaç olmak zorunda değildir.
• Dejenere veya Patolojik Ağaç: Bu ağaçların ana düğümün solunda veya sağında tek bir çocuğu vardır.
• Çarpık ikili ağaç: Ağacın sol düğümlerin veya sağ düğümlerin baskın olduğu patolojik veya dejenere bir ağaçtır. Bu nedenle, iki tür çarpık ikili ağaç vardır, yani sola çarpık veya sağa çarpık ikili ağaç.
• Dengeli ikili ağaç: Her düğüm için sol ve sağ alt ağacın yüksekliği arasındaki fark ya 0 ya da 1'dir.

2. İkili Arama Ağacı

Bu ağaç yapıları doğrusal değildir ve bir düğüm birkaç düğüme bağlıdır. Düğüm en fazla iki alt düğüme bağlanabilir. İkili arama ağacı olarak adlandırılır çünkü:

• Her düğümün en fazla iki alt düğümü vardır.
• 0(log(n)) zamanında bir öğeyi aramak için kullanılabilir ve bu nedenle arama ağacı olarak bilinir.

Şekil: İkili arama ağacına bir örnek ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

İkili arama ağacının özellikleri şunlardır:

• Sol alt ağacın tüm düğümlerindeki değer, kök düğümdeki değerden küçük olmalıdır.
• Sağ alt ağacın tüm düğümlerindeki değer, kök düğümdeki değerden daha büyük olmalıdır.

3. AVL Ağacı

AVL ağaçları, ikili bir ağacın türleri veya çeşitleridir. Hem ikili hem de ikili arama ağacından gelen özelliklerden oluşur. Adelson Velsky Lindas tarafından icat edilen bu ağaçlar kendi kendini dengeler, yani sol alt ağacın yüksekliği ve sağ alt ağaç dengelenir. Bu denge, bir dengeleme faktörü ile ölçülür.

Dengeleme faktörü:

• Sol alt ağaç ile sağ alt ağaç arasındaki farktır.
• Bir dengeleme faktörünün değeri 0, -1 veya 1 olmalıdır. Bu nedenle, bir AVL ağacının her düğümü bir dengeleme faktörü değerinden oluşmalıdır, yani 0, -1 veya 1.
• Denge Faktörü = (Sol Alt Ağacın Yüksekliği – Sağ Alt Ağacın Yüksekliği)
• Her düğümün denge faktörü -1 ile 1 arasındaysa, bir AVL ağacının dengeli bir ağaç olduğu söylenir.

Bir AVL ağacında -1'den 1'e kadar olan düğümlerin değerleri, dengelenmesi gereken dengesiz bir ağacı temsil edecektir.

• Bir düğümün denge faktörü 1'e sahipse, bu, sol alt ağacın sağ alt ağaçtan bir seviye daha yüksek olduğu anlamına gelir.
• Bir düğümün denge faktörü 0 ise, bu, sol alt ağaç ile sağ alt ağacın yüksekliğinin eşit olduğu anlamına gelir.
• Bir düğümün denge faktörü -1 ise, bu, sağ alt ağacın sol alt ağaçtan bir seviye yukarıda olduğu veya sol alt ağacın sağ alt ağaçtan bir seviye aşağıda olduğu anlamına gelir.

4. B-Ağacı

B Ağacı, ikili arama ağacının daha genelleştirilmiş bir şeklidir. Ayrıca, m'nin ağacın sırası olduğu, yüksekliği dengeli m yolu ağacı olarak da bilinir. Ağacın her düğümü birden fazla anahtara ve ikiden fazla alt düğüme sahip olabilir. İkili ağaç durumunda, yaprak düğümleri aynı seviyede olmayabilir. Ancak, bir B Ağacı durumunda, tüm yaprak düğümleri aynı seviyede olmalıdır.

Bir B ağacının özellikleri:

• Anahtarlar, her x düğümü için artan sırada saklanır.
• Her düğümde bir Boolean değeri "x.leaf" bulunur; bu, x bir yapraksa doğrudur.
• Dahili düğümler, en fazla "n-1" anahtara sahip olmalıdır, burada n, ağacın sırasıdır. Ayrıca her çocuk için bir işaretçi olmalıdır.
• Kök düğüm hariç tüm düğümlerin en fazla n çocuğu ve en az n/2 çocuğu olacaktır.
• Ağacın yaprak düğümleri aynı derinliğe sahiptir.
• Kök düğümün en az 1 anahtarı ve en az iki çocuğu olacaktır.
• n ≥ 1 ise, o zaman h yüksekliği ve minimum derece t ≥ 2 olan herhangi bir n-anahtar B-ağacı için, h ≥ logt (n+1)/2.

Uygulamalar

• İkili Arama ağacı, bir öğe kümesindeki bir öğeyi aramak için uygulanabilir.
• Yığın sıralama için yığın ağaçları kullanılır.
• Modern yönlendiriciler, yönlendirme bilgilerini depolamak için Tries adlı bir ağaç türü kullanır.
• B-Ağaçları ve T-Ağaçları çoğunlukla popüler veritabanları tarafından verilerini depolamak için kullanılır.
• Derleyiciler tarafından yazılan her programın sözdizimini doğrulamak için bir sözdizimi ağacı kullanılır.

Çözüm

Veri yapıları, kolay yönetim ve etkin kullanım için verileri depolamanın organize bir yolunu sağlar. Farklı veri türleri için çeşitli veri yapıları mevcuttur. Saklanması gereken veri türüne göre kullanıcı tarafından seçilir.

Ağaçlar, hiyerarşik veri türünün saklanabileceği bu tür veri yapılarının türleridir. Veriler, bazen alt düğümler olarak adlandırılan diğer düğümler için referansı depolayan düğümlerde depolanır.

Alt düğümlerin sayısına bağlı olarak, ağaçlar makalede belirtildiği gibi çeşitli türlere ayrılabilir. Ağaç türlerindeki düğümlerin düzenine bağlı olarak, her ağaç yapısı ilişkili özelliklere sahiptir. Farklı ağaç sınıfları tarafından gerçekleştirilebilen farklı işlem türleri ile bu tür veri yapısı, sıralama algoritmalarında ve veri depolamada uygulamalar bulmuştur.

UpGrad & IIIT-Bangalore tarafından düzenlenen Yazılım Geliştirmede Yönetici PG Programı – Tam Yığın Geliştirmede Uzmanlaşma, profilinizi geliştirmenize ve bir programcı olarak daha iyi istihdam fırsatları sağlamanıza yardımcı olabilir.