Splay ağacının temel mantığı en son aranan elemana en kolay ulaşmayı sağlamaktır. Splay Ağacı oluştururken 3 temel kuraldan bahsedilir. Bu kuralları örneklerle beraber inceleyelim.
(1-5-3-7-6-4-11-0-2)
Sayılarını sırasıyla Splay Ağacına ekleyeceğiz :
1.Adım :
İlk ekleyeceğimiz sayıyı ağaca ekliyoruz.
2.Adım :
2. Eklediğimiz sayı ilk sayıdan büyükse sağ tarafa , küçükse sol tarafa ekleme işlemini yapıyoruz. 5 > 1 olduğu için 5'i 1'in sağ tarafına ekliyoruz.
Ardından Splay ağacının mantığı olan son kullanan elemanı en üste taşıma işlemini yapmamız gerekiyor.. Burada yapılan işleme ZIG denir. Burada Zig Left işlemi uygulanacak... Son elemanı başa ekledikten sonra şeklimiz şu hale gelecek :
3.Adım :
Bu adımda 3 sayısını ağaca ekleyelim. 5 ' ten küçük olduğu için sol tarafa gidiyoruz.. 5'in sol tarafında 1 var. 3 ile 1 ' i kıyaslıyoruz.. 3 > 1 olduğu için 3'ü 1'in sağ tarafına yerleştiriyoruz. Şeklimiz şu şekilde oluyor :
Şimdi 3 ' ü en başa geçirmemiz gerekiyor. 3'ün en üste geçmesi için önce sola sonra sağa gitmesi gerekiyor. Bu duruma ZIG-ZAG denir. (Aynı şekilde önce sağa sonra sola gitmeside ZIG-ZAG olarak adlandırılır.)
Son eklenen eleman ZIG-ZAG yapılarak geldiği yere eklenir. Yani örneğimizde 5'in yerine gelir... Ardından kontroller sağlanır... 1 < 3 olduğu için 1 soluna , 5 > 3 olduğu için 5 sağına eklenir. Şeklimiz şu hale gelir :
4.Adım :
Bu adımda 7 elemanını ağaca ekleyelim. En üstten kontrole başlayalım. 7 ile 3 ü kıyasladığımızda 7 > 3 olduğunu görüyoruz. 3'ün sağ tarafına gidiyoruz. Sağ tarafta 5 var.. 7 ile 5 ' i kıyaslıyoruz. 7 > 5 olduğu için 7' yi 5'in sağ tarafına ekliyoruz. Şeklimiz şu hale geliyor :
Şimdi sırada 7'yi en üste taşıma işlemi var. Burada dikkat ederseniz 2 kez sola kayarak en üste gelmesi gerekiyor. Bu işleme ise ZIG-ZIG yöntemi denir. (2 kez sağa gelme işlemi de ZIG-ZIG)
ZIG-ZIG yönteminde öncelikle 5 elemanı başa geçer. 5 elemanı başa geçer. 5 başa geçince solunda sırası ile 3 ve 1 sağında ise 7 elemanı bulunacaktır.
Ardından 7 elemanımız başa geçer ve şeklimiz şu hale gelmiş olur :
5.Adım :
Bu adımda 6 elemanını elemanını Ağacımıza ekleyelim. 6 yı kontrol ettiğimizde 5 elemanının sağ tarafına eklememiz gerektiğini görüyoruz. Şeklimiz şu hale geliyor :
Şimdi 6 ' nın en başa geçmesi gerekiyor. 6 en başa geçmek için önce sola sonra sağa gitmesi gerek. Yani ZIG-ZAG yöntemi uyguluyoruz. ZIG-ZAG yöntemi uyguladıktan sonra şeklimiz :
6.Adım :
Bu adımda ise önce ZIG-ZAG ardından ZIG işlemi yapmamız gereken bir eleman ekleyelim. Hangi elemanı eklersek bu işlemleri gerçekleştirmek zorunda kalırız? Tabii ki 4 :) 4' ü ağacımıza ekleyelim :
4 elemanını ağacımıza ekledikten sonra öncelikle ZIG-ZAG işlemi yapmamız gerekiyor. Önce sola sonra sağa gidip 5 ' i yerinden ediyoruz :) Şeklimiz şu hale gelmiş oluyor :
Şimdi ise ZIG işlemi yaparak tahtımıza 4 elemanını oturtuyoruz . Ağacımızın yeni şekli şöyle olmuş oluyor :
Basit bişeyi hatırlatayım . Belki anlayamayan , dikkat edemeyen birkaç kişi çıkar diye söyleme ihtiyacı duydum. Burada 5 sayısı 4 ten büyük olduğu için 4'ün sağ tarafına , 6 ' nın sol tarafına eklendi. Bazen arkadaşlar dikkatsizlik yapıp 3'ün sağ tarafına ekliyor. Tüm ağaç sistemi bozuluyor :)
7.Adım :
Şimdi de önce ZIG-ZIG ardından ZIG işlemi yapmamız gereken bir sayı ekleyelim ağacımıza. Bu sayıda tabii ki 7 ' den büyük herhangi bir sayı olabilir.. Biz 11'i ekleyelim.. 11 ' i ağacımıza eklediğimizde şeklimiz :
Şimdi 11 ' i başa geçirmek için öncelikle ZIG-ZIG işlemini gerçekleştirelim. ZIG-ZIG işlemini gerçekleştirdiğimizde öncelikle 7 , 6'nın yerine geçecek.. 6 ve 5 , 7'nin solunda , 11 ise sağında olacak . Ardından 11 ' de 7 nin yerine geçecek ve şeklimiz şu hale gelmiş olacak :
Son olarak 11 ' i tahta geçirme vaktimiz geldi :) Tahta geçen sayının tahtı devraldığı sayı ile bağı asla kopmaz. Dolayısıyla şeklimiz şu hale gelmiş oluyor.
8.Adım :
Şimdi de 2 adet ZIG-ZIG yapmamız gereken bir sayı ekleyelim. Bu sayı da 0 olsun. 0 ' ı ağacımıza eklediğimizde şeklimiz şu hale gelmiş olacak :
İlk ZIG-ZIG işlemimizde şeklimiz :
İkinci ZIG-ZIG işlemimizde 0 tahta geçer ve şeklimiz şu şekilde olmuş olur:
9.Adım :
Bu seferde 2 kez ZIG-ZAG yöntemi izleyeceğimiz bir sayı ekleyelim.. 2 sayısını ağacımıza eklediğimizde :
2 sayısının tahta geçmesi için 2 kez ZIG-ZAG yapması gerek... İlk ZIG-ZAG'da 1' in yerini , ikinci ZIG-ZAG'da ise tahtı ele geçirecek. İlk ZIG-ZAG ' ın sonucunda ağacımız :
İkinci ZIG-ZAG'dan sonra ağacımız :
Şimdi siz :
Ağaca öncelikle 13 elemanını ekleyin (13 Eklendikten sonra Splay Ağacı)
Ardından 21 elemanını ekleyin (21 Eklendikten sonra Splay Ağacı)
Ardından 12 elemanını ekleyin (12 Eklendikten sonra Splay Ağacı)
Ardından 17 elemanını ekleyin (17 Eklendikten sonra Splay Ağacı)
ve son olarak
14 elemanını ağaca ekleyin (14 Eklendikten sonra Splay Ağacı)
