bilgisayar programında bu işi yapabilmek için kabul Ağaçlar görmüş üç gezinme yöntemi bulunmaktadır:
Ağaç veri yapısı, verilerin birbirlerine temsili bir ağaç oluşturacak şekilde bağlandığı hiyerarşik bir veri Preorder Gezinme: Bu yöntemde öncelikle kök, daha modelidir. Bir ağaç düğümlerden ve düğümleri birbirine sonrasında sol alt ağaç, en son olarak da sağ alt ağa bağlayan dallardan meydana gelir. Ağaç veri yapısı, çizge üzerinde gezinme yapılır. Bu yöntemi akılda tutmak için veri yapısının bir alt kümesidir. Bir çizgenin ağaç “Root–Left–Right” terimini kullanabiliriz.
olabilmesi için, her iki düğüm arasında sadece bir yol Inorder Gezinme: Bu yöntemde öncelikle sol alt ağaç, olmalı, düğümler arasındaki yolda döngü (cycle) daha sonrasında kök, en son olarak da sağ alt ağaç olmamalıdır. üzerinde gezinme yapılır. Bu yöntemi akılda tutmak için
Ağaç veri yapısında bilinmesi gereken başlıca kavramlar “Left–Root–Right” terimini kullanabiliriz.
aşağıda listelenmiştir: Postorder Gezinme: Bu yöntemde öncelikle sol alt ağaç,
- Kök (Root): Bir ağacın en üst noktasında bulunan daha sonrasında sağ alt ağaç, en son olarak da kök düğümdür. üzerinde gezinme yapılır. Bu yöntemi akılda tutmak için - Dal (Edge): Düğümleri birbirine bağlayan kenara “Left–Right–Root” terimini kullanabiliriz.
verilen isimdir. İkili Arama Ağaçları: Bu veri yapısında, ikili ağaç - Yol (Path): Birbirleri ile bağlantılı dal dizisine yol adı özelliklerine ek olarak düğümlerde yer alan veriler verilir. arasında büyüklük-küçüklük ilişkisi bulunmaktadır. - Yol Uzunluğu (Length of a Path): Bir yolu oluşturan dal dizisindeki dal sayısıdır. İkili ağaç özellikleri taşıyan bir ağacın ikili arama ağacı - Ebeveyn (Parent):Bir düğümden önce yer alan ve o olabilmesi için ağaçtaki her düğümün, sol alt ağacındaki düğüme bir dal ile bağlı olan düğüme ebeveyn denir. tüm değerlerden büyük olması, sağ alt ağacındaki tüm Kök hariç her düğümün bir ebeveyni bulunmaktadır. değerlerden küçük veya eşit olması gerekmektedir.
- Çocuk (Child): Bir düğümden sonra yer alan ve o İkili Arama Ağacına Düğüm Ekleme: İkili arama ağacına düğüme bir dal ile bağlı olan düğüm/düğümlere çocuk düğüm eklemede, ağacın düğümlerinin değerleri denir. arasındaki büyüklük-küçüklük ilişkisini korumak için - Ağaç Yüksekliği (Height of a Tree): Bir ağacın eklenecek düğümün yeri tespit edilmelidir. Ağaç boş ise kökünden ağaçtaki en alt çocuğa kadar olan yolun yeni düğüm, ağacın kökü olarak tayin edilir. Ağaç dolu ise uzunluğudur. ağacın kökünden yola çıkılarak, eklenecek düğümün - Düğüm Yüksekliği (HeightofaNode): Bir düğümden değeri ile kök düğümün değeri karşılaştırılır. Yeni ağaçtaki en alt çocuğa kadar olan yolun uzunluğudur. düğümün değeri kökteki değerden büyükse sağ alt ağaca, - Düğüm Derinliği (Depthofa Node): Bir düğümden küçükse sol alt ağaca doğru ilerlenir. Bu işlem, yeni ağaç köküne kadar olan yolun uzunluğudur. düğüm için uygun bir yer bulunana kadar tekrarlanır.
Bir ağaç veri yapısı, sahip olduğu özellikler ile farklı İkili Arama Ağacından Düğüm Çıkarma: İkili arama kategorilere ayrılabilir. Ağaç veri yapısı ikili ağaçlar, ikili ağacından düğüm çıkarma için öncelikle düğümün ağaçta arama ağaçları ve AVL ağaçları olmak üzere bulunması gerekir. Düğüm ağaçta yer alıyorsa, ikili arama incelenecektir. ağacı özellikleri korunarak çıkarma işlemi gerçekleştirilir. İkili arama ağacından düğüm çıkarırken incelenmesi İkili Ağaçlar(Binary Trees): İkili ağaçlar, her bir düğümün gereken üç durum vardır: en fazla 2 çocuğa sahip olabildiği ağaç türüdür. Bu veri yapısında ekleme, silme ve arama işlemleri çok hızlı bir i. Çıkarılacak düğümün çocuğu yok ise; düğümün şekilde yapılabilmektedir. Kitabımız Sayfa 42, Örnek ebeveyninin ilgili göstericisi (left veya right) NULL 3.1’de struct kullanımı ile ikili ağaç veri yapısının nasıl yapılır, düğüm hafızadan silinir. tanımlanabileceği gösterilmiştir. ii. Çıkarılacak düğümün 1 çocuğu var ise; düğümün çocuğundan itibaren olan alt ağaç düğümün İkili Ağaçlarda Gezinme Yöntemleri: Bir ağacın ebeveynine bağlanır, düğüm hafızadan silinir. düğümlerini belirli bir algoritma ve sıra çerçevesinde iii. Çıkarılacak düğümün 2 çocuğu var ise düğümün sağ dolaşma eylemine ikili ağaçta gezinme adı verilir. Bir alt ağacındaki en küçük değerli düğüm bulunur, bilgisayar programındaki ağaç veri yapısında gezinmenin bulunan düğüm ile çıkarılacak düğüm yer değiştirilir, düğümlerde arama yapma, düğümleri kullanıcıya düğüm hafızadan silinir. gösterme, düğüm değerlerini ekrana yazdırma gibi çeşitli sebepleri olabilir. AVL Ağaçları: İkili ağaçlarda ve ikili arama ağaçlarında ağacın yüksekliği için herhangi bir ölçüt bulunmamakta- İkili ağaç veri yapısı kendi içerisinde alt ağaçlardan dır. N adet düğüme sahip bir ikili ağacın yüksekliği en meydana geldiği için, ikili ağaçları gezinmede fazla N-1 olabilir. AVL (Adelson –Velsky – Landis) özyinelemeli fonksiyonlar kullanılır. İkili ağaçlardaki ağaçları, ikili arama ağaçlarının özel bir türüdür. Bu veri düğümler dolaşılırken farklı yöntemler uygulanabilirken, yapısında ağaç içerisindeki denge korunmakta, sol alt ağaç
YBS204U-ALGORİTMALAR ve PROGRAMLAMA
Ünite 3: Ağaçlar, Yığın Ağaçları ve Özetleme Tabloları
ile sağ alt ağaç arasındaki yükseklik farkı en fazla 1 olabilmektedir.
Bir düğümün sol alt ağacının yüksekliği ile sağ alt ağacının yüksekliği arasındaki farka denge faktörü adı verilir.
AVL ağaçlarındaki düğümler için denge faktörü
bf = hLeft – hRight
formülü ile hesaplanır ve dengeli bir ağaç için bu değerler yalnızca -1, 0 ve 1 olabilir.
AVL ağaçları için düğüm ekleme ve düğüm çıkarma işlemleri, ağaçtaki düğümlerin dengesini bozabilmektedir. Dolayısıyla bu işlemlerde ağacın dengesini korumak için pivot düğüm üzerinde çeşitli döndürmeler yapılır. Denge faktörü 2 veya -2 olan düğüme pivot adı verilir. AVL ağaçlarında pivot düğüm üzerinde döndürmeler yapılarak denge sağlanır.
AVL ağaçları için ekleme ve çıkarma işlemleri anlatılırken aşağıdaki terminolojiden faydalanılacaktır:
- P: Pivot - L: Pivotun sol alt ağacı - R: Pivotun sağ alt ağacı - A bölgesi: Pivotun sol alt ağacının sol çocuğudur. - B bölgesi: Pivotun sol alt ağacının sağ çocuğudur. - C bölgesi: Pivotun sağ alt ağacının sol çocuğudur. - D bölgesi: Pivotun sağ alt ağacının sağ çocuğudur.
AVL Ağacına Düğüm Ekleme ve Denge Korunumu:
AVL ağacına düğüm eklerken, öncelikle düğümün ekleneceği yer bulunur. Düğüm eklendikten sonra oluşan yeni ağaç üzerinde denge faktörleri hesaplanır, ağaçta bir dengesizlik olması durumunda dengesizliğin olduğu düğüm (pivot) tarafında bir veya iki tane döndürme işlemi uygulanır.
Ekleme işleminden sonra oluşan dengesizlik, dört ayrı şekilde görülebilir:
i. A bölgesine ekleme (LLImbalance): P’nin denge faktörü 2, L’nin denge faktörü 0 veya 1 iken karşılaşılır, pivot etrafında sağa doğru tek döndürme ile çözülür. ii. D bölgesine ekleme (RRImbalance): P’nin denge faktörü-2, R’nin denge faktörü değeri 0 veya -1 iken karşılaşılır, pivot etrafında sola doğru tek döndürme ile çözülür. iii. C bölgesine ekleme (RL Imbalance): P’nin denge faktörü -2, R’nin denge faktörü 1 iken karşılaşılır, sağ ve sol çiftdöndürme ile çözülür. iv. B bölgesine ekleme (LRImbalance): P’nin denge faktörü2 ,L’nin denge faktörü -1 iken karşılaşılır, sol ve sağ çift döndürme ile çözülür.
AVL Ağacından Düğüm Çıkarma ve Denge Korunumu: AVL ağacından düğüm çıkarılırken, ikili arama ağacındaki çıkarma yöntemi izlenir. Düğüm çıkarıldıktan sonra oluşan yeni ağaç üzerinde denge faktörleri
hesaplanır. Ağaçta bir dengesizlik olması durumunda dengesizliğin olduğu düğüm (pivot) tarafında bir veya iki tane döndürme işlemi uygulanır.
Çıkarma işleminden sonra oluşan dengesizlik, dört ayrı şekilde görülebilir:
i. A bölgesinden çıkarma (LL Imbalance): P’nin denge faktörü2, L’nin denge faktörü 0 veya 1 iken karşılaşılır, pivot etrafında sağa doğru tek döndürme ile çözülür. ii. D bölgesinden çıkarma (RRImbalance): P’nin denge faktörü-2, R’nin denge faktörü 0 veya -1 iken karşılaşılır, pivot etrafında sola doğru tek döndürme ile çözülür. iii. C bölgesinden çıkarma (RLImbalance): P’nin denge faktörü-2, R’nin denge faktörü 1 iken karşılaşılır, sağ ve sol çift döndürme ile çözülür. iv. B bölgesinden çıkarma (LR Imbalance): P’nin denge faktörü2, L’nin denge faktörü -1 iken karşılaşılır, sol ve sağ çift döndürme ile çözülür.
Yığın Ağaçları
Bir veri kümesi içerisinde en küçük elemanın hızlıca bulunmasını sağlayan veri yapısıdır. Aşağıda verilen iki özelliği sağlayan bir ikili ağaç, yığın ağacı veri yapısı olarak sınıflandırılır:
1. Ağaç bütünlüğü: Ağacın son düzeyi hariç tüm düzeyleri, içerdikleri düğümler bakımından eksiksiz olmalıdır. Ağacın son düzeyindeki düğümler de soldan sağa doğru dolu olmalıdır. 2. Heap özelliği: Bir düğümün sahip olduğu değer, düğümün çocuklarına ait değerlerden küçük veya eşit olmalıdır.
Dizi ile Yığın Ağacı Uygulaması: Yığın ağaçları, ağaç bütünlüğüne sahip ikili ağaçlar olduğu için, yığın ağacı veri yapısını bir dizi kullanılarak programlanabilir. Bu sayede göstericilerden ve bağlı liste kullanımından kaçınılmış olunur.
Yığın Ağacında En Küçük Elemanı Elde Etme: Yığın ağacının en küçük elemanı, ağacın kökünde yer almaktadır. Bu elemanı elde etmek için dizinin 1 numaralı indisine erişmek yeterlidir. N uzunluğunda H isimli bir dizi ile ifade edilen yığın ağacında en küçük elemanı elde etmek için dizinin H[1] elemanına erişmek yeterlidir.
Yığın Ağacından En Küçük Elemanı Çıkarma: Aşağı Yönlendirme: Yığın ağacının en küçük elemanı ağaçtan çıkarılırken, ağacın son düzeyinin en sağındaki düğüm ile ağacın kökü yer değiştirilir. Yer değiştirme işleminden sonra en küçük elemanı içeren ağacın son düzeyindeki en sağ düğüm ağaçtan çıkarılır. Ağacın heap özelliğini korumak için, ağacın kökü üzerine aşağı yönlendirme işlemi uygulanır. Bu düğüm, ağaç içerisinde doğru yere gelinceye kadar çocukları ile karşılaştırılır ve değer olarak en küçük çocuk ile yer değiştirilir.
Yığın Ağacına Eleman Ekleme: Yukarı Yönlendirme: Yığın ağacına yeni bir eleman eklerken, ağacın son düzeyinin en sağında yeni bir düğüm yaratılır ve eklenecek değer bu yeni düğüme atanır. Oluşan yeni ağaç için ağaç bütünlüğü korunmakta, fakat ağacın heap özelliği kaybolmaktadır. Ağacın heap özelliğini sağlaması amacıyla, eklenen düğüm üzerinden yukarı yönlendirme işlemi yapılır. Eklenen yeni düğüm, ağaç içerisinde doğru yere gelinceye kadar ebeveyniyle karşılaştırılır ve düğümün değeri ebeveynin değerinden küçük ise düğüm ile ebeveynin yeri değiştirilir.
Özetleme (Hash) Tabloları
Özetleme tabloları ekleme, silme ve arama işlemlerinin çok hızlı bir şekilde yapılmasını sağlayan, verileri bir anahtar ve veri çifti şeklinde saklayan veri yapısıdır. Özetleme tablolarındaki genel çalışma mantığı, verileri N boyutlu bir dizide tutmak ve verilere erişim için sayı veya dizgiden oluşan anahtarı kullanmaktır.
Hash fonksiyonu, özetleme tablolarında verilen bir anahtar için tablodaki indis değerini hesaplayıp döndüren fonksiyondur. Özetleme tablosunda saklanacak bir veri için hash fonksiyonuna anahtar değeri gönderilir, fonksiyonun hesapladığı değer, verinin dizide tutulacağı indis olur.
Çatışmalar: Özetleme tablolarında kullanılan hash fonksiyonları belirli bir algoritmaya sahiptir. Fonksiyon için tanımlı algoritma, fonksiyona verilen anahtar değeri doğrultusunda bir indis değeri hesaplar ve döndürür.
Hash fonksiyonu için tanımlanan algoritma, her anahtar değeri için farklı bir indis üretmeyebilir. Özetleme tablosunda fonksiyonun döndürdüğü indis değerine karşılık gelen alan dolu ise çatışma adı verilen durum ortaya çıkar. Çatışmalar, hash fonksiyonları için istenmeyen durumlardır. Verimli ve etkin bir hash fonksiyonu aşağıdaki özellikleri sağlamalıdır:
i. Fonksiyon içerisinde hesaplamalar hızlı yapılmalıdır ii. Hesaplama sonucu üretilen değerlerde minimum çatışma olmalıdır. iii. Özetleme tablosundaki tüm alanlar kullanılabilir olmalıdır. iv. Özetleme tablosundaki doluluklarda eşit dağılım sağlanmalıdır.
Çatışma Çözüm Yöntemleri: Bir hash fonksiyonu için çatışma oluşumu ihtimalini ortadan kaldırmak mümkün olmasa da çatışma ile karşılaşıldığında uygulanabilecek çözümler mevcuttur.
Çatışma çözüm yöntemleri iki ana başlıkta incelenir:
1. Ayrık Zincirleme (Separate Chaining): Ayrık zincirleme yönteminde aynı indise karşılık gelen veriler, bir bağlı liste kullanarak saklanır. Böylelikle özetleme tablosundaki bir alanda birden çok verinin saklanması sağlanır.
2. Açık Adresleme (Open Addressing): Olası bir çatışma durumunda ikinci bir hash fonksiyonu kullanarak, tabloda boş bir alan aranan yönteme açık adresleme adı verilir. N boyutlu bir özetleme tablosunda, X anahtarı için açık adreslemenin genel formülü şu şekildedir:
hi(X) = (Hash(X) +F(i)) mod N
Belirtilen formüldeki i değişkeni, anahtarın hash fonksiyonuna kaçıncı kez gönderildiğini ifade eden sayıdır. F fonksiyonu çatışma çözümü için kullanılan ikinci fonksiyondur ve F(0) = 0’dır.
Açık adreslemede çatışma çözümü için kullanılan üç çeşit temel ikinci hash fonksiyonu bulunmaktadır.
a) Doğrusal Sınama (Linear Probing): F(i)=i b) Karesel Sınama (Quadratic Probing): F(i)=i2
c) İkili Hash (Double Hashing): F(i)=i*Hash2(i)