Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde kullanılan veri saklama ve veriye kolay ulaşma yöntemlerinden birisi de ağaçlardır. Çok farklı şekillerde ağaçların kodlanması ve modellenmesi mümkündür. Bu özel ağaçlardan birisi de iç yol indirgeme ağaçlarıdır (internal path reduction tree, IPR Tree).

Bir ipr ağacı kısaca bir ikili ağaçtır (binary tree). Ayrıca IPR ağaçlarının dengeli olması şarttır (balanced tree).

Aynı şekilde ağacı sürekli olarak dengeli tutan ve bir ikili ağaç olan (binary tree) AVL ağaçları ile kıyaslandığında performans olarak eşit veya daha iyi olması söz konusudur. Yani IPR ağaçları AVL ağaçlarından ( avl tree) kötü performansta olamazlar, iyi veya en kötü durumda eşit performans gösterirler.

IPR ağaçlarının derinlik hesaplamasında ağacın iç yol uzunluğu (internal path length) hesaplanır. Bu değerin hesaplanışını hatırlayacak olursak, ağaçtaki iç düğümlere erişmek için yapılan işlem sayısının toplamıdır. aşağıdaki temsili ağaçta iç yol uzunluğu 3’tür.

Tam bu noktada kaynaklardaki bir ayrılıktan bahsetmekte yarar vardır. Bazı kaynaklar kök düğüme (root node) erişimin maliyetini 0 kabul ederken bazı kaynaklar bu maliyeti 1 kabul etmektedir. Örneğin yukarıdaki örnekte şayet kök düğüme erişim maliyeti 0 kabul edilirse ağacın toplam iç yol uzunluğu

0+ 1 + 2 + 0 = 3

Olarak hesaplanır. Ancak bazı kaynaklar iç yol uzunluğunu hesaplarken kök düğümün maliyetini 1 olarak alıp bütün düğümlere (sadece iç düğümlere (internal nodes) değil, hem iç hem de dış düğümlere (external nodes) olan uzaklık) olarak hesaplamaktadır.

Bu durumda yukarıdaki ağacın iç yol uzunluğu:

1 + 2 + 2 + 3 + 3 + 4 = 15

Olarak bulunur.

IPR ağacının çalışması sırasında istenen bir hesaplama yöntemi kullanılabilir, sonuç değişmemektedir.

IPR ağacı üzerinde yapılabilecek işlemleri aşağıdaki şekilde sıralayabiliriz:

Yukarıda sıralanan dört ayrı işlem, IPR ağaçlarında karşılaşılabilecek durumlardır. Bu durumları sıralayacak olursak, yukarıdaki 4 şekil için sırasıyla:

n c > n b => sola döndür

n x > n a => çift sola döndür

n c > n a => sağa döndür

n x > n a => çift sağa döndür

olarak sıralanabilir.

Yukarıdaki açıklamalardan sonra aşağıdaki kelimeleri bir ağaca yerleştirerek IPR ağacının nasıl çalıştığını görelim. Burada dikkat edilecek bir husus, IPR ağacının sadece yerleştirme (insertion) kuralının ikili arama ağacından (binary search tree) farklı olduğudur. Bunun dışında, ağaçta arama yapma işlemi veya bir bilgiyi değiştirme işlemi ikili arama ağacı (binary search tree) ile aynıdır.

Örnek olarak yerleştireceğimiz (insert) kelimeler aşağıdaki kelimeler olsun:

Şadi, Evren, ŞEKER, www, bilgisayar, kavramları, com

Yukarıdaki 7 kelimeyi verilen sırayla yerleştirmeye çalışalım:

Yukarıdaki ekleme işlemleri sırasında, klasik bir ikili arama ağacına ekleme dışında bir işlem yapılmamıştır. Ancak ağacın son halinde, eklenen son kelime ( “com” kelimesi) ile birlikte ağacın dengesi bozulmuştur. Bu aşamaya kadar ağaçta bir dengesizlik bulunmamaktadır.

Ağacın son halindeki durum çift sağa döndürme gerektirip, döndürülmüş hali aşağıda gösterilmiştir:

Bu döndürme işlemi iki aşamada yapılmıştır. Birinci aşamada çift sağa döndürürken x = kavramları, z = evren ve y = şadi şeklinde düşünülebilir. Ardından oluşan yeni ağacın hem solunda hem de sağında yeniden döndürme işlemleri icra edilmiştir.

Yorumlar

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir