Ağaç Veri Yapısı (Tree)

by admin · Published 13 Temmuz 2017 · Updated 18 Temmuz 2017

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
public void insert(int key) { … }

// search işlevi, key değerine sahip elemanı bulup erişim bilgisini verir
public Node search(int key) { … }

// remove işlevi, key değerine sahip elemanı bulup siler
public void remove(int key) { … }

// findMax işlevi, ağacın en büyük elemanının erişim bilgisini verir
public Node findMax() { … }

// findMin işlevi, ağacın en küçük elemanının erişim bilgisini verir
public Node findMin() { … }
}

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
public void insert(int key) {
root=insert(key,root); // özyinelemeli iç işlevi çağır
}

// parametrede verilen key değerine sahip elemanı, kökü t olan ağaca veya alt ağaca ekler
// özyinelemeli iç işlev, öz nitelik erişimi olmadığı için “static”
private static Node insert(int key, Node t) {
if(t==null)                    // kök yoksa (bu alt ağaç boşsa),
t=new Node(key,null,null);   // yeni eleman kök olsun
else if(key<t.key)             // eklenecek değer, kök elemanından küçükse
t.leftChild=insert(key,t.leftChild);   // yeni elemanı sol alt ağaca ekle
else if(key>t.key)             // eklenecek değer, kök elemanından büyükse
t.rightChild=insert(key,t.rightChild); // yeni elemanı sağ alt ağaca ekle
else ;                         // eklenecek değer, kök elemanına eşitse, bir şey yapma
return t;                      // bu alt ağacın kök eleman erişim bilgisini döndür
}

// search işlevi, key değerine sahip elemanı bulup erişim bilgisini verir
public Node search(int key) {
return search(key,root); // özyinelemeli iç işlevi çağır
}

// parametrede verilen key değerine sahip elemanı, kökü t olan ağacın veya alt ağacın altında arar
// özyinelemeli iç işlev, öz nitelik erişimi olmadığı için “static”
private static Node search(int key, Node t) {
if(t==null)                    // kök yoksa (bu alt ağaç boşsa),
return null;                 // bulamadık
else if(key<t.key)             // aranılan değer, kök elemanından küçükse
return search(key,t.leftChild); // sol alt ağaçta ara
else if(key>t.key)             // aranılan değer, kök elemanından büyükse
return search(key,t.rightChild); // sağ alt ağaçta ara
else                           // aranılan değer, kök elemanından eşitse
return t;                    // bulduk: elemanın erişim bilgisini döndür
}

// remove işlevi, key değerine sahip elemanı bulup siler
public void remove(int key) {
root=remove(key,root); // özyinelemeli iç işlevi çağır
}

// parametrede verilen key değerine sahip elemanı, kökü t olan ağacın veya alt ağacın altında arayıp siler
// özyinelemeli iç işlev, öz nitelik erişimi olmadığı için “static”
private static Node remove(int key, Node t) {
if(t==null)                    // kök yoksa (bu alt ağaç boşsa),
return t;                    // bulamadık
if(key<t.key)                  // silinecek değer, kök elemanından küçükse
t.leftChild=remove(key,t.leftChild);   // sol alt ağaçta ara
else if(key>t.key)             // silinecek değer, kök elemanından büyükse
t.rightChild=remove(key,t.rightChild); // sağ alt ağaçta ara
else                           // bulduk: silelim
if(t.leftChild!=null && t.rightChild!=null) { // silinecek elemanın 2 çocuğu (alt ağacı) varsa
t.key=findMax(t.leftChild).key;         // sol alt ağacının en büyüğü silinecek olanın yerini alsın
t.leftChild=remove(t.key,t.leftChild); // şimdi bu en büyüğü sol alt ağaçtan silelim
}
else if(t.leftChild!=null)   // yalnızca sol çocuğu varsa,
t=t.leftChild;             // sol çocuk, silinecek olanın yerine gelsin
else                         // yoksa,
t=t.rightChild;            // sağ çocuk, silinecek olanın yerine gelsin
return t;                      // bu alt ağacın kök elemanının erişim bilgisini döndür
}

// findMax işlevi, ağacın en büyük elemanının erişim bilgisini verir
public Node findMax() {
if(root==null) return null; // ağaç boşsa, null döndür
return findMax(root); // (değilse) özyinelemeli iç işlevi çağır
}

// kökü t olan ağacın veya alt-ağacın en büyük elemanının erişim bilgisini verir
// özyinelemeli iç işlev, öz nitelik erişimi olmadığı için “static”
private static Node findMax(Node t) {
if(t.rightChild==null) return t; // sağ çocuğu yoksa, en büyük bu
return findMax(t.rightChild); // varsa, sağ çocukla devam et
}

// findMin işlevi, ağacın en küçük elemanının erişim bilgisini verir
public Node findMin() {
Node t=root;                   // kökten başla
if(t!=null)                    // ağaç boş değilse,
while(t.leftChild!=null)     // sol çocuk boş olmadığı sürece,
t=t.leftChild;             // sol taraftan devam et
return t;                      // sol çocuğu olmayan bu en sol, en alt elemanı döndür
}
}

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
}
}