BİL204U-ALGORİTMALAR
Ünite 7: Liste ve Ağaç Yapıları
Giriş
Ağaç ve liste yapıları işaretçilerin kullanımı sayesinde dinamik olarak saklanan veri miktarının ve/veya verinin değiştirilebileceği veri yapılarıdır. Bu veri yapılarında veriyi saklayan birimler düğüm adını alırlar. Düğüm birimi içerisinde veri ve diğer düğümlere ait adres bilgisini taşıyan işaretçi(ler) yer alır. Bu işaretçiler sayesinde bir düğümden diğer düğüme geçiş yapılabilir. Bu sebeple düğümlerin yer aldığı veri yapıları görsel olarak ifade edilirken düğümler arasındaki ilişkileri göstermek adına oklar çizilir.
Düğümlerin işaretçilerinde sakladıkları sonraki düğümlere ait adres bilgisine göre liste, ağaç vb. gibi farklı veri yapıları oluşturulması mümkündür. Örneğin, tek yönlü bağlı liste yapısında her bir düğümde tek bir işaretçi olur ve bu işaretçi sonraki düğüme ait adres bilgisini taşır. Kitabın 141. sayfasındaki şekil 7.1’de dört düğümün bulunduğu tek yönlü bir bağlı liste örneği verilmiştir.
Her bir düğümde bulunan işaretçi sayısının iki olduğu durumda ise kitabın 141. Sayfasındaki şekil 7.2’de verilen şekilde bir ikili ağaç yapısının oluşturulması mümkündür. Şekil 7.2’de verilen her bir düğümde i1 ve i2 şeklinde isimlendirilen iki işaretçi bulunmaktadır. Gösterim kolaylığı olması açısında düğümlerin işaretçi alanı çizilmeden sadece oklar ile düğümler arası ilişkiler gösterilir. Bu durumda kitabın 141. Sayfasındaki şekil 7.1’de verilen dört düğümlü liste aynı sayfadaki şekil 7.3’teki görsel ile ifade edilir.
Liste Yapıları
Listeler verilerin bellekte ardışık olarak saklanmasını gerektirmeyen dinamik yapılardır. Bu dinamik yapı temelde veriyi saklayan düğüm yapısının içine işaretçiler yerleştirilerek kurulur. Bu işaretçiler liste yapısında ilgili düğümden sonra ve/veya önce gelen düğümün adres bilgisini saklamakla görevlidir. Diğer bir deyişle işaretçiler vasıtası ile düğümler birbirine bağlanır, bu sebeple listeler çeşitli kaynaklarda bağlı listeler olarak da adlandırılır. Bağlı listeler kuyruk, yığın gibi yapıların kurulması amacı ile kullanılır.
Listeler dizi (İng. array) yapılarına benzer şekilde belirli bir veri koleksiyonunu işlemek/saklamak amaçlı kullanılırlar. Ancak bellek kullanımı açısından daha avantajlı oldukları durumlar söz konusudur. Örneğin, 100 adet sayının dizi yapısı ile saklanması durumunda bu kümenin tümünün tek bir bellek bloğu içinde saklanması gerekirken liste yapısında her bir düğüm bellekteki farklı bir lokasyonda bulunabilir. Bu anlamda belleğin kullanımı açısından daha verimli bir yapı sunulmuş olur. Bununla beraber her bir düğümde verinin yanı sıra adres bilgisinin de saklanması gerekliliği bellek kullanımı açısından bir dezavantajdır.
Kitabın 142. sayfasındaki şekil 7.4’te verilen örnek liste üzerinde yapılabilecek temel işlemler yeni bir düğüm yaratma, listeye düğüm ekleme, listeden düğüm silme, liste içinde gezinme şeklinde listelenebilir. Yeni bir düğüm yaratma operasyonu saklanacak verinin alınması, gerekli
bellek alanının düğüm için rezerve edilmesi (açılması), verinin ilgili alana kopyalanması ve işaretçinin ilk değerinin verilmesi işlemlerinin sırasıyla yürütülmesini içerir.
Liste İşlemleri
Temel liste işlemleri listeye düğüm ekleme, listede belirli bir düğümü silme ve listede arama yapma işlemleridir.
Listeye yeni bir düğüm ekleme işleminde düğümün ekleneceği lokasyona göre farklı problemler tanımlanabilir. Örnek olarak düğümün
• listenin başına • listenin sonuna • düğüm olarak
eklenmesi gibi farklı ekleme problemleri söz konusudur.
Liste başına ekleme operasyonunda ilk olarak yeni bir düğüm yaratılmalıdır. Bu işlemde bellekte bir düğüm yaratılır, veri düğüm içine aktarılır ve işaretçi değeri olarak BOŞ atanır. Daha sonra listenin geçerliliği yani en azından ilk düğümü içermesi durumu kontrol edilir. Geçerli bir liste var ise yeni düğüm işaretçisine listede bulunan ilk düğümün adresi yani listenin adresi atanmalıdır. Bu atama ile yeni düğüm ile liste bağlanmış olacaktır. Bu bağlama sonrasında listenin başlangıç düğümü artık yeni düğüm olmalıdır. Bu sebeple listenin adresi olarak yeni düğümün adresi atanmalıdır. Diğer bir deyişle listeye erişim için artık yeni düğüm kullanılmalıdır. Bu işlem Sözde kitabın 143. Sayfasındaki sözde kod 7.1’de verilmiştir.
Kitabın 143. sayfasındaki Sözde Kod 7.2’de bir listenin sonuna düğüm eklemeye dair adımlar verilmiştir. Önceki operasyona benzer şekilde önce yeni bir düğüm yaratılması sonrasında liste geçerliliğinin kontrolü gereklidir. Sonra- sında ise bu düğüme ulaşabilmek için listenin başından sonuna kadar düğümler tek tek ziyaret edilerek son düğüme ulaşılmalıdır.
Listeye i. düğüm olarak yeni düğüm eklenmek istendiğinde öncelikle listenin uzunluğu yani listede yer alan düğüm sayısının tespiti gereklidir. Listede en az i-1 adet düğüm var bu işlem gerçekleştirilebilir. Aksi durumda ise bir hata mesajı ile geri dönülmelidir. Liste sonuna düğüm ekleme işlemine benzer şekilde bir döngü kurulur. Ancak bu sefer liste içinde i-1 nolu düğüme kadar ilerlemek gereklidir. Kitabın 144. Sayfasındaki sözde Kod 7.3’te verildiği üzere i-1 nolu düğüme gelindiğinde bu düğüm güncel Düğüm, izleyen düğüm (i. düğüm) ise sonraki Düğüm değişkenlerinde saklanarak araya yeni düğümün eklenmesi sağlanabilir. Aynı sayfadaki Şekil 7.5’te i=3 için örnek bir görsel verilmiştir.
Temel liste işlemlerinden biri de listeden bir düğümün silinmesidir. Listenin başındaki ve sonundaki düğümün silinmesi işlemlerine ek olarak verilen bir verinin yani belirli bir düğümün de silinmesi istenebilir. Listenin başından düğüm silme işlemi basitçe ikinci düğümün liste başı olarak etiketlenmesini gerektirir. Kitabın 144.
sayfasındaki sözde Kod 7.4’te bu işlem verilmiştir. Listede son düğüm silinmesi işleminde öncelikle son düğümden önceki düğüme kadar liste içinde ilerlenmesi, bu düğüme gelindiğinde ise işaretçisinin BOŞ hâle getirilmesi gereklidir. Kitabın 145. Sayfasındaki sözde Kod 7.5’te bu işlem verilmiştir.
Listeden düğüm silme probleminin en karmaşık hâli verilen bir verinin listede aranması ve listede bu verinin bulunması durumunda ilgili düğümün listeden silinmesidir. Bu silme işlemi kitabın 145 sayfasındaki Sözde Kod 7.6’da verilmiştir. Bağlı listelerde verdiğimiz silme işlemi örneği temelde arama işlemini içermektedir. Burada kurulan döngü ise kitabın 146. sayfasındaki Sözde Kod 7.7’de görüleceği üzere arama işleminde de yer almaktadır.
Liste Türleri
Listeler işaretçilerin sayısı ve kullanımına bağlı olarak dört temel sınıfa ayrılırlar. Bunlar;
1. Tek yönlü bağlı liste 2. Çift yönlü bağlı liste 3. Dairesel tek yönlü bağlı liste 4. Dairesel çift yönlü bağlı liste
Tek yönlü bağlı listeler başlangıç ve son düğümü arasında düğümlerin yer aldığı ve her bir düğümün kendinden sonraki düğüme ait adres bilgisini sakladığı düğümlerdir. Buraya kadar verilen tüm sözde kod örnekleri ve görseller bu sınıfa aittir. Çift yönlü listelerin farkı iki adet işaretçiye sahip olmalarıdır. Bu sayede önceki ve sonraki düğüme ait adresi saklayarak çift yönlü harekete olanak tanırlar. Kitabın 146. Sayfasındaki resim 7.6’da çift yönlü bağlı listelere dört düğümlü bir örnek verilmiştir. Bu örnekte n ve p isimli iki işaretçi bulunmaktadır. Bu işaretçilerden n sonraki, p önceki düğüme ait adres değerini saklamaktadır.
Çift yönlü bağlı listelerde ilk düğümün p işaretçisi herhangi bir düğümü işaret etmeyeceği için geçerli bir adres saklamamaktadır. Bu tip listelerde p işaretçisi ile önceki düğüme ait adres de saklandığı için ekleme, silme vb. işlemlerde farklılıklar vardır. Kitabın 147. Sayfasındaki Sözde Kod 7.8’de düğüm silme işlemi çift yönlü bağlı liste için verilmiştir. Bu kodda özellikle güncelDüğüm.p.n =güncel Düğüm.n satırı kritik öneme sahiptir. Bu satırda basitçe silinecek verinin yer aldığı güncelDüğüm’ün öncesindeki düğümün işaretçisine güncel Düğümden sonraki düğümün adresi atanır. Kitabın 147. sayfasındaki Şekil 7.7’de bu durum görselleştirilmiştir.
Dairesel bağlı listelerde diğer listelerden farklı olarak son düğüm ilk düğüme ait adres bilgisini saklamaktadır. Resim 7.8’de dört düğümlü tek yönlü bir dairesel liste verilmiştir.
Dairesel olmayan listelerde son düğümün ilk düğüme bağlı olması liste işlemlerinde son düğümün sorgulandığı durumlarda değişiklik yapılmasına sebep olur. Dairesel tek bağlı listelerde kitabın 147. sayfasındaki Sözde Kod 7.9 ve 148. sayfasındaki Sözde Kod 7.10’da verildiği şekilde yeni düğüm sırasıyla son düğüm ve ilk düğüm olarak eklenir.
Ağaç Yapıları
Ağaçlar düğümlerin hiyerarşik bir yapıya sahip olacak şekilde birbirine bağlandığı doğrusal olmayan yapılardır. Bu yapılarda ilk düğüm kök olarak adlandırılır. Kök düğümden başlayarak her düğümün adreslerini sakladığı çocuk düğümleri olabilir. Görsel olarak kök düğüm en üstte yer alır ve diğer düğümler katmanlar hâlinde yerleştirilirler. Başka düğümlerin adreslerini saklamayan düğümlere yaprak adı verilir. Kitabın 149. Sayfasındaki şekil 7.9’da verilen ağaç örneğinde A düğümü kök, E, F, I, J ve D düğümleri ise yaprak düğümlerdir. Bu örnek ağaçta kök düğümünden sonra 3 katman mevcuttur. Örnek ağaçta A düğümü 3 çocuk düğüme (B, C ve D) ait adresi saklarken, C düğümü bir adres, B ve H düğümleri ise 2 adrese işaret etmektedir. Ağaç yapısında çocuk düğümlere sahip olan düğümlere ebeveyn ismi verilir. Bir ebeveynin sahip olduğu çocuk sayısına düğümün derecesi denir. Aynı ebeveyne sahip düğümler ise kardeş düğümdürler. Örneğin H düğümü 2 dereceli bir ebeveyn, I ve J düğümleri ise onun çocuklarıdırlar. Diğer bir deyişle I ve J düğümleri kardeştir. Ağaç yapısındaki bu ebeveyn-çocuk ilişkisi kapsamında bir düğüme bağlı tüm alt düğümlere o düğümün varisleri denir. Bir düğümden kök düğüme kadar izlenen yolda bulunan tüm düğümler ilgili düğümün atası olur.
Ağaç yapısında düğümler arası bağlantılar dal veya kenar olarak adlandırılır. Kenarlar ağaç tipine bağlı olarak Şekil 7.9’da verildiği şekilde tek yönlü veya çift yönlü bağlantıya sahip olabilirler. Her bir düğümün kenarları sayesinde bağlı olduğu varislerinden oluşan bir alt-ağacı vardır. Örneğin, örnek ağaçta C düğümünün kök olduğu H, I ve J düğümlerinden oluşan bir alt ağaç vardır.
Ağaç yapılarında yükseklik ve derinlik şeklinde isimlendirilen iki önemli terim tanımlanmıştır.
Şekil 7.9’da en uçtaki yaprak düğümler I ve J’dir. Bu sebeple verilen ağacın derinliği 3’tür. Bir düğümün kök düğüme olan uzaklığı (geçilen kenar sayısı) ise ilgili düğüm için düğüm derinliğini verir. Örneğin; H için düğüm derinliği 2, B için ise 1’dir.
Ağacın yüksekliği kök düğümün yüksekliğine eşittir. Ağaçların yaprak düğümlerinin yüksekliği sıfırdır. Şekil 7.9’da verilen örnek ağaçta B ve H düğümlerinin yüksekliği 1; C düğümünün yüksekliği 2; D, E, F, I ve J düğümlerinin yükseklikleri ise sıfırdır. Ağacın yüksekliği ise 3’tür.
Ağaç Türleri
Ağaç veri yapısı her bir düğümün sahip olabileceği çocuk sayısı, ağacın oluşturulma amacı vb. çeşitli sebeplerle farklı türlere ayrılır ve farklı isimler ile anılırlar.
İkili Ağaçlar
İkili ağaçlarda her bir düğümün en fazla iki çocuk düğümü olabilmektedir. Bu düğümler sağ ve sol çocuk olarak adlandırılmaktadır. İkili ağaçlar derleyiciler tarafından söz dizimi ağaçlarının oluşturulması, ifade derleyici ve çözücülerde kullanılmaktadır. Bu ağaçlara çeşitli özellikler
ve kısıtlamalar eklenerek ikili arama, AVL gibi farklı ağaç bir, sol alt ağacında iki kenar vardır. Bu sebeple dengeleme tipleri oluşturulabilmektedir. faktörü -1 olmuştur.
İkili Arama Ağaçları AVL ağaçlarında yeni bir düğüm eklendiğinde eğer ağacın İkili arama ağaçları her düğümün sağ ve sol çocuğunun dengesi bozulur ise döndürme işlemi ile ağaç tekrar dengeli olabileceği yapıya sahiptir. Bu ağaçlarda sol çocuk her hâle getirilir. Sağ, sol, sağ-sol, sol-sağ şeklinde zaman ebeveyninden küçük veya eşit değeri saklarken sağ isimlendirilen 4 döndürme işlemi vardır.
çocuk ise her zaman ebeveyninden büyük bir değer Kitabın yine 153. sayfasındaki Şekil 7.13 ve 7.14’te sağa ve saklamak durumundadır. Kitabın 150. sayfasındaki Şekil sola döndürme işlemleri örneklendirilmiştir. Bu işlemlerde 7.10’da örnek bir ikili arama ağacı verilmiştir. Örneğin, bu sol tarafı dengesiz bir ağacı sağa döndürmede her düğüm ağaca 3 değerini eklemek istediğimizde yeni düğüm 4 hâlihazırdaki pozisyonundan bir sağ pozisyona kayarken, değerini saklayan düğümün sol çocuğu olarak eklenecektir. sağ tarafı dengesiz bir ağaçta sola döndürme ile düğümler
İkili arama ağaçlarına yeni bir düğüm eklenmesi işlemine bir sol pozisyona kayar.
ait özyinelemeli algoritma kitabın 150. Sayfasındaki Sözde 154. sayfadaki Şekil 7.15 ve 7.16’da ise sağ-sol ve sol-sağ Kod 7.11’de verilmiştir. Kodda verilen x değişkeni ağacın döndürmeye ait örnekler verilmiştir. kök düğümünü ifade etmektedir. Bu algoritma 3 değerini Şekil 7.10’da verilen ağaca eklerken x düğümü sırasıyla 8, 6 ve 4 değerlerini taşıyacaktır.
Düğümlerin sakladıklarının veri değerine dair belirlenen kısıtlama sayesinde ikili arama ağaçları içinde gezinilirken ağaçta saklanan veriye sıralı şekilde ulaşılması mümkündür. İç-sıralı gezinme (İng. in-order traversal) olarak verilen bu işlem kitabın 151. Sayfasındaki Sözde Kod 7.12’de verilmiştir. Şekil 7.10’da verilen ağaç için bu kod koşturulduğunda yürütülen işlemler 151. Sayfadaki Şekil 7.11’de görülmektedir. İşlemler [8] düğümünün fonksiyona verilmesi ile başlar. Sırasıyla 4-5-6-7-8-9 düğümleri yazdırılır.
İkili arama ağaçlarında gezinme için iç sıralı gezinme dışında önce-kök (İng. preorder) (kitabın 152. sayfasındaki Sözde Kod 7.13), sonra-kök (İng postorder) (kitabın 152. sayfasındaki Sözde Kod 7.14) gibi çeşitli yöntemler vardır. Örneğin önce-kök yöntemi verilen örnek ağaçta uygulanınca 8-6-4-5-7-9 düğümleri sırasıyla ziyaret edilmiş olur. Verilen probleme uygun olarak yöntem seçilerek istenen şekilde bir gezinme sağlanabilir.
İkili arama ağaçlarında belirli bir düğümün aranması işleminde düğümlerin sakladıkları değere göre sola veya sağa yönlendirme yapılarak sol veya sağ ağaç arama işlemine devam edilir. Yine kitabın 152. sayfasındaki Sözde Kod 7.15’te x ağacında d değerinin aranmasına dair arama algoritması verilmiştir. Arama algoritması değeri bulamadığı durumda BOŞ, bulduğu durumda ise ilgili değeri taşıyan düğümü geri döndürmektedir.
AVL Ağaçları
AVL ağaçları sağ ve sol alt ağaçlarda dengenin sağlandığı ikili ağaçlardadır. Diğer bir deyişle bu ağaçlarda her bir düğümün sağ ve sol ağaçlarının uzunluğu arasındaki fark en fazla bir olabilir. Daha fazla fark olduğu durumda dengeleme işlemi yapılarak belirlenen uzunluk kısıtına uygun şekilde düğümler yerleştirilir. Kitabın 153. Sayfasındaki Şekil 7.12’de verilen ağaç dengeli bir ağaçtır. Her bir düğümün yanında yazan değer ise sağ alt ağaç uzunluğunun sol alt ağaç uzunluğu arasındaki farktır. Örneğin B düğümü için sağ alt ağacında bağlantılı en uzun