AVL Trees / Slide 1
Silme
Anahtar hedefi silmek için, x yaprağında buluruz ve sonra sileriz.
Dikkat edilmesi gereken iki durum vardır. (1) Hedef bazı iç düğümlerde bir anahtar olabilir.
(bahsedilen mantığa göre yeni elemanla yer değiştirmesi gerekir.)
(2) x yaprağından hedefi sildikten sonra, M/2 - 1 anahtardan daha az eleman içerirse (düğümleri birleştirmek gerekir. )
AVL Trees / Slide 2
Durum (1)
Verilen mantığa göre, hedef x in enfazla bir y atasında anahtar olarak görülebilir. Üstelik, düğüm y’yi ziyaret etmiş olmamız gerekir ve hedefi onun içerisınde görmüş olmamız gerekir. Bu yüzden x düğümünden sildikten sonra, y’ ye doğrudan erişebiliriz ve x’deki yeni en küçük elemanla yer değiştirebiliriz.
AVL Trees / Slide 3
Durum (2): Çok az anahtarı olan yaprakların düzenlenmesi
Farzedelimki bir yapraktan hedef anahtarlı bir kayıdı sildik
u M/2 - 2 kadar (çok az) anahtarı olan bir yaprak olsun.
v, u nun bir kardeşi olsun k u ve v yi ayıran ve u ve v nin ebeveyninde
olan bir anahtar (işaretçi) olsun. Bu halde iki durum vardır.
AVL Trees / Slide 4
Çok az anahtarı olan yaprakların düzenlenmesi
Durum 1: v M/2 kadar veya daha fazla anahtar içerir ve v, u ‘nun sağdaki kardeşidir. Ensoldaki kaydı v’den u’ya taşı Ebeveyn’de u ve v yi ayırabilmek için gerekli
anahtarı v’nin en küçük yeni elemanı olarak belirle
Durum 2: v M/2 veya daha fazla anahtar içeriyor ve v, u’nun soldaki kardeşidir. Ensağdaki kaydı v’den u’ya taşı Ebeveyn’de u ve v yi ayırabilmek için gerekli
anahtarı u’nun en küçük yeni elemanı olarak belirle
AVL Trees / Slide 5
Silme Örneği
15 silinmek isteniyor
AVL Trees / Slide 6
9 silinmek isteniyor
AVL Trees / Slide 7
10 silinmek isteniyor
AVL Trees / Slide 8
AVL Trees / Slide 9
AVL Trees / Slide 10
İki yaprağın birleştirilmesi
En az M/2 kadar anahtarı olmayan iki kardeş birleştirilir.
Durum (1): Farzedelimki u’nun sağdaki kardeşi v tam olarak M/2 -1 anahtar içermektedir. u ve v birleştirilir u’daki anahtarları v’ye taşı Ebeveyndeki u’ya olan işaretçiği kaldır. u’nun ebeveynınden u ve v yi ayıran anahtarı sil
AVL Trees / Slide 11
İki yaprağın birleştirilmesi
Durum (2): Farzedelimki u’nun solundaki kardeşi v tam olarak M/2 -1 anahtar içermektedir. u ve v birleştirilir u’daki anahtarları v’ye taşı Ebeveyndeki u’ya olan işaretçiği kaldır. u’nun ebeveynınden u ve v yi ayıran anahtarı sil
AVL Trees / Slide 12
Örnek
12 silinmek isteniyor
AVL Trees / Slide 13
Devamı
u v
AVL Trees / Slide 14
Devamı
AVL Trees / Slide 15
Devamı
çok az anahtar! …
AVL Trees / Slide 16
İç bir düğümden bir anahtarın silinmesi
Farzedelim ki iç düğüm u’dan bir anahtar silindi ve u’ daki anahtar sayısıM/2 -1 ‘den az oldu.
Durum (1): u kökse Eğer u boş ise, u’yu kaldır ve onun çocuğunu yeni
kök yap
AVL Trees / Slide 17
İç bir düğümden bir anahtarın silinmesi Durum (2): u’nun sağ kardeşi vM/2 kadar veya daha
fazla anahtara sahipse u ve v’nin ebeveyninden u ve v arasındaki ayırıcı anahtarı
u’ya taşı. v’nin en soldaki çocuğunu u’nun en sağdaki çocuğu yap ebeveyne u ve v yi ayırmak için v’nin en solundaki anahtarı
taşı. Durum (2): u’nun sol kardeşi v M/2 kadar veya daha
fazla anahtara sahipse u ve v’nin ebeveyninden u ve v arasındaki ayırıcı anahtarı
u’ya taşı. v’nin en sağındaki çocuğunu u’nun en solundaki çocuk yap ebeveyne u ve v yi ayırmak için v’nin en sağındaki anahtarı
taşı
AVL Trees / Slide 18
…önceki örnekten devam edersek
u v
case 2
AVL Trees / Slide 19
devamı
AVL Trees / Slide 20
Durum (3): u ve v kardeşleri tam olarak M/2 - 1 anahtar içeriyorsa u ve v’nin ebeveyninden u ve v arasındaki ayırıcı
anahtarı u’ya taşı. u’daki anahtar ve çocuk işaretçilerini v’ ye taşı Evebeynden u’ ya olan işaretçiyi kaldır.
AVL Trees / Slide 21
Örnek
5 silinmek isteniyor
AVL Trees / Slide 22
Devamı
uv
AVL Trees / Slide 23
Devamı
AVL Trees / Slide 24
Devamı
u v
Durum 3
AVL Trees / Slide 25
Devamı
AVL Trees / Slide 26
Devamı
