Ağaçlar (Trees)
Dallanan Veri Yapıları
Meyve olarak para veren ağaçlar yoktur, ama dallarını gezerek verilere ulaşabileceğimiz ağaçlar vardır, en azından bazı bilgisayar programlarında.
Veri ağaçları birbirleriyle üst-alt ilişkisi bulunan, yani hiyerarşik (hierarchical) bir düzene sahip bilgileri saklamak için uygundurlar. Soy ağaçlarını veya kuruluşların organizasyon şemalarını oluşturan bireylerin kimlik bilgileri bu türden bir düzene sahip oldukları için bir veri ağacıyla temsil edilebilirler. Bir veri ağacı bir soy ağacı veya organizasyon şeması gibi yukarıdan aşağı doğru dallanan bir ağaç şeklinde düşünülebilir. Başlangıç noktasında bir “kök eleman” (root node) vardır. Buna bağlı sıfır, bir kaç veya bir çok “çocuk eleman” (child node) olabilir. Çocuk elemanların da her biri sıfır, bir kaç veya bir çok çocuk elemana sahip olabilir. Kök elemandan bağlayarak en alttaki çocuk elemana kadarki nesil sayısı “ağacın derinliği” olarak tanımlanır.
Burada şu noktaya dikkat çekelim: Biyolojik bir organizma olan gerçek bir ağacı oluşturan asıl elemanlar dallarıdır. Bir veri ağacının elemanları ise dalların çıkış noktalarıdır; bunlara “düğümler” (nodes) de denir. Bir başka fark da şudur: Veri ağaçlarını kök elemandan çocuk elemanlara doğru aşağı doğru dallanırlarmış gibi tarif ettik, ama bir veri ağacının elemanları bilgisayar hafızasında soldan sağa, yukarıdan aşağı, vb. gibi hiç bir öncelik veya sonralık ilişkisi içinde olmak zorunda değildir.
Veri Ağaçlarının Elemanları
Elemanlar arasında bir öncelik-sonralik ilişkisi de yoksa bu elemanları ancak adres bilgileriyle ilişkilendirebiliriz. Tıpkı sıralı bir listede olduğu gibi her ağaç elemanı kendisine bağlı çocuk elemanların adreslerini içeren bir adres değişkenleri listesi bulundurmak zorundadır. Bu sayede bir programcı bir veri ağacını kök elemandan bağlayıp onun çocuk elemanlarına, onların çocuk elemanlarına, … sırasıyla erişerek baştan başa dolaşabilir. Bu dolaşma işini önce belli bir dal silsilesini izleyerek en alttaki çocuk elemana erişip başa döndükten sonra başka bir silsileyi takip ederek, yani derinlik-öncelikli dolaşım (dept-first traversal) yoluyla, veya önce en üstteki çocuk elemanların her birine erişip daha sonra onların çocuk elemanlarına teker teker erişerek, yani genişlik-öncelikli dolaşım (breadth-first traversal) yoluyla yapabilir. Hangi yolun seçileceği –ki bazen farketmez- veri ağacıyla temsil edilen bilgilerin cinsine ve o bilgilere ne için erişildiğine bağlıdır. Eğer her ağaç elemanı bir de üstten bağlı olduğu ana elemana (parent node) işaret eden bir adres değişkenine sahip ise veri ağacını alta doğru da üste doğru da dolaşmak mümkündür.
Tabi her ağaç elemanı bir takım bilgiler de saklıyor olacaktır. Bu bilgilerin bütünü o elemanın değeri (value) olarak düşünülecektir. Bu bilgiler bir soy ağacındaki bir bireyin kimlik bilgileri, bir kuruluş organizasyonunun bir birimi hakkında bilgiler, bir aktivite sırasında değişik koşullarda alınacak tedbir veya yapılacak etkinlikler hakkında bilgiler, vb. olabilir.
İkili Ağaçlar (Binary Trees)
Hiyerarşik düzene sahip bilgileri temsil etmek için kullanılan veri ağaçlarında bir eleman belirsiz sayıda çocuk elemana sahip olabileceği için her elemanın kısalıp uzayabilen bir çocuk eleman listesine sahip olması gerekir. Bu da bilgilerin ve elemanların birbirleriyle ilişkilendirilebilmesi için bilgisayar hafızasının oldukça verimsiz kullanılmasıyla sonuçlanan bir listeler yığını kullanılması demektir. Her elemanının çocuk eleman sayısı belli olsaydı, örneğin her elemana en fazla iki çocuk düşeceği bilinseydi, bir veri ağacı elemanı çocuk elemanlar için esnek bir liste yerine eleman sayısı sabit bir dizi kullanırdı ve bu da veri depolama işini kolaylaştırırdı. Çocuk eleman sayısını 2 ile sınırlandıran bir veri ağacı “ikili ağaç” diye adlandırılır ve bazı durumlarda veri arama-tarama işlemlerini de hızlandırabildiği için oldukça sık kullanılır.
İkili ağaçlar rasgele sıralandıkları halde çabucak aranıp taranması gereken bilgileri depolamaktır. Bir veri grubunda arama işlemlerinin çabuk yapılabilmesi için sırasız bir liste yerine sıralı bir dizi kullanmamız gerektiğini biliyoruz; ne var ki, sürekli eklemelerle sayıları daha da artacak çok sayıda veriyi sıralı bir dizi oluşturacak şekilde depolamamız imkansız olabilir, veya verilerin tekrar tekrar silinip uzun süren sıralama işlemlerinden sonra tekrar kaydedilmesi gerekebilir. Bu verileri bir ikili veri ağacı oluşturacak şekilde depolayarak sıralı bir dizi oluşturmadan yarılamalı arama algoritmasını kullanarak arama yapabiliriz. Bunun nasıl olduğunu tamsayılardan ibaret bir veri grubundan oluşan bir ikili ağaç üzerinde gösterelim:
Şekil 5‑1 Rasgele sırayla okunan bir grup tamsayının bir ikili ağaç şeklinde depolanması
Şekil 5‑1’de her veri elemanı pSol ve pSağ diye adlandırılmış, çocuk elemanların yerini gösteren iki adres değişkenine, ve bir de tamsayı değere sahiptir. Solda yukarıdan aşağıya doğru yeni okunup ağaca eklenen tamsayı değerler listelenmiştir. Biraz dikkatli bir incelemeyle yeni değerlerin yerleştirilmesinde uygulanan kurallar kolayca anlaşılabilir
İlk okunan değer, 55, doğal olarak kök eleman olarak yerleştirilmiştir. İkinci okunan değer, 73, 55’ten büyük olduğu için kök elemanın sağ çocuğu olarak yerleştirilmiştir. Yani çocuk eleman olarak eklenecek yeni değer ana elemandan daha büyükse sağ çocuk olarak yerleştiriliyor. Üçüncü eklenen değer, 21, kök elemandan küçük olduğu için onun sol çocuğu olarak yerleştirilmiştir. Bu aşamada kök eleman 55’in iki çocuğu vardır ve artık ona yeni çocuk ekleyemeyiz. Dördüncü değer, 37, kök elemandan küçük olduğu için sola yerleştirilmelidir, ama solda zaten bir çocuk olduğu için bu yeni değer soldaki çocuğun bir çocuğu olarak eklenmelidir. Yeni değer 37, ana elemanı 21’den büyük olduğu için onun sağına yerleştirilmelidir. Bir sonra eklenen 14 ise yine 55’den küçük olduğu için onun soluna, 55’in solundaki 21’den de küçük olduğu için onun da soluna yerleştirilmiştir. Son eklenen 98 ise kök eleman 55’den büyük olduğu için onun sağında, 55’in sağındaki 73’den de büyük olduğu için onun da sağına yerleştirilmiştir.
Aşağıdaki şekilde bu veri ağacına bir kaç ekleme daha yapıldıktan sonra veri ağacında bir değer taranırken izelenecek yollar gösterilmiştir.
Şekil 5‑2 İkili bir veri ağacında arama yapılması
Hemen görülüyor ki bu arama işleminde sırasız bir listedeki gibi tek tek bütün elemanların değerlerinin aranan değerle karşılaştırılması gerekmemiştir. Değerler sıralı bir dizi de oluşturmadıkları halde bir yarılamalı arama algoritması uygulanmıştır. En alttaki eleman 93’ü saymazsak ağaç derinliği 3’tür ve aranan değer 47’yi bulmak için atılan adım sayısı da 3’tür. Bir genelleme yapacak olursak, bir ikili veri ağacı üzerinde yapılacak bir arama işleminin adım sayısının ağaç derinliğine eşit olduğunu söyleyebiliriz. Kısa bir not: Algoritma kitapları, örneğin (4), bir veri ağacının derinliğini verirken kök eleman da dahil olmak üzere altalta dizili eleman sayısını verirler. Biz burada altalta dizili dalları saymakla yetindik.
Bir konuya açıklık getirmeden geçmeyelim: Bir ikili ağaç yalnızca her elemanı en fazla iki çocuk elemana sahip olabilen bir ağaçtır. Yukarıdaki gibi yarılamalı arama algoritmasına izin verecek şekilde küçük elemanları sola, büyük elemanları sağa (tam tersi de olabilir) yerleştirerek oluşturulan bir ikili veri ağacına “ikili arama ağacı” (binary search tree) denir. Her ikili ağaç yarılamalı arama yapılacak şekilde düzenlenmiş olmayabilir.
Dengeli ve Dengesiz Ağaçlar
Bu şekildeki gibi hemen her dalda derinliği aynı olan bir veri ağacı “dengeli ağaç” (balanced tree) diye adlandırılır. Dengeli bir veri ağacı tıpkı dalları her yöne eşit açılarla ve eşit uzunluklarda uzayan gerçek bir ağa. gibi sağlıklı ve bir simetrik görüntüye sahip olacaktır. N elemanlı bir ikili ağacın derinliği, eğer ağaç dengeliyse yaklaşık lg(N/2)’ye eşittir. Bu da lg(N) – 1 demektir. Bu sonuç, bu tür bir veri ağacı üzerindeki bir arama işleminin oldukça kısa süreceği anlamına gelir. Şekil 5‑2’deki gibi rasgele sırayla gelen değerlerle oluşturulan bir ikili veri ağacı oldukça dengeli olacaktır.
Ama veri ağacına eklenecek değerlerin geliş sırası fazla düzenli ise ağaç çoğunlukla sola, ya da çoğunlukla sağa doğru dal verecektir ki o zaman da bir sıralı listeden farksız hale gelir. Böyle dengesiz bir ağaç üzerinde yapılacak bir arama işleminin adım sayısı yine ağaç derinliğine eşittir, ama ağaç derinliği hemen hemen eleman sayısına eşit olacağı için lg(N/2)’den çok daha fazla olabilir. Yani dengesiz bir ağaçta arama yapmak doğrusal arama yapmakla eşdeğerdir.
Veri Ağaçlarlarıyla İlgili Özel İşlemler
Veri Ağacı Oluşturulması
Bir veri ağacında önemli olan her elemanın çocuk elemanlarını gösteren bir adres değişkenleri listesine veya dizisine sahip olmasıdır. Bu koşulu sağlayan elemanlar bilgisayar hafızasında bir bağlantılı liste veya bir dizi halinde saklanabilir. İkili ağaçların çocuk eleman sayıları 2 olarak sabitlenmiş için bir ikili ağacı bir diziyle temsil etmek mümkündür. Örneğin, Şekil 5‑2’deki veri ağacı aşağıdaki gibi bir diziyle temsil edilebilir:
Şekil 5‑3 Bir diziyle temsil edilen bir ikili arama ağacı
Dizi şeklindeki bu ikili ağaçta her eleman okunduğu sırayla diziye sokulmuş, sol ve sağ çocukların adresleri olarak basitçe dizi içindeki sıra numaraları verilmiştir. Gerçek bir bilgisayar programında bu adresler bayt numaraları olurdu, ama onlar da bu sıra numaralarıyla doğrusal ilişkili olurdu. Şimdi yapay dille ikili arama ağacı oluşturacak bir algoritma tasarlayalım. Bu algoritmayı kendini çağıran bir fonksiyonla oluşturmak daha kolay olabilir. Çünkü yapacağımız şey, ağacı temsil eden diziye eklenecek her yeni elemanı kök elemanla tanıştırmak ve mümkünse yeni elemanı ona “evlat edindirtmektir”. Yeni elemanın taşıdığı değer kök elemanınkinden küçükse kök eleman onu sol çocuk (yok eğer büyükse sağ çocuk) olarak kabul edebilir. Sol çocuğu (ya da sağ çocuğu) varsa da sol çocuğunun (ya da sağ çocuğun) adresini veya sıra numarasını verir ki o zaman biz çocuk edintirten fonksiyonu bir kez daha çağırıp yeni elemanı evlat edinecek bir başka eleman ararız. Aşağıdaki kod örneğindeki fÇocukAta fonksiyonu bu evlat edindirme işini işte bu şekilde yapacaktır. Fonksiyona parametre olarak veri ağacını temsil eden dizi (buradaki ismi Ağaç), yeni elemanı çocuk eleman olarak kabul etmesi planlanan ana elemanın sıra numarası (ana), ve yeni eklenen çocuk elemanın sıra numarası (çocuk) gönderilmektedir.
Kod Örneği 5‑1 Bir ikili arama ağacını temsil edecek bir dizi oluşturulması
| fÇocukAta(pAnaEleman, pÇocukEleman)
{ “çocuk elemanın değeri küçükse ana elemanın “soluna yerleştirilecek if(pÇocukEleman.Değer < pAnaEleman.Değer) { “Bu elemanın sol çocuğu yoksa “yeni eleman sol çocuk olacak if(pAnaEleman.pSol ≠ BOŞ) else { pAnaEleman.pSol = pÇocukEleman} } else { “Bu elemanın sağ çocuğu yoksa “yeni eleman sağ çocuk olacak if(pAnaEleman.pSağ ≠ BOŞ) else { pAnaEleman.pSağ = pÇocukEleman } } } |
Bu fonksiyon diziye yeni eklenen her çocuk için bir kere, ana eleman sıra numarası olarak kök elemanın sıra numarası –ki o da 1- verilerek çağrılacaktır. Önce kök elemanı, olmazsa onun çocuklarını deneye deneye bu fonksiyon her yeni eleman için bir ana eleman bulacaktır. Bu şekilde oluşturulan bir ikili arama ağacının her elemanını yerleştirmek dizinin o anki derinliği kadar adım gerektirir. Örneğin, 32’den fazla elemanı olan dengeli bir ikili arama ağacına 32. eleman eklenmesi yaklaşık 4 adım (lg(32) − 1) gerektirecektir.
Eleman Bulma
Bu kez de yukarıdaki algoritma ile yarattığımız ikili arama ağacında belli bir değeri aradığımızı varsayalım. Araman değeri X ile temsil edelim. Bir ikili arama ağacında arama yaparken önce kök elemanın değerini aranan değerle karşılaştırır, eşitlik göremezsek onun çocuk elemanlarından birini deneriz. Aranan değer kök elemanınkinden küçükse sol çocuk, değilse sağ çocuk için bu karşılaştırma işlemini tekrarlarız. Demek ki bir ikili arama ağacındaki arama algoritması da kendini çağıran bir fonksiyon ile oluşturulabilir:
Kod Örneği 5‑2 Bir diziyle temsil edilen ikili veri ağacında belli bir değer aranması
| fElemanBul(pAğaçEleman, X)
{ “aranan değer küçükse elemanın soluna bak if(pAğaçEleman.Değer > X) { “Bu elemanın sol çocuğu yoksa aranan “değer bulunamadı demektir. if(pAğaçEleman.pSol ≠ BOŞ) else { SONUÇ: HAYIR } } else if(pAğaçEleman.Değer < X) { “Bu elemanın sağ çocuğu yoksa aranan “değer bulunamadı demektir. if(pAğaçEleman.pSağ ≠ BOŞ) else { SONUÇ: HAYIR } } “Aranan değer elemanın değerine eşitse aranan “değer bulunmuş demektir. SONUÇ: EVET } |
Bu fonksiyon aranan değer için bir kere, elemanno için kök eleman sıra numarası, yani 1, verilerek çağrılır. Fonksiyon sonuç olarak aranan değerin bulunup bulunamadığını gösteren bir mantıksal belirteç gönderecektir.
Eleman Silme
Bir veri ağacından eleman silerken dikkat edilmesi gereken şey o elemana bağlı çocuk elemanların ve onlara bağlı çocuk elemanların, … kısacası silinecek elemana bağlı tüm silsilenin –ki buna “alt-ağaç” (subtree) denir- de silinmesinin gerektiğidir. Bu tıpkı bir ticari kurumun bir birimini kapatıp o birimde çalışan elemanlarını işten çıkartması veya o birime ait malları likidite etmesi gibi düşünülebilir.
Bir ikili veri ağacından bir eleman silecek kodun yazılması bu bölümün sorularından birinde okuyuculara bırakılmıştır. Kendini çağıran bir fonksiyon kullanarak basit görünüşlü bir kod yazılabilir. Kendini yinelemeyen bir basit algoritmanın kodu biraz daha karmaşık gözükecektir.
| fElemanSil(pAğaçEleman)
{ “varsa bütün çocuk elemanları sildikten pÇocuk = pAğaçEleman.ÇocukListesi.pİLK } |
