Algoritmalar Ve Programlama Dersi 3. Ünite Özet

Ağaçlar

Ağaç veri yapısı, verilerin birbirlerine temsili bir ağaç oluşturacak şekilde bağlandığı hiyerarşik bir veri modelidir. Bir ağaç düğümlerden ve düğümleri birbirine bağlayan dallardan meydana gelir. Ağaç veri yapısı, çizge veri yapısının bir alt kümesidir. Bir çizgenin ağaç olabilmesi için, her iki düğüm arasında sadece bir yol olmalı, düğümler arasındaki yolda döngü (cycle) olmamalıdır.

Ağaç veri yapısında bilinmesi gereken başlıca kavramlar aşağıda listelenmiştir:

• Kök (Root): Bir ağacın en üst noktasında bulunan düğümdür.
• Dal (Edge): Düğümleri birbirine bağlayan kenara verilen isimdir.
• Yol (Path): Birbirleri ile bağlantılı dal dizisine yol adı verilir.
• Yol Uzunluğu (Length of a Path): Bir yolu oluşturan dal dizisindeki dal sayısıdır.
• Ebeveyn (Parent):Bir düğümden önce yer alan ve o düğüme bir dal ile bağlı olan düğüme ebeveyn denir. Kök hariç her düğümün bir ebeveyni bulunmaktadır.
• Çocuk (Child): Bir düğümden sonra yer alan ve o düğüme bir dal ile bağlı olan düğüm/düğümlere çocuk denir.
• Ağaç Yüksekliği (Height of a Tree): Bir ağacın kökünden ağaçtaki en alt çocuğa kadar olan yolun uzunluğudur.
• Düğüm Yüksekliği (HeightofaNode): Bir düğümden ağaçtaki en alt çocuğa kadar olan yolun uzunluğudur.
• Düğüm Derinliği (Depthofa Node): Bir düğümden ağaç köküne kadar olan yolun uzunluğudur.

Bir ağaç veri yapısı, sahip olduğu özellikler ile farklı kategorilere ayrılabilir. Ağaç veri yapısı ikili ağaçlar, ikili arama ağaçları ve AVL ağaçları olmak üzere incelenecektir.

İkili Ağaçlar(Binary Trees): İkili ağaçlar, her bir düğümün 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 şekilde yapılabilmektedir. Kitabımız Sayfa 42, Örnek 3.1’de struct kullanımı ile ikili ağaç veri yapısının nasıl tanımlanabileceği gösterilmiştir

İkili Ağaçlarda Gezinme Yöntemleri: Bir ağacın düğümlerini belirli bir algoritma ve sıra çerçevesinde dolaşma eylemine ikili ağaçta gezinme adı verilir. Bir bilgisayar programındaki ağaç veri yapısında gezinmenin düğümlerde arama yapma, düğümleri kullanıcıya gösterme, düğüm değerlerini ekrana yazdırma gibi çeşitli sebepleri olabilir.

İkili ağaç veri yapısı kendi içerisinde alt ağaçlardan meydana geldiği için, ikili ağaçları gezinmede özyinelemeli fonksiyonlar kullanılır. İkili ağaçlardaki düğümler dolaşılırken farklı yöntemler uygulanabilirken, bilgisayar programında bu işi yapabilmek için kabul görmüş üç gezinme yöntemi bulunmaktadır:

Preorder Gezinme: Bu yöntemde öncelikle kök, daha sonrasında sol alt ağaç, en son olarak da sağ alt ağa üzerinde gezinme yapılır. Bu yöntemi akılda tutmak için “Root–Left–Right” terimini kullanabiliriz.

Inorder Gezinme: Bu yöntemde öncelikle sol alt ağaç, daha sonrasında kök, en son olarak da sağ alt ağaç üzerinde gezinme yapılır. Bu yöntemi akılda tutmak için “Left–Root–Right” terimini kullanabiliriz.

Postorder Gezinme: Bu yöntemde öncelikle sol alt ağaç, daha sonrasında sağ alt ağaç, en son olarak da kök üzerinde gezinme yapılır. Bu yöntemi akılda tutmak için “Left–Right–Root” terimini kullanabiliriz.

İkili Arama Ağaçları: Bu veri yapısında, ikili ağaç özelliklerine ek olarak düğümlerde yer alan veriler arasında büyüklük-küçüklük ilişkisi bulunmaktadır.

İkili ağaç özellikleri taşıyan bir ağacın ikili arama ağacı olabilmesi için ağaçtaki her düğümün, sol alt ağacındaki tüm değerlerden büyük olması, sağ alt ağacındaki tüm değerlerden küçük veya eşit olması gerekmektedir.

İkili Arama Ağacına Düğüm Ekleme: İkili arama ağacına düğüm eklemede, ağacın düğümlerinin değerleri arasındaki büyüklük-küçüklük ilişkisini korumak için eklenecek düğümün yeri tespit edilmelidir. Ağaç boş ise yeni düğüm, ağacın kökü olarak tayin edilir. Ağaç dolu ise ağacın kökünden yola çıkılarak, eklenecek düğümün değeri ile kök düğümün değeri karşılaştırılır. Yeni düğümün değeri kökteki değerden büyükse sağ alt ağaca, küçükse sol alt ağaca doğru ilerlenir. Bu işlem, yeni düğüm için uygun bir yer bulunana kadar tekrarlanır.

İkili Arama Ağacından Düğüm Çıkarma: İkili arama ağacından düğüm çıkarma için öncelikle düğümün ağaçta bulunması gerekir. Düğüm ağaçta yer alıyorsa, ikili arama ağacı özellikleri korunarak çıkarma işlemi gerçekleştirilir. İkili arama ağacından düğüm çıkarırken incelenmesi gereken üç durum vardır:

1. Çıkarılacak düğümün çocuğu yok ise; düğümün ebeveyninin ilgili göstericisi (left veya right) NULL yapılır, düğüm hafızadan silinir.
2. Çıkarılacak düğümün 1 çocuğu var ise; düğümün çocuğundan itibaren olan alt ağaç düğümün ebeveynine bağlanır, düğüm hafızadan silinir.
3. Çıkarılacak düğümün 2 çocuğu var ise düğümün sağ alt ağacındaki en küçük değerli düğüm bulunur, bulunan düğüm ile çıkarılacak düğüm yer değiştirilir, düğüm hafızadan silinir.

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 bulunmamaktadır. N adet düğüme sahip bir ikili ağacın yüksekliği en fazla N-1 olabilir. AVL (Adelson –Velsky – Landis) ağaçları, ikili arama ağaçlarının özel bir türüdür. Bu veri yapısında ağaç içerisindeki denge korunmakta, sol alt ağaç 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:

1. 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.
2. 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.
3. 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.
4. 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:

1. 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.
2. 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.
3. 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.
4. 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:

1. Fonksiyon içerisinde hesaplamalar hızlı yapılmalıdır
2. Hesaplama sonucu üretilen değerlerde minimum çatışma olmalıdır.
3. Özetleme tablosundaki tüm alanlar kullanılabilir olmalıdır.
4. Ö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.

1. Doğrusal Sınama (Linear Probing): F(i)=i
2. Karesel Sınama (Quadratic Probing): F(i)=i2
3. İkili Hash (Double Hashing): F(i)=i*Hash2(i)