in Veri Yapıları

Trees – Ağaçlar

 

Ağaçlar bilgisayar bilimlerinde bir çok farklı alanda kullanılmaktadır.İşletim sistemleri,grafiksel işlemler,veritabanı sistemleri gibi alanlar buna örnektir.Doğadaki ağaçlar ile farkı ise burada kökün en tepede olmasıdır.

Bağlı listeler (Linked Lists), yığıtlar(stack) ve kuyruklar(queues) doğrusal veri yapılarıdır.Ağaçlar(Trees) ise doğrusal olmayan iki boyutlu yapılardır.Ağaçlar en tepede olmak üzere bir adet kök(root) ve onun altında devam eden düğümlerden oluşur.

trees

Şekilde de görüldüğü üzere A düğümümüz kök(root) düğümdür.Onun sağ ve solundan itibaren ise diğer düğümler devam etmektedir.

 

Ağaçlardan bahsederken 3 özellik sayabiliriz.

  1. Ağaçların yapısındaki gruplandırılma sayesinde üstten aşağıya doğru ihtiyaçlarımıza göre verileri azaltabiliyoruz.
  2. Örneğin; iki adet düğümümüz var ve bunların alt düğümlerinde ise aynı veri var.Bu durumda bir tanesindeki veriyi değiştirdiğimiz de diğer veri etkilenmeyecektir.Çünkü her bir düğüm kendi üst düğümüne bağlıdır.
  3. Yukarda bahsettiğim nedenden ötürü de her düğüm aslında unique(eşsiz) değerdir.

Aşağıdaki resimde Unix işletim sisteminin dosya yapısını görebilirsiniz.

unixd

Gördüğünüz gibi kök dizinden başlayarak istediğiniz dizine sırasıyla inebiliyorsunuz.

Bir başka örnekte HTML tarafından;

Evet bu kodlarında ağaçlardaki karşılığı bu resimdeki gibidir.

htmltree

Aslında bilgisayar kullandığımız her gün ağaçlar veri yapısıyla iç içeyiz.Bir web sayfasını açtığımızda HTML kodlarıyla işlem yapıyoruz.İşletim sistemlerimizde de aynı şekilde dosya sistemini kullanıyoruz.Şimdi birde ikili arama ağaçlarına değinelim.

 İkili Arama Ağaçları(Binary Search Tree)

İkili arama ağaçlarında kökün solundaki değerler her zaman kendisinden küçük, sağındaki değerler ise kendisinden büyük olmalıdır.İkili arama ağaçlarında en önemli işlemlerden birisi arama işlemidir.

binarysearchtreeGörüldüğü üzere 47’nin kök olduğu bir ağaç yapısında 25 değeri eklenmesi gerektiğinde küçük olduğu için sol tarafa ekleniyor.77 ise 47’den büyük olduğu için sağ tarafa ekleniyor.Ayrıca dikkat edilmesi gereken bir diğer konu ise her kökün değerine göre işlem yapılmasıdır.Yani 1. Düzey’de ki 77’ye eklenen 93 değerinin 47’de yeni bir düğüm açmadığını ve 77’nin sağına eklendiğini görmüş olmalısınız.

İkili arama ağaçlarında arama işlemi yapmak istediğimizde ise şöyle bir yol izlenir.

Aranacak değer 17 olsun diyelim.

  1. 17 ve 47 sayıları karşılaştırılacaklardır.Buradan 17<47 sonucu çıkacaktır.Yani aramaya sol düğümden devam edilecektir.
  2. 17 ve 25 sayıları karşılaştırılacaklardır. Buradan 17<25 sonucu çıkacak.Aramaya sol düğümden devam edilecek.
  3. Bu seferki değerimiz 11. 17 ve 11 karşılaştırılacak.  Buradan da 17>11 sonucu çıkacak.Bu sefer de sağ düğümden devam edilecek.
  4. Son adım olarakta 17 ile 17 karşılaştırılarak işlem tamamlanmış olacak.

 

Evet bu konuda değineceklerim bu kadar.

Bir diğer yazıda görüşmek üzere…

 

Yorum yaz

Comment