ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Yzm 2116 Bölüm 7 - Tree ve Binary tree - İkili Ağaç

•Download as PPTX, PDF•
•
Deniz KILINÇ
Deniz KILINÇ

Binary Tree, İkili Ağaç, Traversal, Ağaç Üzerinde Gezinme, Preorder, Postorder, Inorder

1 of 55
Downloaded 243 times
YZM 2116 Veri Yapıları Yrd. Doç. Dr. Deniz KILINÇ Celal Bayar Üniversitesi Hasan Ferdi Turgutlu Teknoloji Fakültesi Yazılım Mühendisliği
BÖLÜM - 6 Bu bölümde, • Ağaç (Tree) Veri Yapısı Giriş • Ağaç VY Temel Kavramlar • İkili Ağaç (Binary Tree) • İkili Ağaç Özellikleri • İkili Ağaç Gerçekleştirim • İkili Ağaç Üzerinde Gezinme (Traverse) • Preorder, Inorder, Postorder • İkili Ağaç Gerçekleştirimine Dair Sorular konusuna değinilecektir. Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları
3Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları • Verilerin birbirine sanki bir ağaç yapısı oluşturuyormuş gibi sanal olarak bağlanmasıyla elde edilen hiyerarşik yapıya sahip veri yapısıdır. • Aynı aile soyağacında olduğu gibi hiyerarşik bir yapısı vardır ve orada geçen birçok kavram buradaki ağaç veri yapısında da tanımlıdır. • Örneğin çocuk, kardeş düğüm, aile, ata gibi birçok kavram ağaç veri yapısında da kullanılır. • Her biri değişik bir uygulamaya doğal çözüm olan ikili ağaç, kodlama ağacı, sözlük ağacı, kümeleme ağacı gibi çeşitli ağaç şekilleri vardır; üstelik uygulamaya yönelik özel ağaç şekilleri de çıkarılabilir. Ağaç VY Giriş
4Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları • 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. • Ağaçlar hiyerarşik ilişkileri göstermek için kullanılır. • Her ağaç düğümlerden (node) ve kenarlardan (edge) oluşur. • Her düğüm bir nesneyi gösterir. • Her kenar (bağlantı) iki node arasındaki ilişkiyi gösterir. • Arama işlemi bağlı listelere göre çok hızlı yapılır. Ağaç VY Giriş (devam…)
5Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Ağaç VY Giriş (devam…) • 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 ve sağ bağlar NULL olabilir. • Düğüm yapıları değişik türlerde bilgiler içeren veya birden fazla bilgi içeren ağaçlar da olabilir.
6Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları • Ağaç veri yapısı / modeli aşağıdaki yazılım uygulamalarında kullanılırlar: o İşletim sisteminin dosya sistemini modellemekte o Oyunlar için farklı hamleleri ele almakta o Ağ routing (yönlendirme) algoritmalarında o Trie adı verilen VY ile sözlük oluşturmakta ve dinamik yazım kontrolü gibi alanlarda o Huffman sıkıştırma kodlamasında ve o Derleyicilerde matematiksel ifadeleri modellemede kullanılırlar. Ağaç VY Kullanılan Yazılım Uygulamaları
7Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Örnek Ağaç Yapısı – Dosya Sistemi /yazilim kitaplar kodlar dersler yzm219 yzm112 ... 1.pdf 2.pdf 1.pdf 2015-2016 eskia.java b.java yzm2116 yzm317 yzm215 ... 1.ppt 1.doc 1.Pdf
8Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Örnek Ağaç Yapısı – Şirket Organizasyonu
9Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Ağaç VY Temel Kavramlar Level - Seviye 0 1 2 3 A B C D E F G Kök (root) Yaprak Düğüm Aile / Ara Düğüm Yaprak Düğüm 7 düğümlü ağaç Çocuk Düğümler • A düğümü kök olmak üzere 7 düğümden (n) oluşmaktadır. • Toplam 6 kenar (n-1) vardı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.
10Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Ağaç VY Temel Kavramlar (devam…) • Düğüm (Node): Ağacın her elemanına verilen isim. • Kök (Root): Ağacın başlangıç düğümüdür. • Çocuk (Child): Bir düğüme doğrudan bağlı olan düğümlere o çocukları denilir. • Kardeş Düğüm (Sibling): Aynı düğüme bağlı düğümlere kardeş düğüm veya kısaca kardeş denir. • Aile (Parent): Düğümlerin doğrudan bağlı oldukları düğüm aile olarak adlandırılır; diğer bir deyişle aile, kardeşlerin bağlı olduğu düğümdür. • Ata (Ancestor): Aile düğümünün daha üstünde kalan düğümlere denir. • Torun (Dedscendant): Bir düğümün çocuğuna bağlı olan düğümlere denir.
11Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Ağaç VY Temel Kavramlar (devam…) • Yaprak (Leaf): Ağacın en altında bulunan ve çocukları olmayan düğümlerdir. • Derece (Degree): Bir düğümden alt hiyerarşiye yapılan bağlantıların sayısıdır; yani çocuk veya alt ağaç sayısıdır. • Seviye (Level): Hiyerarşik sıradır (rank). Kök düğüm seviye = 0. • Derinlik (Depth): Bir düğümün köke olan uzaklığı derinliktir. Kök düğüm derinlik = 0. • Yükseklik (Height): Bir düğümün kendi silsilesinden en uzak yaprak düğüme olan uzaklığıdır. Yaprak düğümlerin yükseliği = 0. (Kök yüksekliği = Ağaç Yükesekliği) • Yol (Path): Bir düğümün aşağıya doğru (çocukları üzerinden) bir başka düğüme gidebilmek için üzerinden geçilmesi gereken düğümlerin listesidir.
12Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Ağaç VY Temel Kavramlar (devam…) A B C D E F G Kök (Root) Tanım Kök B D Çocuk/Derece 2 0 0 Kardeş 1 2 3 Seviye 0 1 2 Aile yok Kök C Ata yok yok Kök Yol A A, B A,C,D Derinlik 0 1 2 Yükseklik 3 0 0
13Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Ağaç VY Temel Kavramlar (devam…) Düğüm sayısı: Yükseklik: Kök düğüm: Yapraklar: Seviye sayısı: H'nin ataları: B'nin torunları: E'nin kardeşleri: 9 4 A C, D, F, H, I 4 E, B, A G, H, I D, F
14Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Ağaçlara Özyinelemeli Yaklaşım • Rekürsif mantıkla bir ağaç, bir kök (root) ve alt-ağaçlar şeklinde tanımlanır. • 1 düğümü  2 ve 3 alt-ağaçlarından oluşur • 2 düğümü  4,6 ve 5 (5-9-10) olmak üzere üç alt-ağaçtan oluşur.
15Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç (Binary Tree)
16Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç (Binary Tree) • Her düğümün en fazla iki çocuk düğüme sahip olduğu ağaç yapısına BT denir. • BT, bilgisayar bilimlerinde en çok kullanılan ağaç veri yapılarından olup, sıralı olması durumunda arama, ekleme ve silme işlemlerini çabuklaştırırlar. • Bir BT o Boş tek bir düğümden oluşabileceği gibi, o Sol alt ağaç ve sağ alt ağaç olmak üzere köke ait iki adet ikili ağaçtan da oluşabilir. • BT için gerek şart ilgili BT düğümünün en fazla iki çocuğa (alt ağaca) sahip olabileceğidir.
17Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç (Binary Tree) (devam…) A C D Z I K Kök P M Sağ alt ağaç A B A B İki farklı ikili ağaç
18Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Katı İkili Ağaç (Strict Binary Tree) • Yaprak düğümler haricindeki tüm düğümler sıfır veya iki çocuğa sahip ise katı ikili ağaç olarak adlandırılır. Katı İkili AğaçKatı Olmayan İkili Ağaç
19Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Tam İkili Ağaç (Full Binary Tree) • Her bir düğümün (i)net olarak iki çocuk düğüme sahip olduğu ve (ii)yaprak düğümlerin aynı seviyede olduğu iki ağaçtır. • Her düğüm eşit şekilde sağ ve sol alt-ağaçlara sahiptir.
20Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Eksiksiz İkili Ağaç (Complete Binary Tree) • Son seviye dışındaki tüm seviyelerin tam (full) olduğu ikili ağaç türüdür. • Düğümleri sol taraftan (düğüme göre) doldurulur. • Yeni bir derinliğe soldan sağa doğru ekleme başlanır.
21Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Eksiksiz İkili Ağaç (Complete Binary Tree) • Aşağıdaki örnekler, eksiksiz ikili ağaç kriterlerine uyuyor mu?
22Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç Özellikleri – Özellik 1 • Her k seviyesinde, maksimum düğüm sayısı 2k dır. • Kök düğümde k=0 olduğu için düğüm sayısı 1 olurken, • k=2 için maksimum düğüm sayısı 4 olur.
23Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç Özellikleri – Özellik 2 • h yüksekliğindeki ikili ağacın maksimum düğüm sayısı = 2h+1 - 1 olarak hesaplanır. • Aşağıdaki ağaç için h = 3 olduğundan maksimum düğüm sayısı 16 – 1 = 15 bulunur.
24Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç Özellikleri – Özellik 3 • h yüksekliğindeki ikili ağacın o minimum düğüm sayısı = h + 1 olarak hesaplanır. • Kök düğümün h = 0 da olduğuna dikkat ediniz. A C P P A C P P
25Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç Özellikleri – Özellik 4 • En az iki düğüme sahip, n elemanlı bir ikili ağaçta, kenar sayısı = (n - 1) olarak hesaplanır. • Aşağıdaki örneklerde 4’er düğüm ve 3’er kenar mevcuttur. A C P P A C P P
26Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç Özellikleri – Özellik 5 • n yaprak düğüme sahip, eksiksiz bir ikili ağaçta (complete), kenar sayısı (k) = 2(n-1)’dir.
27Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç Gerçekleştirimi • İki türlü gerçekleştirimi mümkündür: o Dizi kullanarak o Bağlı liste kullanarak
28Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Bağlı Liste İkili Ağaç Gerçekleştirimi
29Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Bağlı Liste İkili Ağaç Gerçekleştirimi (devam…) 4 6 12 45 7 kök 1
30Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Bağlı Liste İkili Ağaç Gerçekleştirimi (devam…) 4 6 12 45 7 kök 1 • Soru: Kökten itibaren düğümleri elimizde olan ikili ağaç üzerinde nasıl dolaşırız?
31Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç Üzerinde Gezinme (Traverse) • Bir ağacı bir düğüme sadece bir defa uğrayacak şekilde gezmeye gezinme/geçiş denir. • Gezinme, ağacın sakladığı bilgi türüne göre bir bilgiye ulaşma, listeleme ve başka amaçlarla gerçekleştirilir. • 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. • Örneğin; düğümlerin matematiksel operatörler ve oparandlar olduğu bir ikili ağacın gezinme işlemi, infix-postfix gibi bir notasyonu elde etmemizi sağlar.
32Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç Üzerinde Gezinme (devam…) • İkili ağacın üzerinde gezinilmesi sırasında bağımsız olarak 3 grup ikili ağaç parçasının 1. Kök 2. Sol alt ağaç 3. Sağ alt ağaç değişik sıralarda gezilmesiyle ile gerçekleşir.
33Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç Üzerinde Gezinme (devam…) • İkili ağaç üzerinde dolaşmak için 3 temel yol vardır. Bunlar: • Önce-kök/ziyaret (Preorder - NLR):  Kök/ziyaret, Sol, Sağ Önce kök, sonra sol alt ağaç ve ardından sağ alt ağaç • Ortada-kök/ziyaret (Inorder - LNR):  Sol, Kök/ziyaret, Sağ Önce sol alt ağaç, kök ve sağ alt ağaç • Sonra-kök/ziyaret (Postorder - LRN):  Sol, Sağ, Kök/ziyaret Önce sol alt ağaç, sağ alt ağaç ve kök.
34Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları İkili Ağaç Üzerinde Gezinme (devam…) A B C Q M H K L X P Örnek Ağaç
35Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Preorder ile Gezinme 1. Düğümü ziyaret et 2. Sol alt ağaçta gezin 3. Sağ alt ağaçta gezin Preorder Gezinme: a, b, d, c, e
36Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Preorder ile Gezinme (devam…)
37Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları A B C Q M H K L X P Preorder ile Gezinme (devam…) Preorder Gezinme: Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları
38Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Inorder ile Gezinme 1. Sol alt ağaçta gezin 2. Düğümü ziyaret et 3. Sağ alt ağaçta gezin Inorder Gezinme: b, d, a, e, c
39Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Inorder ile Gezinme (devam…)
40Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Inorder ile Gezinme (devam…) A B C Q M H K L X P Inorder Gezinme: Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları
41Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Postorder ile Gezinme 1. Sol alt ağaçta gezin 2. Sağ alt ağaçta gezin 3. Düğümü ziyaret et Postorder Gezinme: d, b, e, c, a
42Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Postorder ile Gezinme (devam…)
43 Postorder ile Gezinme (devam…) A B C Q M H K L X P Postorder Gezinme: Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları
44 Gezinme - Örnek 1 Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları
45 Gezinme - Örnek 2
46 Gezinmeler Ne İşe Yarar? Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Preorder: • Ağacın kopyasını elde etme • Düğümleri sayma • Yaprakları sayma • Matematiksel ifadeler için prefix gösterimini elde etme Postorder: • İkili ağacı silme • Fonksiyonel dil derleyicilerinde • Hesap makinesi programlarında • Postfix matematiksel ifadelerinin oluşturulmasında Inorder: • İkili Arama Ağacında (Binary Search Tree) ağaçtaki bilgiyi sıralı halde yazdırmada
47 İkili Ağaç Uygulamaları • Binary Search Tree (İkili Arama Ağacı): Birçok arama uygulamasında, • Binary Space Partition: Hemen hemen tüm 3D video oyunlarında, hangi nesnelerin render edilmesi gerektiğini belirlemede, • Binary Tries: Yüksek bant genişliğine sahip router cihazların router-tablolarını saklamada, • Hash Trees: P2P programlarında, imza doğrulamada • Heaps: Öncelik kuyruklarının daha etkin/verimli gerçekleştiriminde kullanılır. Öncelik kuyrukları işletim sisteminde prosesleri planlamak için kullanılır. Yapay zeka uygulamalarında A* yol bulma (path finding) algoritmasının gerçekleştiriminde Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları
48 İkili Ağaç Uygulamaları (devam…) • GGM Trees: Bir çok şifreleme uygulamasında, sözde rastgele sayıların ağacının oluşturulmasında • Treap: Kablosuz ağlarda ve bellek tahsisinde • T-tree: Bellek içi veritabanlarına (Datablitz, EXtremeDB, MySQL Cluster, Oracle TimesTen) ait işlemlerinde Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Stackoverflow tartışmasına bakınız…
49 İkili Ağaç Gerçekleştirimine Dair Sorular • Ağaçtaki düğüm sayısını nasıl bulurum? • Ağaçtaki yaprak sayısını nasıl bulurum? • Ağaç yüksekliğini nasıl bulurum? • İkili ağacın katı (strict) ikili ağaç olup olmadığını nasıl anlarım? • İkili ağaçtaki 2 yaprak düğümün en küçük ortak atasını nasıl bulurum (LCA – Lowest Common Ancestor)? • Inorder ve Preorder gezinme sonuçları verilen ikili ağacı nasıl oluştururum? • Inorder ve Postorder gezinme sonuçları verilen ikili ağacı nasıl oluştururum? Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları
50 Ağaçtaki Düğüm Sayısını Bulma Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları
51 Ağaçtaki Yaprak Sayısını Bulma Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları
52 İki Gezinme Sonucundan Ağaç Elde Etme Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları • Eğer Preorder sonuç verildiyse ilk düğüm köktür. • Eğer Postorder sonuç verildiyse son düğüm köktür. • Kök bulunduktan sonra, Inorder gezinmeye göre, kökün sol ve sağ tarafındaki düğümler; sol ve sağ alt ağaç olarak belirlenirler. • Aynı teknik yeni bulunan sol ve sağ alt ağaç için özyinelemeli (recursive) olarak uygulanır. • Gezinme sonuçlarından birisi mutlaka Inorder olmalıdır. Diğeri Preorder veya Postorder olabilir.
53 İki Gezinme Sonucundan Ağaç Elde Etme (devam…) Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları Inorder gezinme: 20 30 35 40 45 50 55 60 7 Preorder gezinme: 50 40 30 20 35 45 60 55 70 Soru: İkili ağacı elde ediniz.
İYİ ÇALIŞMALAR… Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları
Yararlanılan Kaynaklar • Ders Kitabı: • Data Structures through JAVA, V.V.Muniswamy • Yardımcı Okumalar: • Data Structures and Algorithms in Java, Narashima Karumanchi • Data Structures, Algorithms and Applications in Java, Sartaj Sahni • Algorithms, Robert Sedgewick Celal Bayar Üniversitesi – YZM 2116 Veri Yapıları

More Related Content

Yzm 2116 Bölüm 7 - Tree ve Binary tree - İkili Ağaç

  • 1. YZM 2116 Veri Yapıları Yrd. Doç. Dr. Deniz KILINÇ Celal Bayar Ãœniversitesi Hasan Ferdi Turgutlu Teknoloji Fakültesi Yazılım MühendisliÄŸi
  • 2. BÖLÃœM - 6 Bu bölümde, • AÄŸaç (Tree) Veri Yapısı GiriÅŸ • AÄŸaç VY Temel Kavramlar • Ä°kili AÄŸaç (Binary Tree) • Ä°kili AÄŸaç Özellikleri • Ä°kili AÄŸaç GerçekleÅŸtirim • Ä°kili AÄŸaç Ãœzerinde Gezinme (Traverse) • Preorder, Inorder, Postorder • Ä°kili AÄŸaç GerçekleÅŸtirimine Dair Sorular konusuna deÄŸinilecektir. Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları
  • 3. 3Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları • Verilerin birbirine sanki bir aÄŸaç yapısı oluÅŸturuyormuÅŸ gibi sanal olarak baÄŸlanmasıyla elde edilen hiyerarÅŸik yapıya sahip veri yapısıdır. • Aynı aile soyaÄŸacında olduÄŸu gibi hiyerarÅŸik bir yapısı vardır ve orada geçen birçok kavram buradaki aÄŸaç veri yapısında da tanımlıdır. • ÖrneÄŸin çocuk, kardeÅŸ düğüm, aile, ata gibi birçok kavram aÄŸaç veri yapısında da kullanılır. • Her biri deÄŸiÅŸik bir uygulamaya doÄŸal çözüm olan ikili aÄŸaç, kodlama aÄŸacı, sözlük aÄŸacı, kümeleme aÄŸacı gibi çeÅŸitli aÄŸaç ÅŸekilleri vardır; üstelik uygulamaya yönelik özel aÄŸaç ÅŸekilleri de çıkarılabilir. AÄŸaç VY GiriÅŸ
  • 4. 4Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları • 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. • AÄŸaçlar hiyerarÅŸik iliÅŸkileri göstermek için kullanılır. • Her aÄŸaç düğümlerden (node) ve kenarlardan (edge) oluÅŸur. • Her düğüm bir nesneyi gösterir. • Her kenar (baÄŸlantı) iki node arasındaki iliÅŸkiyi gösterir. • Arama iÅŸlemi baÄŸlı listelere göre çok hızlı yapılır. AÄŸaç VY GiriÅŸ (devam…)
  • 5. 5Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları AÄŸaç VY GiriÅŸ (devam…) • 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 ve saÄŸ baÄŸlar NULL olabilir. • Düğüm yapıları deÄŸiÅŸik türlerde bilgiler içeren veya birden fazla bilgi içeren aÄŸaçlar da olabilir.
  • 6. 6Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları • AÄŸaç veri yapısı / modeli aÅŸağıdaki yazılım uygulamalarında kullanılırlar: o Ä°ÅŸletim sisteminin dosya sistemini modellemekte o Oyunlar için farklı hamleleri ele almakta o AÄŸ routing (yönlendirme) algoritmalarında o Trie adı verilen VY ile sözlük oluÅŸturmakta ve dinamik yazım kontrolü gibi alanlarda o Huffman sıkıştırma kodlamasında ve o Derleyicilerde matematiksel ifadeleri modellemede kullanılırlar. AÄŸaç VY Kullanılan Yazılım Uygulamaları
  • 7. 7Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Örnek AÄŸaç Yapısı – Dosya Sistemi /yazilim kitaplar kodlar dersler yzm219 yzm112 ... 1.pdf 2.pdf 1.pdf 2015-2016 eskia.java b.java yzm2116 yzm317 yzm215 ... 1.ppt 1.doc 1.Pdf
  • 8. 8Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Örnek AÄŸaç Yapısı – Åžirket Organizasyonu
  • 9. 9Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları AÄŸaç VY Temel Kavramlar Level - Seviye 0 1 2 3 A B C D E F G Kök (root) Yaprak Düğüm Aile / Ara Düğüm Yaprak Düğüm 7 düğümlü aÄŸaç Çocuk Düğümler • A düğümü kök olmak üzere 7 düğümden (n) oluÅŸmaktadır. • Toplam 6 kenar (n-1) vardı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.
  • 10. 10Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları AÄŸaç VY Temel Kavramlar (devam…) • Düğüm (Node): AÄŸacın her elemanına verilen isim. • Kök (Root): AÄŸacın baÅŸlangıç düğümüdür. • Çocuk (Child): Bir düğüme doÄŸrudan baÄŸlı olan düğümlere o çocukları denilir. • KardeÅŸ Düğüm (Sibling): Aynı düğüme baÄŸlı düğümlere kardeÅŸ düğüm veya kısaca kardeÅŸ denir. • Aile (Parent): Düğümlerin doÄŸrudan baÄŸlı oldukları düğüm aile olarak adlandırılır; diÄŸer bir deyiÅŸle aile, kardeÅŸlerin baÄŸlı olduÄŸu düğümdür. • Ata (Ancestor): Aile düğümünün daha üstünde kalan düğümlere denir. • Torun (Dedscendant): Bir düğümün çocuÄŸuna baÄŸlı olan düğümlere denir.
  • 11. 11Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları AÄŸaç VY Temel Kavramlar (devam…) • Yaprak (Leaf): AÄŸacın en altında bulunan ve çocukları olmayan düğümlerdir. • Derece (Degree): Bir düğümden alt hiyerarÅŸiye yapılan baÄŸlantıların sayısıdır; yani çocuk veya alt aÄŸaç sayısıdır. • Seviye (Level): HiyerarÅŸik sıradır (rank). Kök düğüm seviye = 0. • Derinlik (Depth): Bir düğümün köke olan uzaklığı derinliktir. Kök düğüm derinlik = 0. • Yükseklik (Height): Bir düğümün kendi silsilesinden en uzak yaprak düğüme olan uzaklığıdır. Yaprak düğümlerin yükseliÄŸi = 0. (Kök yüksekliÄŸi = AÄŸaç YükesekliÄŸi) • Yol (Path): Bir düğümün aÅŸağıya doÄŸru (çocukları üzerinden) bir baÅŸka düğüme gidebilmek için üzerinden geçilmesi gereken düğümlerin listesidir.
  • 12. 12Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları AÄŸaç VY Temel Kavramlar (devam…) A B C D E F G Kök (Root) Tanım Kök B D Çocuk/Derece 2 0 0 KardeÅŸ 1 2 3 Seviye 0 1 2 Aile yok Kök C Ata yok yok Kök Yol A A, B A,C,D Derinlik 0 1 2 Yükseklik 3 0 0
  • 13. 13Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları AÄŸaç VY Temel Kavramlar (devam…) Düğüm sayısı: Yükseklik: Kök düğüm: Yapraklar: Seviye sayısı: H'nin ataları: B'nin torunları: E'nin kardeÅŸleri: 9 4 A C, D, F, H, I 4 E, B, A G, H, I D, F
  • 14. 14Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları AÄŸaçlara Özyinelemeli Yaklaşım • Rekürsif mantıkla bir aÄŸaç, bir kök (root) ve alt-aÄŸaçlar ÅŸeklinde tanımlanır. • 1 düğümü  2 ve 3 alt-aÄŸaçlarından oluÅŸur • 2 düğümü  4,6 ve 5 (5-9-10) olmak üzere üç alt-aÄŸaçtan oluÅŸur.
  • 15. 15Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç (Binary Tree)
  • 16. 16Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç (Binary Tree) • Her düğümün en fazla iki çocuk düğüme sahip olduÄŸu aÄŸaç yapısına BT denir. • BT, bilgisayar bilimlerinde en çok kullanılan aÄŸaç veri yapılarından olup, sıralı olması durumunda arama, ekleme ve silme iÅŸlemlerini çabuklaÅŸtırırlar. • Bir BT o BoÅŸ tek bir düğümden oluÅŸabileceÄŸi gibi, o Sol alt aÄŸaç ve saÄŸ alt aÄŸaç olmak üzere köke ait iki adet ikili aÄŸaçtan da oluÅŸabilir. • BT için gerek ÅŸart ilgili BT düğümünün en fazla iki çocuÄŸa (alt aÄŸaca) sahip olabileceÄŸidir.
  • 17. 17Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç (Binary Tree) (devam…) A C D Z I K Kök P M SaÄŸ alt aÄŸaç A B A B Ä°ki farklı ikili aÄŸaç
  • 18. 18Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Katı Ä°kili AÄŸaç (Strict Binary Tree) • Yaprak düğümler haricindeki tüm düğümler sıfır veya iki çocuÄŸa sahip ise katı ikili aÄŸaç olarak adlandırılır. Katı Ä°kili AÄŸaçKatı Olmayan Ä°kili AÄŸaç
  • 19. 19Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Tam Ä°kili AÄŸaç (Full Binary Tree) • Her bir düğümün (i)net olarak iki çocuk düğüme sahip olduÄŸu ve (ii)yaprak düğümlerin aynı seviyede olduÄŸu iki aÄŸaçtır. • Her düğüm eÅŸit ÅŸekilde saÄŸ ve sol alt-aÄŸaçlara sahiptir.
  • 20. 20Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Eksiksiz Ä°kili AÄŸaç (Complete Binary Tree) • Son seviye dışındaki tüm seviyelerin tam (full) olduÄŸu ikili aÄŸaç türüdür. • Düğümleri sol taraftan (düğüme göre) doldurulur. • Yeni bir derinliÄŸe soldan saÄŸa doÄŸru ekleme baÅŸlanır.
  • 21. 21Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Eksiksiz Ä°kili AÄŸaç (Complete Binary Tree) • AÅŸağıdaki örnekler, eksiksiz ikili aÄŸaç kriterlerine uyuyor mu?
  • 22. 22Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç Özellikleri – Özellik 1 • Her k seviyesinde, maksimum düğüm sayısı 2k dır. • Kök düğümde k=0 olduÄŸu için düğüm sayısı 1 olurken, • k=2 için maksimum düğüm sayısı 4 olur.
  • 23. 23Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç Özellikleri – Özellik 2 • h yüksekliÄŸindeki ikili aÄŸacın maksimum düğüm sayısı = 2h+1 - 1 olarak hesaplanır. • AÅŸağıdaki aÄŸaç için h = 3 olduÄŸundan maksimum düğüm sayısı 16 – 1 = 15 bulunur.
  • 24. 24Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç Özellikleri – Özellik 3 • h yüksekliÄŸindeki ikili aÄŸacın o minimum düğüm sayısı = h + 1 olarak hesaplanır. • Kök düğümün h = 0 da olduÄŸuna dikkat ediniz. A C P P A C P P
  • 25. 25Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç Özellikleri – Özellik 4 • En az iki düğüme sahip, n elemanlı bir ikili aÄŸaçta, kenar sayısı = (n - 1) olarak hesaplanır. • AÅŸağıdaki örneklerde 4’er düğüm ve 3’er kenar mevcuttur. A C P P A C P P
  • 26. 26Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç Özellikleri – Özellik 5 • n yaprak düğüme sahip, eksiksiz bir ikili aÄŸaçta (complete), kenar sayısı (k) = 2(n-1)’dir.
  • 27. 27Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç GerçekleÅŸtirimi • Ä°ki türlü gerçekleÅŸtirimi mümkündür: o Dizi kullanarak o BaÄŸlı liste kullanarak
  • 28. 28Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları BaÄŸlı Liste Ä°kili AÄŸaç GerçekleÅŸtirimi
  • 29. 29Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları BaÄŸlı Liste Ä°kili AÄŸaç GerçekleÅŸtirimi (devam…) 4 6 12 45 7 kök 1
  • 30. 30Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları BaÄŸlı Liste Ä°kili AÄŸaç GerçekleÅŸtirimi (devam…) 4 6 12 45 7 kök 1 • Soru: Kökten itibaren düğümleri elimizde olan ikili aÄŸaç üzerinde nasıl dolaşırız?
  • 31. 31Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç Ãœzerinde Gezinme (Traverse) • Bir aÄŸacı bir düğüme sadece bir defa uÄŸrayacak ÅŸekilde gezmeye gezinme/geçiÅŸ denir. • Gezinme, aÄŸacın sakladığı bilgi türüne göre bir bilgiye ulaÅŸma, listeleme ve baÅŸka amaçlarla gerçekleÅŸtirilir. • 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. • ÖrneÄŸin; düğümlerin matematiksel operatörler ve oparandlar olduÄŸu bir ikili aÄŸacın gezinme iÅŸlemi, infix-postfix gibi bir notasyonu elde etmemizi saÄŸlar.
  • 32. 32Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç Ãœzerinde Gezinme (devam…) • Ä°kili aÄŸacın üzerinde gezinilmesi sırasında bağımsız olarak 3 grup ikili aÄŸaç parçasının 1. Kök 2. Sol alt aÄŸaç 3. SaÄŸ alt aÄŸaç deÄŸiÅŸik sıralarda gezilmesiyle ile gerçekleÅŸir.
  • 33. 33Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç Ãœzerinde Gezinme (devam…) • Ä°kili aÄŸaç üzerinde dolaÅŸmak için 3 temel yol vardır. Bunlar: • Önce-kök/ziyaret (Preorder - NLR):  Kök/ziyaret, Sol, SaÄŸ Önce kök, sonra sol alt aÄŸaç ve ardından saÄŸ alt aÄŸaç • Ortada-kök/ziyaret (Inorder - LNR):  Sol, Kök/ziyaret, SaÄŸ Önce sol alt aÄŸaç, kök ve saÄŸ alt aÄŸaç • Sonra-kök/ziyaret (Postorder - LRN):  Sol, SaÄŸ, Kök/ziyaret Önce sol alt aÄŸaç, saÄŸ alt aÄŸaç ve kök.
  • 34. 34Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Ä°kili AÄŸaç Ãœzerinde Gezinme (devam…) A B C Q M H K L X P Örnek AÄŸaç
  • 35. 35Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Preorder ile Gezinme 1. Düğümü ziyaret et 2. Sol alt aÄŸaçta gezin 3. SaÄŸ alt aÄŸaçta gezin Preorder Gezinme: a, b, d, c, e
  • 36. 36Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Preorder ile Gezinme (devam…)
  • 37. 37Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları A B C Q M H K L X P Preorder ile Gezinme (devam…) Preorder Gezinme: Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları
  • 38. 38Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Inorder ile Gezinme 1. Sol alt aÄŸaçta gezin 2. Düğümü ziyaret et 3. SaÄŸ alt aÄŸaçta gezin Inorder Gezinme: b, d, a, e, c
  • 39. 39Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Inorder ile Gezinme (devam…)
  • 40. 40Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Inorder ile Gezinme (devam…) A B C Q M H K L X P Inorder Gezinme: Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları
  • 41. 41Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Postorder ile Gezinme 1. Sol alt aÄŸaçta gezin 2. SaÄŸ alt aÄŸaçta gezin 3. Düğümü ziyaret et Postorder Gezinme: d, b, e, c, a
  • 42. 42Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Postorder ile Gezinme (devam…)
  • 43. 43 Postorder ile Gezinme (devam…) A B C Q M H K L X P Postorder Gezinme: Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları
  • 44. 44 Gezinme - Örnek 1 Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları
  • 46. 46 Gezinmeler Ne Ä°ÅŸe Yarar? Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Preorder: • AÄŸacın kopyasını elde etme • Düğümleri sayma • Yaprakları sayma • Matematiksel ifadeler için prefix gösterimini elde etme Postorder: • Ä°kili aÄŸacı silme • Fonksiyonel dil derleyicilerinde • Hesap makinesi programlarında • Postfix matematiksel ifadelerinin oluÅŸturulmasında Inorder: • Ä°kili Arama AÄŸacında (Binary Search Tree) aÄŸaçtaki bilgiyi sıralı halde yazdırmada
  • 47. 47 Ä°kili AÄŸaç Uygulamaları • Binary Search Tree (Ä°kili Arama AÄŸacı): Birçok arama uygulamasında, • Binary Space Partition: Hemen hemen tüm 3D video oyunlarında, hangi nesnelerin render edilmesi gerektiÄŸini belirlemede, • Binary Tries: Yüksek bant geniÅŸliÄŸine sahip router cihazların router-tablolarını saklamada, • Hash Trees: P2P programlarında, imza doÄŸrulamada • Heaps: Öncelik kuyruklarının daha etkin/verimli gerçekleÅŸtiriminde kullanılır. Öncelik kuyrukları iÅŸletim sisteminde prosesleri planlamak için kullanılır. Yapay zeka uygulamalarında A* yol bulma (path finding) algoritmasının gerçekleÅŸtiriminde Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları
  • 48. 48 Ä°kili AÄŸaç Uygulamaları (devam…) • GGM Trees: Bir çok ÅŸifreleme uygulamasında, sözde rastgele sayıların aÄŸacının oluÅŸturulmasında • Treap: Kablosuz aÄŸlarda ve bellek tahsisinde • T-tree: Bellek içi veritabanlarına (Datablitz, EXtremeDB, MySQL Cluster, Oracle TimesTen) ait iÅŸlemlerinde Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Stackoverflow tartışmasına bakınız…
  • 49. 49 Ä°kili AÄŸaç GerçekleÅŸtirimine Dair Sorular • AÄŸaçtaki düğüm sayısını nasıl bulurum? • AÄŸaçtaki yaprak sayısını nasıl bulurum? • AÄŸaç yüksekliÄŸini nasıl bulurum? • Ä°kili aÄŸacın katı (strict) ikili aÄŸaç olup olmadığını nasıl anlarım? • Ä°kili aÄŸaçtaki 2 yaprak düğümün en küçük ortak atasını nasıl bulurum (LCA – Lowest Common Ancestor)? • Inorder ve Preorder gezinme sonuçları verilen ikili aÄŸacı nasıl oluÅŸtururum? • Inorder ve Postorder gezinme sonuçları verilen ikili aÄŸacı nasıl oluÅŸtururum? Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları
  • 50. 50 AÄŸaçtaki Düğüm Sayısını Bulma Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları
  • 51. 51 AÄŸaçtaki Yaprak Sayısını Bulma Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları
  • 52. 52 Ä°ki Gezinme Sonucundan AÄŸaç Elde Etme Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları • EÄŸer Preorder sonuç verildiyse ilk düğüm köktür. • EÄŸer Postorder sonuç verildiyse son düğüm köktür. • Kök bulunduktan sonra, Inorder gezinmeye göre, kökün sol ve saÄŸ tarafındaki düğümler; sol ve saÄŸ alt aÄŸaç olarak belirlenirler. • Aynı teknik yeni bulunan sol ve saÄŸ alt aÄŸaç için özyinelemeli (recursive) olarak uygulanır. • Gezinme sonuçlarından birisi mutlaka Inorder olmalıdır. DiÄŸeri Preorder veya Postorder olabilir.
  • 53. 53 Ä°ki Gezinme Sonucundan AÄŸaç Elde Etme (devam…) Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları Inorder gezinme: 20 30 35 40 45 50 55 60 7 Preorder gezinme: 50 40 30 20 35 45 60 55 70 Soru: Ä°kili aÄŸacı elde ediniz.
  • 54. Ä°YÄ° ÇALIÅžMALAR… Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları
  • 55. Yararlanılan Kaynaklar • Ders Kitabı: • Data Structures through JAVA, V.V.Muniswamy • Yardımcı Okumalar: • Data Structures and Algorithms in Java, Narashima Karumanchi • Data Structures, Algorithms and Applications in Java, Sartaj Sahni • Algorithms, Robert Sedgewick Celal Bayar Ãœniversitesi – YZM 2116 Veri Yapıları