LOGO
Veri Yapıları
Yığın
YIĞIN
 Yığın yapısı N tane elemandan oluşan ikili ağaç şeklinde bir
yapıdır.
 Bu iki yapı arasındaki temel farklar:
 İkili arama ağacı, arama temel işlemini hızlı yapmak için
üretilmiş bir veri yapısı iken yığın, bir grup eleman arasından
önceliği en yüksek olan elemanı hızlı bulmak ve bu elemanı
yapıyı bozmadan hızlıca silmek için üretilmiş bir veri
yapısıdır.
 İkili arama ağacında her düğüm sol alt ağacındaki tüm
düğümlerden büyük, sağ alt ağacındaki tüm düğümlerden
küçük iken, yığında her düğüm sol ve sağ alt ağacındaki tüm
düğümlerden büyüktür. Sol ve sağ alt ağaç arasında
büyüklük küçüklük ilişkisi açısından bir zorlama yoktur.
YIĞIN
 İkili arama ağacında düğümleri sol veya sağ çocukları
olabileceği gibi hiç çocuğu olmayabilir. Yığında ise elemanlar
seviye seviye yerleştirlir. Üstteki seviye dolmadan alttaki
seviyede eleman bulunmaz. Dolayısıyla son seviyeden
önceki seviyedeki tüm düğümlerin iki çocuğu vardır.
 Yığınlarda en büyük değerli eleman ağacın kökündeyse bu
sıraya azami-yığın, en küçük değerli eleman ağacın
kökündeyse bu sıraya asgari-yığın denir.
Örnek bir azami-yığın
Örnek bir asgari-yığın
YIĞIN TANIMI
 Azami-yığında ağacın her dalındaki elemanın değeri sol ve
sağ alt dallarındaki elemanların değerlerinden büyük, asgariyığında ise ağacın her dalındaki elemanın değeri sol ve sağ
dallarındaki elemanların değerlerinden küçüktür.
 Bu yapıda dikkat edilmesi gereken husus, ağacın son sırası
hariç her sırasının dolu olmasıdır. Bu yığın yapısının önemli
bir özelliğidir ve bu özelliğinden dolayı yapı, bir dizi halinde
de gösterilebilir.
 Yapılması gereken ağacın kökünden başlayarak ağacın her
sırasındaki elemanları teker teker bir diziye yerleştirmektir.
 Kök eleman sıfırıncı sıraya, sol çocuk birinci sıraya, sağ
çocuk ikinci sıraya gibi.
YIĞIN TANIMI
 Ağacın her dalı ile sol ve sağ çocuklarının dizideki sıra
numaralarına bakıldığında aralarında bir ilişki vardır. x bir
elemanın sıra numarası olmak üzere, sol çocuğun sıra
numarası 2x+1, sağ çocuğun sıra numarası 2x+2 olmaktadır.
YIĞININ EN BÜYÜĞÜNÜ SEÇME VE SİLME
 Azami-yığında en büyük değerli eleman dizini ilk elemanı,
yani ağacın kökündeki elemandır. Bu ilk eleman silindiğinde
dizinin eski yapısına getirilmesi gerekir.
 Ağacın kökündeki eleman silinince ağacın köküne ağacın en
son elemanı yerleştirilir. Fakat bu durumda ağacın en büyük
elemanı en yukarıda olmaz. Bu durumda, sol ve sağ
çocukların değeri daha büyük olanı o elemanın yerine
yerleştirilir ve devam ederek ağacın en altına kadar ilerlenir.
YIĞININ EN BÜYÜĞÜNÜ SEÇME VE SİLME
 Yukarıdaki yığında 16’nın silinmesi aşağıdaki şekillerde
gösterilmiştir.
YIĞININ EN BÜYÜĞÜNÜ SEÇME VE SİLME
YIĞININ EN BÜYÜĞÜNÜ SEÇME VE SİLME
YIĞININ EN BÜYÜĞÜNÜ SEÇME VE SİLME
YIĞININ EN BÜYÜĞÜNÜ SEÇME VE SİLME
YIĞINA YENİ BİR ELEMAN EKLEME
 Bu işlem, ağacın en büyük elemanı silme işleminin tersine
ağacın alt dallarından köküne doğru olmaktadır. Önce yeni
eleman yığının sonuna eklenmekte, yığının özelliğini
bozduğu sürece ebeveyn eleman ile yer değiştirilmektedir.
YIĞINDA ELEMAN ARAMA
 Yığın veri yapısı herhangi bir elemanı hızlı aramak için değil
sadece değeri büyük olan elemanı hızlı getirmek için
tasarlanmıştır. Bu sebeple, ancak yığının elemanlarına tek
tek bakarak istenilen elemana ulaşılabilir.
YIĞINDAKİ BİR ELEMANIN DEĞERİNİN DEĞİŞTİRİLMESİ
 Bir yığında herhangi bir elemanın değeri değiştirildiğinde iki
durum söz konusu olabilir; değer artmış veya azalmıştır.
 Yığının özelliği bozulmamışsa bir şey yapmaya gerek yoktur,
aksi taktirde yığının özelliğinin yeniden oluşturulması gerekir.
 Birinci durumda elemanın yeni değeri yığının özelliğini
bozmuşsa ebeveyn ile yer değiştirilmesi gerekir.
 Aşağıda 14 değeri 18 olarak değiştirilmiştir.
YIĞINDAKİ BİR ELEMANIN DEĞERİNİN DEĞİŞTİRİLMESİ
YIĞINDAKİ BİR ELEMANIN DEĞERİNİN DEĞİŞTİRİLMESİ
YIĞINDAKİ BİR ELEMANIN DEĞERİNİN DEĞİŞTİRİLMESİ
YIĞINDAKİ BİR ELEMANIN DEĞERİNİN DEĞİŞTİRİLMESİ
 İkinci durumda ise yeni elemanın çocuklarından hangisi daha
büyük ise onunla yer değiştirilmesi gerekir.
 Aşağıda 14 değeri 3 olarak değiştirilmiştir.
YIĞINDAKİ BİR ELEMANIN DEĞERİNİN DEĞİŞTİRİLMESİ
YIĞINDAKİ BİR ELEMANIN DEĞERİNİN DEĞİŞTİRİLMESİ
YIĞINDAKİ BİR ELEMANIN DEĞERİNİN DEĞİŞTİRİLMESİ
YIĞINDAKİ BİR ELEMANIN DEĞERİNİN DEĞİŞTİRİLMESİ
 Böylece yığında ekleme, silme, değer değiştirme O(logN) ve
arama O(N) kadar zaman alır.
ÖDEV
 9, 11, 0, 13, 5, 6, 7 sayılarının boş bir yığına eklenmesi ile
ortaya çıkan yığın yapısını gösteriniz. Sonra kökü siliniz.
LOGO
Download

LOGO Veri Yapıları