Önceki blogda, birkaç veri yapısından bahsettik. Şimdi ağaç veri yapıları ile devam edeceğiz ve veri yapıları konusunu bitireceğiz.
Şimdi ağaç veri yapısı ile başlayalım.
Ağaç Veri Yapısı
Ağaç veri yapısı önceki veri yapılarında belirttiğimiz gibi, birbirine bağlı düğümleri içeren ve ters çevrilmiş bir ağacı andıran bir veri yapısı türüdür. Bu yapıda, düğümlere yaprak ve düğümleri birbirine bağlayan kenar yapılara dallar denir. Ağaç yapısı döngüsüz veri yapısı olarak da bilinir.
Düğümler, ağaçta hiyerarşik bir yapı tanımlar. Bu hiyerarşik yapıya göre, üst dalı olmayan düğüme kök adı verilir. Buna karşılık, altta bir çocuk düğümü olmayan bir düğüme ise yaprak adı verilir. Bu iki düğüm arasındaki diğer düğümlere de aile(parent) düğümleri denir. Aile düğümleri ayrıca kendi aralarında da bir ağaç yapısı oluştururlar. Aynı ebeveyne sahip düğümler, birbirleriyle kardeş düğümlerdir.
Düğümlerdeki verilere erişmek ve onları işlemek için birkaç yöntem vardır, bu yollar belirli algoritmalar tarafından sağlanırlar:
Ön Tanımlı Seyahat
Kök — Sol alt ağaç — Sağ alt ağaç
Sıralı Seyahat
Sol alt ağaç — Kök — Sağ alt ağaç
Son Tanımlı Seyahat
Sol alt ağaç — Sağ alt ağaç — Kök
Hash Veri Yapısı
Hash(Karma) veri yapısı diğer veri yapılarından biraz farklıdır ve anlaşılması zordur. Açıklamak gerekirse; eklenecek olan verilerle dizinin boyutu mod olarak alınır. Kalan değer eklenecek olan verinin dizideki adresini belirtmiş olur. Bunun anlamı, “Dizide bir sayı arıyorsanız, sayıyı dizinin öğelerinin sayısına bölün ve aradığınız öğeyi dizinin o indeksine bakarak bulun.” anlamına gelir. Çok karmaşık görünebilir, ama şimdi bir örnekle gösterecek olursak;
13 boyutlu bir dizi için,
Eklenecek rakamlar 5, 9, 12, 18, 21, 27 olsun.
5%13 = 5
9%13 = 9
12%13 = 12
18%13 = 5
21%13 = 8
27%13 = 1
Yukarıdaki gibi diziye yerleştirilirler. Ouugghh… Fakat bir sorun var galiba?
1. ve 4. örnek sonuçları aynı yeri göstermektedir. Bu sorunu çözmek için çatışma sorunlarından kaçınma yöntemleri vardır.
Ayrı zincirleme
Böyle bir çatışma durumunda, bu düğüm liste yapısını alır ve değerler birbiri ardına yerleştirilir.
Sondaj açma
Bu yöntem ikiye ayrılır:
Doğrusal Sondaj
Bu yöntem, verileri çatışmanın gerçekleştiği düğümden hemen sonraki ilk boş düğüme yerleştirmeye çalışır.
Geometrik Sondaj
Doğrusal sondajdan tek fark şudur;
Düğümden sonraki düğüm doluysa, bir sonraki boş düğüm aranmaz, yalnızca düğümden sonraki sayıyı artırarak kareleri kareler ve o düğüme yerleştirir.
(x+1^2, x+2^2 , x+3^2 bunun gibi)
Grafik Veri Yapısı
Grafik veri yapısı, bir ifadenin çizgiler ve düğümlerle temsil edilme şeklidir. Bu işlem bir ifadeyi kolaylaştırır ve ifadeyi net bir şekilde tanımlamaya yardımcı olur. Ağaç veri yapısına çok benzer. Pek çok algoritma tarafından sıklıkla kullanılır.
Bir sonraki yazımda görüşmek üzere. :)
