bilgiz.org

BöLÜm ağAÇlar (trees) Giriş




Tarih14.10.2017
Büyüklüğü52.93 Kb.

Indir 52.93 Kb.

BÖLÜM 4

AĞAÇLAR (TREES)
4.1 Giriş
Bağlı listeler, yığıtlar ve kuyruklar doğrusal (linear) veri yapılarıdır. Ağaçlar ise doğrusal olmayan belirli niteliklere sahip iki boyutlu veri yapılarıdır (Şekil 4.1). Ağaçlardaki düğümlerden iki veya daha fazla bağ çıkabilir. İkili ağaçlar (binary trees), düğümlerinde en fazla iki bağ içeren (0,1 veya 2) ağaçlardır. Ağacın en üstteki düğümüne kök (root) adı verilir.


Şekil 4.1 : Bir ikili ağacın grafiksel gösterimleri
Şekil 4.1'de görülen ağacın düğümlerindeki bilgiler sayılardan oluşmuştur. Her düğümdeki sol ve sağ bağlar yardımı ile diğer düğümlere ulaşılır. Sol (leftptr) ve sağ (rightptr) bağlar boş ("NULL" = "/" = "\") da olabilir. Düğüm yapıları değişik türlerde bilgiler içeren veya birden fazla bilgi içeren ağaçlar da olabilir. Doğadaki ağaçlar köklerinden gelişip göğe doğru yükselirken veri yapılarındaki ağaçlar kökü yukarıda yaprakları aşağıda olacak şekilde çizilirler.
Şekil 4.2'deki ağaç, A düğümü kök olmak üzere 9 düğümden oluşmaktadır. Sol alt ağaç B kökü ile başlamakta ve sağ alt ağaç da C kökü ile başlamaktadır. A'dan solda B'ye giden ve sağda C'ye giden iki dal (branch) çıkmaktadır.


Şekil 4.2 : Ağaçlarda düzeyler

4.2 Tanımlar (Örnekler Şekil 4.2'ye göre verilmiştir) :


  1. İkili Ağaç (Binary Tree) : Sonlu düğümler kümesidir. Bu küme boş bir küme olabilir (empty tree). Boş değilse şu kurallara uyar.

  1. Kök olarak adlandırılan özel bir düğüm vardır.

  2. Her düğüm en fazla iki düğüme bağlıdır.

  3. Kök hariç her düğüm bir daldan gelmektedir.

  4. Tüm düğümlerden yukarı doğru çıkıldıkça sonuçta köke ulaşılır.




  1. Düğüm (node) : Ağacın her bir elemanına düğüm adı verilir. Örnekler : A, B, C.




  1. Kök (root) : Düzey 0'daki (şemanın en üstündeki) tek düğüm. Örnek : Şekil 4.2'de A bilgisini içeren düğüm.




  1. Çocuk (child) : Bir düğümün sol ve sağ bağı aracılığı ile bağlandığı düğümler o düğümün çocuklarıdır. Örnek : B ve C, A'nın çocuklarıdır.




  1. Parent : Bir düğüm, sağ ve sol bağları ile bağlandığı düğümlerin parent'ıdır. A düğümü, B ve C düğümlerinin parent'ıdır.




  1. Bir düğümün düzey (level) veya derinliği (depth) : Bir düğümün kök düğümden olan uzaklığıdır. Örnek : D düğümünün düzeyi veya derinliği 2'dir.




  1. Ağacın derinliği (depth of tree) : En derindeki yaprağın derinliği veya yüksekliği (height). Örnek : Şekil 4.2'deki ağacın derinliği 3'tür.




  1. Yaprak (leaf) : Sol ve sağ bağı boş olan düğümlere yaprak adı verilir. Örnekler : D,G,H,I.




  1. Kardeş (sibling, brother) : Aynı parent'a sahip iki düğüme kardeş düğümler adı verilir. Örnekler : B ile C kardeştir. D ile E kardeştir. H ile I kardeştir.




  1. Ancestor (üst düğüm) : Bir düğümün parent'ı birinci ancestor'ıdır. Parent'ın parent'ı (recursion) ikinci ancestor'ıdır. Kök, kendi hariç tüm düğümlerin ancestor'ıdır.




  1. Descendant (alt düğüm) : Bir düğümün iki çocuğu birinci descendant'larıdır. Onların çocukları da ikinci descendant'larıdır.




  1. Full binary tree : i) Her yaprağı aynı derinlikte olan ii) Yaprak olmayan düğümlerin tümünün iki çocuğu olan ağaç Full (Strictly) Binary Tree'dir (İkinci şart yeterli). Bir full binary tree'de n tane yaprak varsa bu ağaçta toplam 2n-1 düğüm vardır.




  1. Complete binary tree : Full binary tree'de yeni bir derinliğe soldan sağa doğru düğümler eklendiğinde oluşan ağaçlara Complete Binary Tree denilir. Böyle bir ağaçta bazı yapraklar diğerlerinden daha derindir. Bu nedenle full binary tree olmayabilirler. En derin düzeyde düğümler olabildiğince soldadır.




  1. General Tree (Ağaç) : Her düğümün en fazla iki çocuğu olabilme sınırı olmayan ağaçlardır.



  1. İkili Arama Ağacı (Binary Search Tree) : Boş olan veya her düğümü aşağıdaki şartlara uyan anahtara sahip bir ikili ağaçtır :




  1. Kökün solundaki alt ağaçlardaki (eğer varsa) tüm anahtarlar kökteki anahtardan küçüktür.

  2. Kökün sağındaki alt ağaçlardaki (eğer varsa) tüm anahtarlar kökteki anahtardan büyüktür.

  3. Sol ve sağ alt ağaçlar da ikili arama ağaçlarıdır.



4.3 İkili Ağaçlar ve İkili Ağaçlar Üzerindeki Dolaşma İşlemleri
Dolaşma (traverse), ağaç üzerindeki tüm düğümlere uğrayarak gerçekleştirilir. Ağaçlar üzerindeki dolaşma işlemleri, ağaçtaki tüm bilgilerin listelenmesi veya başka amaçlarla yapılır. Doğrusal veri yapılarında baştan sona doğru dolaşmak kolaydır. Ağaçlar ise düğümleri doğrusal olmayan veri yapılarıdır. Bu nedenle farklı algoritmalar uygulanır. Çok bilinen yöntemler üç tane olup özyinelemeden yararlanırlar :


  1. Preorder (depth-first order) Dolaşma (Traversal)

  1. Köke uğra (visit)

  2. Sol alt ağacı preorder olarak dolaş.

  3. Sağ alt ağacı preorder olarak dolaş.




  1. Inorder (Symmetric order) Dolaşma

  1. Sol alt ağacı inorder'a göre dolaş

  2. Köke uğra (visit)

  3. Sağ alt ağacı inorder'a göre dolaş.




  1. Postorder Dolaşma

  1. Sol alt ağacı postorder'a göre dolaş

  2. Sağ alt ağacı postorder'a göre dolaş.

  3. Köke uğra (visit)

A


B

C

D

F



PreOrder : ABDGCEHIF


InOrder : DGBAHEICF

E


PostOrder : GDBHIEFCA





G


H

I

Şekil 4.3 : İkili Ağaç ve değişik şekillerde dolaşılması

4.4 İkili Arama Ağaçları
İkili arama ağaçları, her bir düğümün solundaki (sol alt ağacındaki) tüm düğümler kendisinden küçük, sağındakiler (sağ alt ağacındakiler) de kendisinden büyük olacak şekilde oluşturulurlar (Şekil 4.4). İkili arama ağaçlarındaki en önemli işlemlerden birisi aramadır.
Örnek olarak aşağıdaki ağaçta, 44 sayısını aratmak için şu işlem sırası izlenir :

Karşılaştırma 1 : 44, 47 ile karşılaştırılır. 44<47 olduğundan sol bağdan ilerlenir.

Karşılaştırma 2 : 44, 25 ile karşılaştırılır. 44>25 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 3 : 44, 43 ile karşılaştırılır. 44>43 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 4 : 44 == 44. Aranan anahtar değeri ağaçta bulundu!
Örnek olarak aşağıdaki ağaçta, 90 sayısını aratmak için şu işlem sırası izlenir :

Karşılaştırma 1 : 90, 47 ile karşılaştırılır. 90>47 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 2 : 90, 77 ile karşılaştırılır. 90>77 olduğundan sağ bağdan ilerlenir.

Karşılaştırma 3 : 90, 93 ile karşılaştırılır. 90<93 olduğundan sol bağdan ilerlenir.

: NULL. Aranan anahtar değeri ağaçta bulunamadı.



Şekil 4.4 : İkili Arama Ağacı
Görüldüğü gibi arama işleminin etkinliği ağacın yüksekliğine bağlıdır. İkili arama ağaçları dengeli tutulabilirse, bir anahtar değerini aramada oldukça hızlıdırlar. Böyle olduğunda n elemanlı bir ağaç en fazla log2n düzeyden oluşur. Bir değerin bulunması veya ağaçta olmadığının belirlenmesi için en fazla log2n karşılaştırma yapılır. Örnek olarak 1000 elemanlı bir ikili arama ağacında bir elemanın bulunabilmesi için en fazla 10 karşılaştırma yapmak gerekecektir (210=1024 > 1000). Bağlı listelerde ise bulunacak elemanın değerine göre (eleman sonda ise) 1000 karşılaştırma yapmak gerekebilir.
Düğüm sayısı n olan Complete Binary Tree'de derinliği hesaplayabiliriz.

n = 20 + 21 + 22 +... + 2d = 2d+1-1 => n+1 = 2d+1 => d = log2(n+1) - 1'dir.

15 düğümlü bir ağaçta d = log2(15+1) - 1 = 4-1 = 3'tür.
İkili ağaçlardaki dolaşma işlemlerinin tümü ikili arama ağaçlarında da kullanılır. İkili arama ağaçları üzerinde inorder dolaşıldığında tüm elemanlar küçükten büyüğe sıralı bir şekilde karşımıza gelecektir.

İkili arama ağaçlarının oluşturulması ise şu şekildedir : Herhangi sıralı olmayan bir sayı dizisi gelirken her bir eleman ağaca bir yaprak düğüm olarak eklenir. Örnek olarak sıra ile, 47, 25, 43, 77, 65, 68, 93, 11, 17, 44, 31, 7 sayıları ağaca eklenmek istenirse:

47 : 47 köke eklenir.

25 : 25<47, 47'nin soluna eklenir.

43 : 43<47, 43>25, 25'in sağına eklenir.

77 : 77>47, 47'nin sağına eklenir.

65 : 65>47, 65<77, 77'nin sol bağına eklenir. (Ağacı tamamlayınız...).
.....

.....


.....

.....


.....

İkili arama ağaçları, tekrarları önlemek açısından da oldukça yararlıdırlar. Ağaç oluşturulurken tekrar eden bir eleman eklenmek istendiğinde, kökten itibaren sola git, sağa git kararları ile o değerin olduğu yere hızlıca ulaşılacak ve ağaçta (veriler içinde) o değerin zaten olduğu anlaşılacaktır. Bu şekilde tekrar eden verilerin olması engellenir.


Bunlar dışında ikili arama ağacından düğüm silme, ikili arama ağacını iki boyutlu ağaç biçiminde ekrana çizdirme, ağacı düzey sırasında dolaşma (düzey düzey soldan sağa) gibi algoritmalar da yazılabilir. Ayrıca ağaç düzeyini bulma, ağaca string de dahil birçok bilgi ekleme gibi işlemler de yapılabilir.

4.5 İkili Arama Ağacı Oluşturmayı ve Ağacı Dolaşmayı Sağlayan C Programı
#include

#include

#include
/* Düğüm Yapısı */

struct treenode {

struct treenode *leftptr;

int data;

struct treenode *rightptr;

};
typedef struct treenode TREENODE;

typedef struct treenode * TREENODEPTR;
// Ağaca düğüm eklemeyi sağlayan fonksiyon

TREENODEPTR dugumekle(TREENODEPTR treeptr, int veri)

{

if(treeptr==NULL)

{

treeptr =(treenode *) malloc(sizeof(treenode));

if (treeptr!=NULL)

{

treeptr->data = veri;

treeptr->leftptr = NULL;

treeptr->rightptr = NULL;

}

else printf("%d eklenemedi. Bellek yetersiz.\n",veri);

}

else

if(veridata)

treeptr->leftptr = dugumekle(treeptr->leftptr,veri);

else

if(veri>treeptr->data)

treeptr->rightptr = dugumekle(treeptr->rightptr,veri);

else printf("Dup");

return treeptr;

}

/* Ağacın inorder dolaşılması */

void inorder(TREENODEPTR treeptr)

{

if (treeptr != NULL) {

inorder(treeptr->leftptr);

printf("%3d",treeptr->data);

inorder(treeptr->rightptr);

};

}
/* Ağacın preorder dolaşılması */

void preorder(TREENODEPTR treeptr)

{

if (treeptr != NULL) {

printf("%3d",treeptr->data);

preorder(treeptr->leftptr);

preorder(treeptr->rightptr);

};

}

/* Ağacın postorder dolaşılması */

void postorder(TREENODEPTR treeptr)

{

if (treeptr != NULL) {

postorder(treeptr->leftptr);

postorder(treeptr->rightptr);

printf("%3d",treeptr->data);

};

}

void main()

{

int i, item;

TREENODEPTR treeptr = NULL;
srand(time(NULL));
/* Ağaca yerleştirilecek sayılar */

printf("\n\n");

for(i=0; i<15; ++i)

{

item = rand() % 10;

printf("%3d ", item);

printf("%3d ", item);

treeptr = dugumekle(treeptr, item);

};

printf("\n");
/* Ağacın preorder dolaşılması */

printf("Ağacın preorder dolaşılması :\n");

preorder(treeptr); printf("\n");

/* Ağacın inorder dolaşılması */

printf("Ağacın inorder dolaşılması :\n");

inorder(treeptr); printf("\n");

/* Ağacın postorder dolaşılması */

printf("Ağacın postorder dolaşılması :\n");

postorder(treeptr); printf("\n");
}









    Ana sayfa


BöLÜm ağAÇlar (trees) Giriş

Indir 52.93 Kb.