Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde, özellikle veri yapısı (data structures) konusunda kullanılan bir yöntemdir. Basitçe bir bağlı listeye (linked list) erişimi hızlandırmak amacıyla, listenin üzerinde bir fihrist (index) oluşturmayı hedefler.
Örnek olarak kullanacağımız sayılar aşağıdaki şekilde verilmiş olsun :
2,7,15,37,43,98,123,155
Bu sayıları tutan ve hızlı bir şekilde arama yapan veri yapısını geliştirmek istiyoruz. Örneğin bu sayıları bir dizi üzerinde tutabiliriz. Dizi üzerinde tutulması halinde ikili arama algoritması (binary search) kullanılarak ardışık erişime göre (sequential access) daha hızlı erişim sağlanabilir.
|
2 |
7 |
15 |
37 |
43 |
98 |
123 |
155 |
Ancak yukarıdaki şekilde bir dizinin (array) kullanılması halinde, silme işlemleri problem oluşturmaktadır. Örneğin 7 sayısını diziden sildiğimiz zaman bütün dizinin kaydırılması gerekebilir.
Alternatif olarak bir bağlı liste üzerinde veriler tutulabilir. Örneğin aşağıdaki şekilde bir bağlı listemiz bulunsun:
Yukarıdaki şekilde verilmiş olan sıralı bir listeyi ele alalım. Bu liste üzerinde arama yapmak için klasik olarak ardışık arama (linear search) kullanılabilir. Bu durumda da listenin sonudaki elemana erişmek için bütün listenin dolaşılması gerekecektir. Erişim zamanı uzamaktadır.
Diğer bir alternatif ise sayılardan bir kısmını bir ağaç şeklinde listeye kolay erişim için tutmak olabilir. Ağaç kullanımı bağlı listeye göre avantajlı olmakla birlikte, silme işleminin karmaşıklığı yüksektir. (detaylı bilgi için örneğin ikili arama ağacı başlıklı konuyu okuyabilirsiniz).
Çözüm olarak atlamalı listeyi (skip list) inceleyelim. Öncelikle bilmemiz gerekir ki bu liste yapısı tesadüfi özelliktedir. Yani hangi sayıların daha üst seviyede bulunacağı tesadüfen belirlenir.
Yukarıdaki şekilde, ikinci bir bağlı liste oluşturulmuştur. Oluşturlan ikinci bağlı liste, orjinal listenin elemanlarından bazılarını içermekte olup, bazı elemanları atlamaktadır.
Aslında yukarıdaki listenin tam olarak yorumlanmasını ikili düğümler olarak yapmak gerekir. Diğer bir deyişle bütün düğümlerden tek gösterici (pointer) çıkıp sıradaki düğümü işaret ederken, bazı düğümlerden çift gösterici çıkmaktadır. Örneğin 37 değerini taşıyan düğümden çıkan bir gösterici 43 düğümünü gösterirken diğeri 123 düğümünü göstermektedir.
Yapıyı daha iyi anlayabilmek bir sayının aranmasını adım adım inceleyelim. Örneğin 43 sayısını, yukarıdaki liste yapısını kullanarak aradığımızı düşünelim.
Öncelikle yukarıdaki listede bir seyyar (iterator) çıkarak listedeki sayıları dolaşmaya başlar. Seyyar yapımızda çift gösterici (pointer) tutuyoruz ve göstericilerden birisi arkadan geliyor. Bunun sebebi aranan değerin hangi aralıkta olduğunu bulmak. Diğer bir deyişle bağlı liste tek yönlü olduğu ve aradığımız değerden büyük bir değer bulduğumuzda geri döenemediğimiz için son geldiğimiz düğüme bir gösterici bırakıyoruz.
Öncelikle üst seviyedeki liste üzerinde arama işlemine başlıyoruz. Aranan sayı 43 ve şu anda seyyar değerimiz 7’yi göstermekte, sonraki düğüme ilerliyoruz:
Aranan değer 43 ve şu anda bakılan değer 37, aradığımız değer hala daha büyük.
İki göstericimiz de ilerletiliyor ve bu aşamada duruyoruz. Sebebi aradığımız değerden daha büyük bir değer bulmuş olmamız (123 > 43). Dolayısıyla aradığımız sayının hangi aralıklta olduğunu biliyoruz ve listedeki bir alt seviyeye geçiyoruz.
Seyyar göstericisinin, 37 düğümündeki alt seviyeden devam etmesi sonucunda, sıradaki ilk düğüm olan 43 bulunur ve aradığımız değere ulaşmış oluruz.
Yukarıdaki atlamalı liste yapısını bir adım daha ilerleterek bir seviye daha yükseltebiliriz:
Örneğin yukarıdaki temsili resimde, 37 düğümü 3 sevilelidir (3 gösterici çıkmaktadır). Bu durumda arama işlemi önce buradan başlayacak (örneğin 43’ü aradığımızı düşünelim) ardından 37’nin sonraki değeri NULL olduğu için alt seviyeye geçilecek (çünkü 43, 37’den büyüktür). Ardından ikinci seviyeye iniliecek ve 37’nin sonraki değerine bakılacak, Bu değer 123 olduğu için ve 43 sayısı 37 ile 123 arasında olduğu için yine bir alt seviyeye inilecek ve sonunda 43 değeri bulunacaktır.
Düğümlerin neye göre seçildiğine gelince. Öncelikle en alt seviyedeki düğümlerden bazıları rast gele olarak seçilir ve bir üst seviyeye çıkarılır (2. Seviye). Sonra 2. seviyede bulunan düğümlerden bazıları rast gele olarak seçilip bir üst seviyeye çıkarılır. Ve bu işlem istenilen seviye kadar devam eder.