BST(Binary Search Tree)'lerde
silme(Deletion) işlemi yapılırken eğer silinen elemanın tek
çocuğu varsa silinen node'un yerine bu eleman yerleştirilerek ağaç
düzenlenmiş olur.Ancak bu elemanın iki çocuğu varsa ne olur ? Bu
tür durumlar için Hibbard Deletion adında bir yöntem uygulanır
ki çok basit bir yöntemdir.Silinen elamanın sağındaki kolun en
küçük elemanı bulunup o node'a yerleştirilir.
Örnek :
Örnek silinmek istenen node 67 bu elemanın sağında ki elemanları bir ağaç gibi farz edip o ağacın en küçük elemanı olan 79'u silinen node'un yerine yerleştiriyoruz ve ağacımız şu şekili alıyor ;
Heap Türkçeye geçmiş haliyle yığın
ağacı demektir.Yığın ağaçları verileri dengeli bir ikili
ağaçda saklayarak bir veri yapısı oluşturur.Bu yapıda node'lar
aynen öncelikli kuyruk gibi öncelik özelliğene göre
doldurulur.Aşşağıda basit bir yığın ağacı var.
Yukarıdaki ağaç dizidede [64 , 25 ,
52,11,9,32] şeklinde tutulabilir.
Her bireyin üstündeki node
kendisinden büyük şekilde sıralanmış gördüğünüz üzere.Bu
ağacın bu hale gelmesi için en alt seviyedeki ebeveynden
başlarayarak karşılaştırma ve değiştirme işlemleri
yapılır.Ardından bir üst node geçilir.Bir eleman aşşağı
doğru iniyorsa bir alttındaki elamanlarlada karşılaştırma ve
değiştirme işlemleri uygulanır eğer karşılaştırma olumsuz
sonuçlanmışsa diğer aynı seviyedeki diğer noda ,aynı seviyede
node kalmamışsa üst seviyedeki node'a geçilir.Örnekle
pekiştirelim.
En alt seviyenin bir üst seviyesinden
ve soldan başlayarak başlıyoruz karşılaştırmaya.Alttaki node
lardan varsa büyüğü veya ikiside büyükse en büyüğüyle
değiştirme işlemi yapıyoruz.34 sayısının alt elemanları
olduğu için karşılaştırmayı yaptık ancak diğer 2,3,4 diye
numaralandırdığın nodeların alt elemanı olmadığı için
karşılaştırma yapamıyoruz.Ardından bir üst seviyeye çıkıp
aynı işlemleri tekrarlıyoruz .Root(kök) elemanada aynı işlemi
yaptıktan sonra gördüğünüz üzere tüm ebevynler çocuklarından
büyük durumdalar.
Heap sort ? Heap sortta ise en üstteki
elemanı en alttaki ve en sağdaki node ile değiştiririz.Ve büyük
elemanı heapdan çıkarırız.En üstteki elemana üstteki heap
oluştururken yaptığımız aşşağıya doğru karşılaştırma ve
değiştirme işlemlerini yaparız.Tekrardan en üstteki elemana aynı
işlemleri yaparak heapı boşaltırız ve heap sort işlemi
başarıyla tamamlanmış olur.Resim çizimim fazla iyi olmadığı
için aşşağıdaki videyu örnek olarak vereceğim yukarıdaki
resimlerin iğrençliklerinden dolayıda kusura bakmayın :)
Quick-sort(hızlı sıralama) algoritmasının en büyük özelliklerinden birisi parçalama metodudur ki quicksort algoritması divide and conquer(parçala ve feth et) algoritmaları kategorisine girer.Normal parçalama işlemini yaparken eğer dizimizde birden fazla aynı değerden varsa(duplicate keys) algoritmamızı daha hızlı hale çevirmek için Djktra yeni bir yöntem geliştirmiştir.Bu duplicate değerleri dizinin ortasında toplayıp sağına ve soluna iki parça oluşturarak diziyi 3 parçaya bölme yöntemine 3-way partitioning yöntemi denir.Şu an pek lambanın parlamadığının farkındayım.Hemen nasıl yapıldığını öğrenerek lambanın parlaklığını arttıralım.
Buraya kadar bildiğimiz quicksort algoritmasındaki gibi değişimleri yaptık sadece seçtiğimiz en sağdaki duplicate key değerini atlayarak.
Ancak swap yaptığımız elemanlardan birisiseçtiğimiz duplicate değerlerden birisiyse değiştirdiğimiz yöndeki en uçtaki duplicate olmayan eleman ile yerlerini swap yapıyoruz.
Hatta iki duplitace eleman değişitirilse bile aynı işlemi onlarada uygulayarak yer değiştirebilecekleri en sağ ve en soldaki elemanlarla swap işlemi yapılır.
Görüldüğü gibi ortada çıplak gibi bir eleman kaldı bu eleman swap yapacak bir sevgili bulamayacağından artık yöntemin son basamağına geçeriz.En soldaki duplicate değerleri bu çıplak kalan elemanın soldaki elemanlarla tek tek swap yaparız en sağdaki duplicate değerleri de bu çıplak eleman dahil olmak üzere sağa doğru yönelerek değişimleri tamamlarız ve 3-way partioning yöntemimiz sonlanarak parçalama işlemimiz tamamlanmış oluyor.
