Bir temsili değiştirme(Represantation)’dur. Binary tree olarak tanımlanabilir. Her bir düğüme bir anahtar atanır
Yüklə 37,12 Kb.
|
- Bu səhifədəki naviqasiya:
- Dengeli Arama Ağaçları
|
Heap Sort Bir temsili değiştirme(Represantation)’dur. Binary tree olarak tanımlanabilir. Her bir düğüme bir anahtar atanır. Q(logn) sıralama algoritmasıdır. Heap olarak söyleyeceğimiz veri yapısını kullanır. Bir diziden bir heap dönüştürür ve sonra sıralamayı kulayca yapar. Heap’in diğer önemli kullanımı “Priority queue”’dir. Priority queue şu operasyonları yapar. 1.Find(Bul) en yüksek önceliğe sahip elemanı 2.Deleting(Sil) en yüksek önceliğe sahip elemanı 3.Adding(Ekle) çoklu kümeye yeni bir eleman Heap iki durumdan oluşur. -Shape propenty: Binary tree tamdır. Tüm sayılar sadece bazı en sağdaki yapraklar yanlış olduğu yerlerdeki son seviye dışında tamdır. -Parental domirance(veya heapproperty): Her düğümdeki anahtar onun çocuklarındaki anahtarlara eşit veya daha büyüktür. 
1.n düğümlü tam bir binary tree de ağırlık [log2n]’dir. 2.Bir heap’in kökü her zaman onun en büyük elemanını içerir. 3.Tüm torunları ile heap bir düğümü bir heap’dir. 4. Bir heap bir dixi olarak yukarıdan aşağıya ve soldan sağa uygulanır. 0. Eleman H[0] kullanılmaz veya tümünden daha büyük bir sayı içerir. a. Parental node anatarları ilk[n/2] pozisyonunda olacak ve yapraklar son [n/2] pozisyonunda olacak. b. i( 1≤i ≤[n/2]) indeksdeki anahtarların çocukları 2’i ya da 2i+1 pozisyonunda olacak. . i( 2≤i ≤n) indeksindeki anahtarın parent 1,[i/2] pozisyonunda olacak. H[i]≥max{H[2i],H[2i +1]} for i =1,...,[n/2] Bir hep bir diziye dönüştürmenin iki yolu vardır. Dizi: 2,9, 7, 6, 5, 8 
9, 6, 8, 2, 5, 7 Bu süreç “Heapifying” metod “bottom up heap construction”’dır. Algoritma HeapBottomUp(H[1..n]) //Verilen dizinin elemanlarında heap yapma // bottom-up algoritma //Input: H[1..n] bir dizi //Output: H[1..n] heap for i ←[n/2]downto 1do k←i; v←H[k] heap←false while not heap and 2∗k≤n do j ←2∗k if j if v≥H[j] heap←true
else H[k]←H[j]; k←j H[k]←v
Binary tree n=2k-1 düğüme sahiptir. Ağırlık h=[log2n] veya h=[log2(n+1)]-1=k-1’dir. Ağacın her i seviyesi h yaprağı seyyah eder. En kötü durumda bir sonraki seviyeye inmek için 2 karşılaştırma gerekir. Daha büyük çocuk bulmak için veya takasa karar vermek için level i seviyesinde bir anahtara dahil olan anahtar karşılaştırma sayısı 2(h-i)’dir. bu yüzden en kötü durumda toplam karşılaştırma sayısı
Büyüklüğü n olan bir heap 2n’den daha az karşılaştırma yapar. İkinci bir metot:heap inşa etmek yukarıdan aşağıya heap inşa etmek (topdownheep construction) Ekleme işlemi heap ağacının ağırlığından daha fazla karşılaştırma gerektirmez. Bu yüzden O(logn)’dir. Bir heapten max anahtar silme:
1.adım: heapin son anahtar K’sıyla kökün anahtarını takas et. 2.adım: 1. İle heap boyutunu azalt
3.adım: K aşağı doğru eleyerek Heapfy oluştur. Daha önce bottom-up da yaptır. Bu K’nın paralel dominance doğrulayacak. K’nin parantel dominance bulana kadar tekrar eder Silmek istiyorsak;
Verimlilik O(logn )yapıldıktan ve ağaç i azaldıktan sonra silme verimliliği hepify oluşturmak için yapılacak anahtar karşılaştırmalara bağlıdır. Bu heap’in ağırlığından daha fazla karşılaştırma yapılmaz. Bu yüzden O(logn)’dir. Heapsort: 1964’de Willions tarafından keşfedildi. İki aşamalı bir algoritmadır.
1.Aşama:(heap inşa etme): verilen bir dizi için bir heap oluşturur. 2.Aşama:(maximum silme): kalan heapden n-1 kez kök silme operasyonunu uygula
Heap Construction En kötü durum Heap Construction O(n)
Mximum Deletions: Karşılaştırm C(n)
Ağacın ağırlığı [logn] C(n)£O(nlogn) O(n)+O(nlogn)=O(nlogn)
Eğer sayaç i*2 dizinin eleman değeri n’den büyükse bu bir yapraktır. Analız: Heap derinliği h ise 2h’den fazla karşılşatırma olmaz. Aşağıdan itibaren 2 seviyeden itibaren yapılacak bunun anlam heap derinliği 1. h=logN olur. Root 1 altında 2 çocuk anltında 4 çocuk…  2.0(2-1)-2[(0-2)2n+2]
Dengeli Arama Ağaçları Binary tree ağacını daha önce görmüştük. Sıralı liste üzerindeydi. Ağacın kökünden itibaren sol taraf sağ taraftan daha küçüktür. Bir diziden binary tree ağacını dönüşüm temsili değiştirme için iyi bir örnektir. Buiz böyle bir dönüşümle ekleme, silme ve arama işlemlerinde zaman verimliliği kazandık. Q(logn)’dir. En kötü durumda bu operasyonda Q(n)’dir. Çünkü ağaç dengesiz hale gelince n-1 ağırlığa sahip olur. 2 tane yaklaşıma sahibiz
AVL Tree de her düğümün sol ve sağ alt ağaçları arasındaki fark 1’i aşmaz. Red Black Tree aynı düğümün alt ağacının 2 katı kadar olan bir alt ağacının ağırlığına tolere eder. Eğer silme ve ekleme dengeyi bozarsa, dengeyi düzeltmek anlamına gelen rotation olarak çağırılır. Özel dönüşüm ailesi tarafından yerinde yapılandırılır.
Böyle ağaçlar 2-3 trees, 2-3-4 trees’tir. Ve B-tree’dir. ağacın tek bir düğümde izin verilen eleman sayısı farklıdır. 
AVL Trees Blance Faktörü: heighleftchild- heighrightchild Balance faktörü -1, 0, 1 olabilir. Yani hL-hr <=1 olmalı 
Dengeli olmalı. Çünkü Q(logn) sağlamalıyız. Boş ağaç ağırlığı -1’dir.
AVL Ağacına Eleman Ekleme Eleman ekleme AVL Ağacını dengesizleştirir. Ağaç dengesizleşirse rotation yapılır. Ekleme işleminden sonra düğümün BF 2 veya -2 ise düğüm dengesizlerdendir. 4 farklı rotasyon vardır. 1.R-rotasyon veya tek sağa döndürme Ekleme yapılamdan önce +1 dengeli bir köke sahip ağacın son child’nin sol alt ağacına yeni bir ekleme yapılırsa gerçekleşir. Bu durumda kökün bağlandığı kenar sağ çocuk olur. 
Ekleme yapılmadan önce -1 dengeli bir köke sahip olan ağacın sağ child’e sağ sağ alt ağacına yeni bir ekleme yapılır. Kökün bağlandığı kenar sağ çocuğu olur.
2 döndürmenin kombinasyonudur. Önce sol döndürme sonra sol döndürme
Çıktı alınacak AVL ppt Silme İşleminde 3 durum oluşur.
Örn:Çıktı AVLppt Rotasyon İşleemlerinde Ağırlık Kaydırma 
Örn: Ekleme 
Ekleme Sıra 5,6,8,3,2,4,7 Yüklə 37,12 Kb. Dostları ilə paylaş:
|
