Ağaç Veri Yapısı (Tree)
Ağaç veri yapısı, elemanlarının birbirlerine liste veri yapısında olduğu gibi referanslar aracılığı ile bağlandığı bir veri yapısıdır. Bu veri yapısının listelerden farklılığı, liste veri yapısının aksine bir elemanın birden fazla elemana bağlanmasının mümkün olmasıdır. Bu sayede ağaç veri yapısında yer alan elemanlar arasında hiyerarşik bir diziliş sağlamak mümkündür. Bir ağaç veri yapısında bir elemanın en fazla kaç elemana bağlanabileceği o ağaç veri yapısının derecesini (order) belirtmektedir. Derecesi iki olan ağaç veri yapısı en basit ağaç türü olarak oluşmakta ve ikili ağaç (binary tree) diye adlandırılmaktadır. Aşağıdaki şekilde elemanları tamsayı olan bir ikili ağaç örneği verilmiştir;
Liste veri yapısında herhangi bir elemandan önce (predessor) veya sonra gelen (successor) sadece bir (liste başı ve sonu için sıfır) tane eleman bulunmaktaydı. Ağaç veri yapısında ise, her elemanın yine bir (kök için sıfır) tane önce geleni (predessor) bulunurken, o elemandan sonra gelen eleman sayısı birden fazla (en fazla ağacın derecesi kadar) olabilir. Her ağaçta kendisinden önce hiçbir eleman bulunmayan bir eleman bulunur. Bu eleman yukarıdaki şekilde de görüldüğü gibi en üstte yer alan elemandır ve ağacın kökü (root) olarak adlandırılır. Ayrıca kendisinden sonra hiç eleman bulunmayan elemanlar da ağaçta yer alır ve bu elemanlar da ağacın yaprakları (leaves) olarak adlandırılır. Yukarıdaki örnek ikili ağaçta 5 değerine sahip eleman ağacın kökü ve 3, 6 ve 13 değerlerine sahip elemanlar da ağacın yapraklarıdır. Ayrıca ağaç veri yapısında herhangi bir elemandan sonra gelen elemanlar, o elemanın çocukları (children) olarak adlandırılırken, yine herhangi bir elemandan önce yer alan elemana da, o elemanın velisi (parent) denir. Ayrıca ağaç veri yapısının oluşması için (kök dışındaki) her elemanın sadece bir tek velisi olması gerektiğine dikkat ediniz.
Liste veri yapısında olduğu gibi ağaç veri yapısında da elemanlar arasında bir sıralama kullanmak mümkündür. İkili arama ağacı (binary search tree) diye adlandırdığımız ağaç veri yapısında bu sıralama ölçütü, her elemanın sol tarafında yer alan çocuğundan büyük olması ve sağ tarafında yer alan çocuğundan küçük olması olarak belirlenmiştir. Bu dersimizde anlatım kolaylığının sağlanabilmesi için sunacağımız program parçaları ve uygulamalarda ikili arama ağacı kullanılacaktır. Ancak bu uygulama ve programlar başka ağaç türleri için de kolaylıkla güncellenebilir. Bu noktadan sonra ağaç kavramı, “ikili arama ağacı” anlamında kullanılacaktır.
Aşağıda ağaç veri yapısı tanıtılmaktadır:
// Ağaçta tutulacak herbir elemanı tanımlayan sınıf class Node { int key; // elemanın değeri Node leftChild, rightChild; // sol ve sağ elemanların erişim bilgileri // yapıcı işlev, parametre değerlerinin ilgili öz niteliklere atar Node(int key, Node leftChild, Node rightChild) { … } }// Ağaç veri yapısını, “ikili arama ağacı” olarak tanımlayan sınıf public class Tree { private Node root; // ağacın kök elemanının erişim bilgisi// yapıcı işlev, kökü olmayan boş bir ağaç tanımlar public Tree() { … } // insert işlevi, key değerine sahip elemanı ağaca ekler // search işlevi, key değerine sahip elemanı bulup erişim bilgisini verir // remove işlevi, key değerine sahip elemanı bulup siler // findMax işlevi, ağacın en büyük elemanının erişim bilgisini verir // findMin işlevi, ağacın en küçük elemanının erişim bilgisini verir |
Yukarıdaki tanımda da görüldüğü gibi ağaç veri yapısına eleman ekleme ve çıkarma işlemleri insert ve delete işlevleriyle gerçekleştirilmektedir. Search işlevi ise değeri belirtilen değeri taşıyan elemanı ağaç içerisinde bularak, bu elemana işaret eden referansı döndürmektedir.
Yukarıda Tree tanımından önce Node adını verdiğimiz bir başka bir yapı tanımı kullanılmıştır. Bu yapı ağaçta yer alacak elemanların türünü belirlemektedir ve Tree yapısı olarak yarattığımız ağacın elemanlarıNode yapısında tanımlanan şekilde olacaktır. Bu, ağaç yapısı içindeki kök (root) öz niteliğinin Node yapısına bir referans olarak tanımlanmasıyla elde edilmiştir. Yukarıdaki Node tanımına göre yaratılan ağaç tam sayılardan (int) oluşacaktır. Sadece bu tanımı değiştirerek farklı yapılarda elemanların yer alabileceği değişik ağaçlar tanımlanabilir. Node tanımında key değişkeni ile ağaçta tutulan değerlerin türü belirtilirken, rightChild ve leftChild değişkenleri ile de bir elemanı çocuklarına bağlayan referanslar tanımlanmıştır.
Tanımlanan Node yapısı, aşağıdaki şekilde de görüldüğü gibi ağaç elemanının saklandığı ve çocuklara bağlantıyı sağlayan referansların yer aldığı, üç farklı kısımdan oluşmaktadır.
Aşağıdaki şekilde ise Node tanımıyla elde edilen eleman yapılarının oluşturduğu bir ağaç yer almaktadır.
Ağaç İşlemlerinin Gerçekleştirimi
Ağaç veri yapısı üzerindeki işlemlerin ne gibi sonuçlar verdiğini inceledikten sonra şimdi bu işlemlerin gerçekleştirimini daha detaylı inceleyebiliriz.
Bir önceki bölümde tanıtılan işlemler aşağıda tanımlanmış, Node.java ve Tree.java dosyalarında verilmiştir:
// Ağaçta tutulacak herbir elemanı tanımlayan sınıf class Node { int key; // elemanın değeri Node leftChild, rightChild; // sol ve sağ elemanların erişim bilgileri// yapıcı işlev, parametre değerlerinin ilgili öz niteliklere atar Node(int key, Node leftChild, Node rightChild) { this.key=key; this.leftChild=leftChild; this.rightChild=rightChild; } }// Ağaç veri yapısını, “ikili arama ağacı” olarak tanımlayan sınıf public class Tree { private Node root; // ağacın kök elemanının erişim bilgisi// yapıcı işlev, kökü olmayan boş bir ağaç tanımlar public Tree() { root=null; } // insert işlevi, key değerine sahip elemanı ağaca ekler // parametrede verilen key değerine sahip elemanı, kökü t olan ağaca veya alt ağaca ekler // search işlevi, key değerine sahip elemanı bulup erişim bilgisini verir // parametrede verilen key değerine sahip elemanı, kökü t olan ağacın veya alt ağacın altında arar // remove işlevi, key değerine sahip elemanı bulup siler // parametrede verilen key değerine sahip elemanı, kökü t olan ağacın veya alt ağacın altında arayıp siler // findMax işlevi, ağacın en büyük elemanının erişim bilgisini verir // kökü t olan ağacın veya alt-ağacın en büyük elemanının erişim bilgisini verir // findMin işlevi, ağacın en küçük elemanının erişim bilgisini verir |
Ağaç işlemlerini özyinelemeli olarak düşünmek ve yazmak, özyinelemesiz çözümlere göre çoğunlukla daha kolaydır. Bu nedenle (findMin hariç) yukarıdaki işlemlerin tümü, özyinelemeli iç (private) işlevleri çağrılarak gerçekleştirilmiştir. Bu özyinelemeli işlemler, kendisine parametre olarak verilen ağaç düğümü (elemanı) ve onun çocuklarını içeren alt ağaç üzerinde çalışırlar. Her adımda, verilen key değerini, üzerinde çalıştıkları alt ağacın kökü ile karşılaştırıp, key değeri daha küçükse sol, büyükse sağ çocuğu kök kabul eden alt ağaçla işleme devam etmek üzere özyinelemeli olarak kendilerini çağrırlar.
Yukarıdaki insert ve search işlevleri de bu şekilde tanımlanmışlardır. Eleman ekleme (insert) işlevinde, eğer ağaç boş ise yeni bir eleman yaratılmış ve kök (root) referansı bu yeni elamanı gösterir hale getirilmiştir. Eğer ağaçta bazı elemanlar varsa, özyinemeli çağrılarla yeni elemanın ağacın uygun yerine yerleştirilmesi sağlanmıştır. Bu işlev sonuçta ağacın yeni halini gösteren kök değişkenine dönmektedir. Benzer bir yaklaşımla arama (search) işlevinde ise aranan eleman ağaçta bulunmakta ve o elemanı işaret eden referans belirlenmektedir. Eğer aranan eleman ağaçta yok ise göstergecin “null” olarak döndürüleceğine dikkat ediniz.
Yukarıda tanımlanan işlevlerden eleman silme işlevi (delete) en karmaşık işlev olarak karşımıza çıkmaktadır. Bunun nedeni, işlevin herhangi bir eleman silindiğinde ağacın yine ikili arama ağacı özelliklerini korumasını sağlamasıdır. İkili arama ağacının korunması için bu işlevde elemanın silinmesinin yanı sıra, ağaç üzerinde bazı düzenlemeler de gerçekleştirilmiştir.
Aslında bu işlevi, silinecek elemanın ağacın hangi bölümünde olabileceği olasılıklarına göre değişik alt parçalardan oluşmuş olarak düşünebiliriz. Her alt parçacık oluşan durumda gereken düzenlemeyi yapmak üzere tanımlanmıştır. Şimdi bu işlevi bu alt parçalara göre adım adım inceleyebiliriz:
i) İşlevin başında, ikinci else kısmına kadar uzanan özyinelemeli çağrılar, silinecek elemanın ağaç üzerindeki yerini tespit etmektedir. Eğer eleman bulunamazsa, işlevi “null” döndürmektedir.
ii)Elemanın bulunduğu durumdaki olasılıklar tek tek incelenmektedir: İlk olasılık olarak silinecek elemanın iki çocuğu olması ele alınmaktadır. Kök silineceği için kökün yerine ondan bir önceki veya bir sonraki eleman yerleştirilmelidir. Bu kökün sol tarafında yer alan alt ağacın en sağındaki eleman (yani sol alt ağacın en büyüğü) olabileceği gibi, sağ tarafında yer alan alt ağacın en solunda yer alan eleman da (yani sağ alt ağacın en küçüğü) olabilir. Tanımlanan işlevde sol alt ağaç kullanılmıştır. Aşağıdaki şekilde örnek bir ağaç üzerinde kök silindiğinde yapılacak düzenleme ve elde edilen yeni ağaç gösterilmiştir.
Silinecek elemanın iki çocuğu yoksa; sol çocuğu olması durumunda, bu sol çocuk silinecek elemanın yerini almaktadır. Eğer sol çocuğu yoksa, bu kez de sağ çocuk kökün yerine geçmektedir. Burada, sağ çocuk “null” değerine de sahip olabilir; bu da silinecek elemanın hiç çocuğu olmadığı anlamına gelmektedir ve bu durumda silinen elemanın yerini başka bir eleman almayacaktır.
iii) Silme işlevinde diğer büyük işlem de, silinecek elemanın yerini alan sol alt ağacın en büyüğünün silinmesidir. Buradaki tüm kurallar, o silme için de geçerli olacağından, bu işlem bir özyineleme çağrısı ile kolayca gerçekleştirilmektedir.
Aşağıdaki şekilde silinecek olan 2’nin yerini 1.5 aldığı için, 1.5’un aşağıdan silinmesi gereklidir. 1.5 silindiğinde de, onun sol çocuğu 1.1 onun yerini alacaktır.
Ağacın en büyük ve en küçük elemanlarını bulmak için findMax ve findMin işlevleri tanımlanmıştır. İkili arama ağacının en büyüğü en sağdaki, en küçüğü ise en soldaki eleman olacaktır. findMax bu işlemi özyinelemeli olarak yaparken, findMin ise (farklı bir örnek verebilmek amacı ile) döngü ile gerçekleştirmektedir.
Tanımlanan ağaç veri yapısına çeşitli elemanlar ekleyen ve çıkaran örneği aşağıda bulabilirsiniz. Bu örnek, silinecek elemanın iki çocuğu olması durumunda, silinenin yerine sağ alt ağacın en küçüğünü kaydırmaktadır:
Ağaç Uygulaması: Tarama İşlemleri
İkili arama ağacında saklanan verileri, kullanılan erişim sırasına göre üç değişik şekilde taramak mümkündür. Bu tarama şekilleri sıralı (inorder), sıra önceli (preorder) ve sıra sonralı (postorder) olarak adlandırılmaktadırlar.
i) Sıra önceli (preorder) tarama da her elemana o elemanın sol ve sağ alt ağaçlarındaki tüm elemanlardan önce erişilmektedir. ii) Sıralı (inorder) tarama da her elemana , o elemanın sol alt ağacındaki elemanlardan sonra, fakat sağ alt ağacındaki tüm elemanlardan önce ulaşılmaktadır.
iii) Sıra sonralı (postorder) tarama da her elemana, o elemanın sol ve sağ alt ağaçlarındaki tüm elemanlardan sonra erişilmektedir.
Aşağıdaki şekilde bir ikili ağaç, ve bu ağacın elemanlarının bu üç değişik tarama yöntemiyle erişilme sıraları verilmiştir.
Bu tarama yöntemlerinin Java işlevleri aşağıda verilmiştir.
static void preorder(Node t) {
if(t!=null) {
System.out.print(t.key+” “); // bu elemanı yaz
preorder(t.leftChild); // sol alt ağacı sıra önceli gezin
preorder(t.rightChild); // sağ alt ağacı sıra önceli gezin
}
}static void inorder(Node t) {
if(t!=null) {
inorder(t.leftChild); // sol alt ağacı sıralı gezin
System.out.print(t.key+” “); // bu elemanı yaz
inorder(t.rightChild); // sağ alt ağacı sıralı gezin
}
}static void postrder(Node t) {
if(t!=null) {
postorder(t.leftChild); // sol alt ağacı sıra sonralı gezin
postorder(t.rightChild); // sağ alt ağacı sıra sonralı gezin
System.out.print(t.key+” “); // bu elemanı yaz
}
}