İkili Ağaç Yapıları

Ağaç Yapıları (Tree Structures) Kütük Organizasyonu 1 İçerik Temel Kavramlar Ağaçlarda Dolaşım İkili Ağaçlar (Binary Trees) İkili Arama Ağacı (Binary Search Tree ve Temel İşlemler Kütük Organizasyonu 2 Bilgisayar bilimlerinde yer alan önemli veri yapılarından bir tanesi de ağaçlardır. Ağaç yapılarını önemli yapan özellikler : Esneklik : Tek bir amaç için en iyi çözüm ağaç yapısı olmasa da, çoklu çözümler için ağaç yapısının esnekliği bu yapının avantajı olarak sayılabilir. Etkili Arama: Arama sırasında ağacın bazı dalları budanarak arama yapılması performans artışı sağlar ve bu da verimliliği arttırır. Ağaç yapısı genellikle bilginin istenilen bölümüne konumlanmak için genellikle filtreleme aracı olarak kullanılır. Doğal Temsil: Bilgiyi temsil etmenin doğal bir yoludur. Ağaç yapısı bir uygulamayı bazen daha kolay uygulanabilir bir hale dönüştürür. Kütük Organizasyonu 3 Ağaçlar (Trees) Ağaçlar düğümlerin kolleksiyonudur. Ağaç, eğer boş değilse birbirinden farklı r tane düğüme, T1, T2 ve Tn ile ifade edilebilecek olan alt ağaçlara sahiptir. Kütük Organizasyonu 4 Bazı Temel Kavramlar Çocuk ve Aile : Kök (root) haricindeki her düğümün bir ailesi vardır. Yaprak: Herhangi bir çocuğu bulunmayan düğümlerdir. Kardeş: Aynı aileye sahip olan düğümlerdir. Kütük Organizasyonu 5 Bazı Temel Kavramlar (Devam) Yol(Path) : Ardışık kenarlardır. Yol Uzunluğu (Length of Path) : Yol içerisindeki kenarların toplamıdır. Bir düğümün derinliği (Depth of a node) : Kökten düğüme kadar olan eşsiz yolun uzunluğudur. Bir düğümün boyu (Height of a node) : Bir düğümden yaprağa kadar olan en uzun yolun uzunluğudur. Yaprakların boyu 0’dır. Bir ağacın boyutu = Kök düğümün yüksekliği = En dipteki yaprağın derinliğidir. Baba-Oğul (Ata-Torun) : Eğer n1’den n2’ye doğru bir yol var ise, n2 n1’in babası (atası); n1 ise n2’nin oğulu veya torunudur. Kütük Organizasyonu 6 Örnek Bu yapıda operandlar yaprakları, operatörler ise dahili düğümleri oluşturmaktadır. Kütük Organizasyonu 7 Ağaç İçerisinde Hareket (Traversal) Ağaç yapısı üzerinde herhangi bir düğüme erişme sürecimize ağacı gezmek (traverse) denir. Bir ağacı ençok bilinen üç değişik yöntemle gezebiliriz : i)Kökten başlayarak (Preorder) ii)Sondan başlayarak (Postorder) iii)Sıralı (Inorder) Kütük Organizasyonu 8 Kökten Başlayarak Dolaşım (Preorder Traversal) İlk adımda köke uğranır(d). Sol alt ağaç kökten başlayarak dolaşılır (b-a-c). Son adımda sol alt ağaç kökten başlayarak dolaşılır (f-e-g). Sonuçta ağaç sırasıyla d-b-a-c-f-e-g düğümlerine erişilerek gezilir. Kütük Organizasyonu 9 Örnek Yukarıda verilen ağaç yapısında kökten başlayarak (preorder) bir dolaşım izlenirse düğümler hangi sırayla erişilerek gezilmiş olur? Kütük Organizasyonu 10 Örnek ++a*bc*+*defg şeklinde bir sıra izlenir. Kütük Organizasyonu 11 Sondan Başlayarak Dolaşım (Postorder Traversal) İlk adımda sol alt ağaç sondan başlayarak dolaşılır (a-c-b). İkinci adımda sağ alt ağaç sondan başlayarak dolaşılır (e-g-f). Son adımda ise köke uğranır(d). Sonuçta ağaç sırasıyla a-c-b-e-g-f-d düğümlerine erişilerek gezilir. Kütük Organizasyonu 12 SıralıDolaşım (Inorder Traversal) İlk adımda sol alt ağaç sıralı şekilde dolaşılır (a-b-c). Kök düğüme uğranır (d). Son adımda sağ alt ağaç sıralı şekilde dolaşılır (e-f-g). Sonuçta ağaç sırasıyla a-b-c-d-e-f-g düğümlerine erişilerek gezilir. Kütük Organizasyonu 13 İkili Ağaç Yapıları (Binary Tree Structures) Kütük Organizasyonu 14 Binary Tree Düğümlerinin en fazla 2 çocuğa sahip olduğu ağaç yapısıdır. Ortalama bir binary tree’nin derinliği genel olarak N’den küçüktür. Fakat en kötü durumda derinliği N-1 kadardır. Kütük Organizasyonu 15 Kütük Organizasyonu 16 Binary Search Tree (BST) Her X dü ğümü için; Sol taraftaki alta ğaçta yer alan anahtar de ğerleri her zaman için X’in de ğerinden küçüktür. Sa ğ taraftaki alta ğaçta yer alan anahtar de ğerleri her zaman için X’in de ğerinden büyüktür. Kütük Org anizasyo n u 17 a) b) a) Şeklinde yer alan ağaç bir ikili bir arama ağacı iken b) şeklinde yer alan ağaç ise binary tree değildir. Kütük Organizasyonu 18 Aynı anahtar setleri farklı ikili ağaçlar oluşturabilir. Kütük Organizasyonu 19 İkili Ağaçlarda Arama Eğer aranılan sayı 15 ise hemen erişilmiş olur. Eğer aranılan sayı 15’den küçük ise, sol taraftaki ağaca, Eğer aranılan sayı 15’den büyük ise, sağ taraftaki ağaca bakılır. Kütük Organizasyonu 20 Örnek Kütük Org anizasyo n u 21 BST’yi Sıralı Biçinde Dolaşmak İkili arama ağacını sıralı bir biçimde dolaşmak anahtar değerlerinin sıralı bir şekilde elde edilmesini sağlar. Inorder: 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 Kütük Organizasyonu 22 BST’ye Anahtar Eklemek İkili arama a ğacına yeni bir anahtar de ğeri eklenece ği zaman izlenecek adımlar herhangi bir anahtarı bulmak için izlenecek olan adımlar ile aynıdır. Örn: A ş a ğıdaki a ğaca 13 de ğeri eklenmesi durumunda; Kütük Org anizasyo n u 2 3 BST’ye Anahtar Silmek İkili arama a ğacında herhangi bir dü ğüm silindi ğinde bu dü ğüme ba ğlı olan çocukların dikkate alınması gerekmektedir. 3 farklı durum söz konusudur : i) Silinecek olan dü ğüm yaprak ise silme i şlemi hemen gerçekle ştirilir. ii) Silinecek olan dü ğüm e ğer bir çocu ğa sahip ise, o dü ğümün atasının pointer bilgisini alt dü ğüme (çocu ğa) aktarmak gerekir. Kütük Org anizasyo n u 2 4 iii) Silinecek olan düğüm eğer iki çocuğa sahip ise, silinen düğümün yerine o düğümün sağ alt ağacındaki en küçük anahtar değeri getirilir. Daha sonra ise sağ alt ağaçtan taşınan anahtar değeri silinir. Kütük Organizasyonu 25 Dosya Yapılarında İkili Arama Ağaçlarının Kullanılması Kütük Organizasyonu 26 Indexed Sequential File Organization ağaç yapısını kullanmaktadır. Bu ağaç yapısı hem sıralı hem de rastgele olan erişimlerde kullanılmaktadır. Index sequential dosyalarda ağaç sadece index amacı için kullanılır. Kayıtlar yapraklarda saklanır. İkili arama ağaçlarında ise bilgi hem yapraklarda hem de dahili düğümlerde saklanmaktadır. Saklanan bilgi arttıkça ikili arama ağacının yüksekliği artar ve sonuç itibarıyla performansta düşüşler görülür. Kütük Organizasyonu 27 İkili arama ağaçlarında Braching Factor 2’dir. Index sequential dosyalarda ise branching factor daha fazla olduğu için çok sayıda bilginin saklandığı durumlarda sıralı ve doğrudan erişimlerde performans yüksektir. Örnek Örnek: Dallas, Oakland, Pittsburg, Miami, Chicago, Denver, Boston ve Spivey’s Corner kayıtlarını ikili arama ağacında saklamak istiyelim. Bu yapıda herhangi bir kayda ulaşmak için gerekli olan ortalama probe sayısı 2,75’dir. Kütük Organizasyonu 28 İkili ağacın yapısı, bilgilerin eklenme sırasına bağlıdır. Alfabetik sırayla ekleme yapıldığında ağacın yapısı bağlı listeye dönüşür. Bu durumda ise eklenmesi sırasında sürekli olarak ağacın dengenlenmesi gerekir. Bu yapıda herhangi bir kayda ulaşmak için gerekli olan ortalama probe sayısı 4,5’dir. Dengeleme işlemi için geliştirilmiş bir diğer ikili ağaç yapısı ise AVL ağacıdır. Bu ağaç performansı arttırmak için sürekli olarak kendisini yeniden düzenlemektedir. Kütük Organizasyonu 29 AVL Ağaçları (AVLTree Structures) Kütük Organizasyonu 30 İkili Ağaç Yapılarında Denge AVL (Adelson-Velskii-Landis) ağacı, ikili arama ağacı olup bir node’un alt ağaçlarının yükseklikleri yaklaşık aynıdır. Bu yüzden aynı zamanda height balanced tree olarak da bilinirler. En kötü durumda ikili arama ağacının karmaşıklığı O(N-1)’dir. İkili arama ağacının boyunun olabildiğince kısa olması arzu edilir. Kütük Organizasyonu 31 Dengeli Ağaç (Balanced Tree) Kök düğümün sağ ve sol altağaçları aynı boyda olmalıdır. Her bir düğümün sağ ve sol altağaçları aynı boyda olmalıdır. AVL ağacında bilinmesi gereken bir kavram denge faktörüdür. (Balance Factor) Balance Factor = Height (right subtree) - Height (letf subtree) Denge faktörünün -1,0,1 arasında değerler alabilir. (1’den büyük olması söz konusu değildir). Kütük Organizasyonu 32 AVL property violated here AVL tree Balance Factor = 2-3 = |-1| =1 Balance Factor = 1-3 = |-2| =2 Sol taraftaki ağaç dengeli bir yapı sergilerken (balance-factor=1); sağ kesimdeki ağaç ise dengesizdir (balance-factor =2) Dikkat edilmesi gereken önemli bir nokta herhangi bir düğümün denge faktörü hesaplanırken sol ve sağ ağaçların yüksekliklerinin belirlenmesidir. Yoksa herhangi bir kayıt için düğümlerin sayılması değildir. Kütük Organizasyonu 33 Smallest AVL tree of height 7 Smallest AVL tree of height 8 Smallest AVL tree of height 9 Kütük Organizasyonu 34 AVL Ağaçlarında Anahtar Ekleme Herhangi bir kaydın eklenmesi normal ikili ağaçta olduğu gibidir. Fakat, ekleme işleminde ekleme yapılan düğümden köke kadar olan yol üzerindeki bütün düğümlerin denge faktörleri hesaplanır. Eğer sonuç ağaç dengeli bir yapıda değil ise, ağacı dengeli bir hale getirmek için 1 veya 2 döndürme (Rotation) gerekir. 6 7 6 8 Original AVL tree Insert 6 Property violated Restore AVL property Kütük Organizasyonu 35 Dengeleme İşlemi Dengelenecek olan düğüm x olarak gösterilsin. Bu durumda 4 farklı durum söz konusudur. i) Yeni kayıt, x düğümünün sol alt ağacının sol çocuğuna eklenebilir. ii) Yeni kayıt, x düğümünün sağ alt ağacının sol çocuğuna eklenebilir. iii) Yeni kayıt, x düğümünün sol alt ağacının sağ çocuğuna eklenebilir. iv) Yeni kayıt, x düğümünün sağ alt ağacının sağ çocuğuna eklenebilir. Görüldüğü gibi 1. durum ile 3 durum ve 2. durum ile 4 durum birbirlerinin simetrikleridir. Kütük Organizasyonu 36 Döndürme İşlemi (Rotations) Eğer ekleme işlemi ağacı dış kısmında oluyorsa (sağ ağacın sağına veya sol ağacın soluna gibi) tek bir döndürme yeterlidir. Eğer ekleme işlemi ağacı iç kısmında oluyorsa (sağ ağacın soluna veya sol ağacın sağına gibi) tek bir döndürme yeterlidir. Kütük Organizasyonu 37 I) Tek Sefer Döndürme (Single Right Rotation) Örn: Eklenecek olan yeni kayıt sol alt a ğacın sol kesimine (X alt a ğacına) eklenecek olsun. k2 dengesizle şir Bu durumda, sa ğ tarafa do ğru tek bir döndürme i şlemi gerçekle ştirilir. (Single Right Rotation –SRR). Bu işlem daha önce bahsedilen durumlardan birincisine örnek olarak verilebilir. Kütük Org anizasyo n u 3 8 Eklenecek olan yeni kayıt sol alt ağacın sol kesimine eklenerek kök düğümün dengesini bozduğu durumlarda (Denge faktörünün 1’den fazla olduğu durumlada) sağa doğru 1 kere döndürme yapılarak ağaç dengelenir. k2 k1 X k1 X k2 6 anahtarı eklendiğinde 8 anahtarının bulunduğu durum dengesizleştiğinden ağaç sağa doğru 1 defa döndürülür. Kütük Organizasyonu 39 IV) Tek Sefer Döndürme (Single Left Rotation) Örn: Eklenecek olan yeni kayıt sa ğ alt a ğacın s a ğ kesimine (Z alt a ğacına) eklenecek olsun. k1 dengesizle şir. Bu durumda, sol tarafa do ğru tek bir döndürme i şlemi gerçekle ştirilir. (Single Left Rotation –SLR). Bu i şlem daha önce bahsedilen durumlardan dördüncüsüne örnek olarak verilebilir. Kütük Org anizasyo n u 4 0 Aşağıdaki işlem adımları tek seferlik döndürme işlemine (SRR-SLR) örnektir. Sırayla 3, 2, 1, 4, 5, 6 anahtarlarını AVL ağacına ekleyelim. 2 1 4 3 5 3 2 2 1 3 Single rotation 2 1 3 4 4 eklenmesi 2 1 3 4 5 5 eklenmesi, 3 nolu düğümde dengeyi bozar. Kütük Organizasyonu 41 2 1 4 3 5 6 6 eklenmesi, 2 nolu düğümdeki dengeyi bozar. 4 2 5 1 3 6 3 2 1 1’in eklenmesi 3. düğümdeki dengeyi bozar. Örnek Single rotation Single rotation II) İki Sefer Döndürme Eklenecek olan yeni kayıt, x düğümünün sağ alt ağacının sol çocuğuna eklendiğinde tek bir seferlik bir döndürme işlemi gerçekleştirmek ağacın dengeye gelmesini sağlamayacaktır. Bu yüzden 2 aşamalı bir döndürme işlemi gerçekleştirilmelidir. Kütük Organizasyonu 42 C A T1 T2 T3 Kütük Organizasyonu 43 C B T1 T2 T3 A T4 B T4 SLR SRR C B T3 A T3 T4 T4 C düğümü sola doğru dengesiz bir durumdadır. A düğümünün sağ kesimi ise daha ağırdır. Ağacı dengeli AVL ağacına dönüştürmek içn ard arda SLR ve SRR dönüşümleri yapılır. III) İki Sefer Döndürme Eklenecek olan yeni kayıt, x düğümünün sol alt ağacının sağ çocuğuna eklendiğinde tek bir seferlik bir döndürme işlemi gerçekleştirmek ağacın dengeye gelmesini sağlamayacaktır. Bu yüzden II. durumda gerçekleştirilen döndürme işleminin simetriği gerçekleştirilir. Kütük Organizasyonu 44 A C T3 T4 T2 B T1 A B T2 T3 T4 C T1 SRR A düğümü sağa doğru SLR dengesiz bir durumdadır. C düğümünün sol kesimi ise daha ağırdır. Ağacı dengeli AVL ağacına dönüştürmek içn ard arda SRR ve SLR dönüşümleri yapılır. C B T3 A T1 T2 T4 Kütük Organizasyonu 45 Sırayla 7, 16, 15, 14, 13, 12, 11, 10, 8, 9 anahtarlarını ağacımıza ekliyelim. Örnek Bir önceki örnekte oluşturduğumuz ağaca yeni anahtarlar ekleyelim. 4 2 5 1 3 6 7 4 2 6 1 3 5 7 7 anahtarının eklenmesi 5 numaralı düğümde dengesizliğe neden olur. Single rotation Kütük Organizasyonu 46 4 2 6 1 3 5 7 16 16 anahtarının 15 eklenmesinde herhangi bir problem yok iken 15 anahrarının eklenmesiyle 7 numaralı düğümde dengesizlik meydana gelir. 4 2 6 1 3 5 16 15 7 Tekli döndürme ile çözüm almak mümkün değildir. Hala dengesiz durum devam etmektedir. 4 2 6 1 3 5 15 7 16 İkili Döndürme Yapılırk1 k2 k3 Kütük Organizasyonu 47 4 2 6 1 3 5 15 7 16 14 14 anahtarının eklenmesi 4 2 7 1 3 6 15 14 16 k1 k2 A k3 Kütük Organizasyonu 48 k2 k3 5 k1 D C İkili Döndürme 4 2 7 1 3 6 15 5 14 16 7 4 15 2 6 14 16 1 3 5 13 Tekli Döndürme k1 X Y k2 13 anahtarını n eklenmesi Z 7 4 13 2 6 12 15 1 3 5 11 14 16 10 7 4 13 2 6 11 15 1 3 5 10 12 14 16 10 anahtarı ekleniyor Tekli Döndürme Kütük Organizasyonu 49 7 4 13 2 6 11 15 1 3 5 10 12 14 16 8 9 8 ve adrından 9 ekleniyor. 7 4 13 2 6 11 15 1 3 5 8 12 14 16 9 10 Tekli Döndürme Dosya Yapılarında AVL Ağaçlarının Kullanılması Kütük Organizasyonu 50 Örnek Örnek: Dallas, Oakland, Pittsburg, Miami, Chicago, Denver, Boston ve Spivey’s Corner kayıtlarını AVL ağacında saklamak istiyelim. Bu durumda ağaç oluşturulurken izlenecek adımlar sırasıyla aşağıdadır. Bu yapıda herhangi bir kayda ulaşmak için gerekli olan ortalama probe sayısı 2,62’dir. Kütük Organizasyonu 51 Genel Olarak AVL A ğaçları Tüm kayıtların eklenmesi beklenmeden her eklemeden sonra bir veya iki döndürme yapılır. Dengesiz bir a ğacın kök dü ğümünün denge faktörü -/+ 2 olur. Ekleme i şlemi sırasında izlenen yol üzerinde -/+1 denge faktörü de ğerine sahip olan dü ğüm yoksa a ğaç hala dengededir. Ekleme eklenen son yaprak kendi parent’ının ilk child’ı ise yol üzerindeki tüm dü ğümlerin denge faktör de ğeri yeniden düzenlenir. E ğer eklenen son yaprak kendi parent’ının ikinci child’ı ise sadece parent denge faktör de ğeri yeniden düzenlenir. Kütük Org anizasyo n u 5 2