Skip List Veri Yapısında P Eşik Değerlerinin Rastgele Seviye Oluşturma ve Performansa Etkisi

Authors : Mustafa AKSU, Ali KARCI, Şaban YILMAZ

Pages : 148-153

View : 15 | Download : 9

Publication Date : 2013-12-01

Article Type : Other Papers

Abstract :Skip list veri yapısında bağlı listeler kullanılır. Düğümler, birbirine bağlı listeler halinde farklı seviyelere yerleştirilir. Bu seviyeler sayesinde eleman arama, ekleme, silme gibi işlemler kolayca (O(lg N)) yapılabilir. Bununla birlikte, bu veri yapısında seviyelere düğüm ekleme işleminde olması gerekenden yüksek seviyeler üretilebilmektedir. Yüksek seviyeler üretilmesi bu veri yapısının performansını olumsuz etkilemektedir. Bu makalede rastgele seviye üretme problemi ele alınarak farklı “p” eşik değerlerinin (0.1, 0.25, 0.5, 0.75, 0.9 gibi) performansı nasıl etkilediği ele alınıp çözüm önerilmiştir. Skip list veri yapısındaki yüksek seviye üretme problemi optimum p eşik değeri bulunarak çözülmüştür. Böylece, Skip list veri yapısı için p eşik değerlerine bağlı olarak ideal seviyeler oluşturulmuştur.
Keywords : Skip list, rastgele seviye, p eşik değerleri, ideal seviye, optimizasyon