Veri Yapıları - Ders Notu - Süper
Transkript
Veri Yapıları - Ders Notu - Süper
Week 9: Trees 1. TREE KAVRAMI 2. İKİLİ AĞAÇ VE SUNUMU 3. İKİLİ AĞAÇ DİZİLİMİ 4. İKİLİ ARAMA AĞACI < 2 1 6 9 > 4 = 8 1. TREES KAVRAMI Bir ağaç bir veya daha fazla düğümün (T) bir kümesidir : – – Spesifik olarak tasarlanmış root isimli bir düğümü vardır Geriye kalan düğümler her biri bir ağaç olan T1, T2,…,Tn gibi birbirinden ayrık n adet düğümler kümesine ayrılır. 1. TREES KAVRAMI Example 1. TREES KAVRAMI Bir ağaç değildir Ağaç 1. TREES KAVRAMI: Biraz terminoloji Root (kök) Child (left,right) (evlat) Parent (ebeveyn) Leaf node (yaprak) Subtree (alt ağaç) Ancestor of a node (bir düğümün atası) Descendant of a node (bir düğümün soyundan) 1. TREES KAVRAMI Bir ağacın bir düğümünün derecesi – Bir ağacın bir düğümünün derecesi, kökü bu düğüm olan alt ağaçların sayısıdır. Bir ağacın derecesi – Bir ağacın derecesi ağacın derecesi olarak tanımlanır. düğümlerinin maksimum Bir düğümün seviyesi – Kök düğüm 1 olmak üzere, kökten aşağı doğru 1’er artar. 2. İKİLİ AĞAÇ VE SUNUMU İKİLİ AĞAÇ – Hiçbir düğümün derecesi ikiden fazla değildir. – i. Seviye için maksimum düğüm sayısı 2i−1’dir. – Eğer ağacın derinliği k ise o zaman ağaçtaki bütün düğümlerin sayısı – 2k − 1 = 2k−1 + 2k−2 + … + 20 olacaktır. 2. İKİLİ AĞAÇ VE SUNUMU İKİLİ AĞAÇ – Tam dolu bir ikili ağaç 2k − 1 düğümü olan bir ikilidir. – Eğer düğüm sayısı < 2k − 1 ise, o tam dolu bir ikili ağaç değildir. N düğümü olan bir tam ağacın yüksekliği (h) nedir? 2 −1 = N h ⇒ 2 = N +1 h ⇒ h = log( N + 1) → O(log N ) N düğümlü bir ağacın maksimum yüksekliği N (bağlı liste gibi) N düğümlü bir ağacın minimum yüksekliği log(N+1) 2. İKİLİ AĞAÇ VE SUNUMU Tam ikili ağaç 3=22-1 7=23-1 15=24-1 2. İKİLİ AĞAÇ VE SUNUMU struct node { int data; node *left; node *right; }; Ağaç dizilimi Bir ağaçta belirli bir sırada veri yazdırmak için kullanılır. – – – inorder (LDR ) Postorder (LRD ) preorder (DLR ) Pre-order dizilimi – – – Kökteki veriyi yazdır Yinelemeli olarak sol alt ağaçtaki bütün verileri yazdır. Yinelemeli olarak sağ alt ağaçtaki bütün verileri yazdır. Preorder, Postorder and Inorder Preorder dizilimi – – düğüm, sol, sağ Ön ek ifadesi ++a*bc*+*defg Preorder, Postorder and Inorder Postorder dizilimi – – sol, sağ, düğüm Son ek ifadesi abc*+de*f+g*+ İçinde dizilimi – – sol, düğüm, sağ. Orta ek ifadesi a+b*c+d*e+f*g Preorder, Postorder and Inorder 3. İKİLİ AĞAÇ DİZİLİMİ 3. İKİLİ AĞAÇ DİZİLİMİ Inorder = DBEAC Aynı sonucu veren birden çok ağaç olabilir. 4. İKİLİ ARAMA AĞACI Bir ikili arama ağacı – – – – – İkili bir ağaçtır (boş olabilir) Her düğüm bir tanımlayıcı içermelidir. Sol alt ağaçtaki bir düğümün tanımlayıcısı kök düğümdeki tanımlayıcıdan daha küçüktür. Sağ alt ağaçtaki herhangi bir düğümün tanımlayıcısı kök düğümdeki tanımlayıcıdan büyüktür. Hem sol alt ağaç hem de sağ alt ağaç ikili bir arama ağacıdır. 4. İKİLİ ARAMA AĞACI İkili arama ağacı. İkili arama ağaçları İkili arama ağacı İkili arama ağacı değil İkili arama ağacı Aynı kümeyi sunan iki ikili arama ağacı : neden farklı? Performans N elemanı olan bir sözlüğün h yüksekliğine sahip bir ikili ağaç ile sunulduğunu var sayalım. – – Kullanılan bellek uzayı O(n) find, insert ve remove metotları O(h) zamanda yapılır. h yüksekliği için worst case O(n) ve best case O(log n) olarak ölçülür. 4. İKİLİ ARAMA AĞACI Neden ikili arama ağacı kullanırız – – inorder dizilimi: sıralı liste arama daha hızlı gerçekleşir Fakat.. – Ekleme, silme: yavaştır Önemli konu: Veritabanı sistemindeki Index mekanizması – Index özelliğinin doğru şekli kullanarak sorun çözülür. Arama Algorithm TreeSearch(k, v) if (v ==NULL) return v Bir k değerini aramak için, if k < key(v) kökten başlayarak aşağı return TreeSearch(k, T.left(v)) doğru tararız. else if k = key(v) Bir sonraki düğümün ne return v olacağı karşılaştırma else { k > key(v) } sonrasına bağlı olarak değişir. return TreeSearch(k, T.right(v)) Eğer bir yaprağa 6 ulaştığımız halde aranan < eleman bulunamadıysa 2 9 null döndürürüz. > Örnek: find(4): 8 1 4 = – TreeSearch(4,root) Ekleme inser(k, o) işlemini yerine getirmek için, biz önce anahtar değerini (k) ararız (TreeSearch kullanarak) Varsayalım ki son yaprağa vardığımız halde k hala bulunamadı Anahtar (k) değeri w düğümüne ekleriz ve ağacı bir düğüm genişletiriz. Örnek: insert 5 6 < 2 9 > 1 4 8 > w 6 2 1 9 4 8 w 5 4. İKİLİ ARAMA AĞACI Yeni düğüm ekle 4. İKİLİ ARAMA AĞACI Yeni düğüm ekle void InsertNode(node* &root, node *newnode) { if (root==NULL) root=newnode; else if ((root->data)>(newnode->data)) InsertNode(root->l,newnode); else if (root->data<newnode->data) InsertNode(root->r,newnode); } Insert node Insert node Insert Order
Benzer belgeler
Bilkent University Computer Engineering Department
The corresponding pi values for 1 ≤ i ≤ n pi: probability of searching for key Ki
Detaylı