Geri Dön

Atlamalı halka: Dairesel ve atlamalı liste temelli yeni bir veri yapısı

Skip ring: A new data structure based on circular and skip lists

  1. Tez No: 444268
  2. Yazar: MUSTAFA AKSU
  3. Danışmanlar: PROF. DR. ALİ KARCI
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2016
  8. Dil: Türkçe
  9. Üniversite: İnönü Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 113

Özet

Atlamalı liste (skip list) veri yapısında bağlı listeler kullanılır. Katmanlı bir yapıdan oluşur ve en alt katmanda tüm düğümler bulunur; bu düğümler üst katmanlara doğru yarıya düşürülerek piramit şeklinde bir yapı oluşturulur. Böylece arama, ekleme, silme işlemlerinde kolaylık sağlanması amaçlanır. Bunun yanında bu veri yapısı daha da iyileştirilebilir. Bu tez çalışmasındaki amacımız; Atlamalı liste veri yapısını analiz ederek bu veri yapısındaki problemleri tespit edip, tespit edilen problemleri çözerek atlamalı liste veri yapısında iyileştirmeler yapmak ve daha sonra bu iyileştirmeleri önereceğimiz yeni veri yapısına uygulamaktır. Atlamalı listedeki iyileştirmeler dikkate alınarak önerilen yeni veri yapısı atlamalı halka (skip ring), dairesel bağlı liste ve atlamalı liste veri yapılarından faydalanılarak oluşturulmuştur. Önerdiğimiz yeni veri yapısı koni şeklinde birbirine bağlı katmanlar halinde dairesel bağlı listelerden oluşur. Böylece N elemanlı bir atlamalı halka veri yapısında arama, ekleme, silme işlemlerinin zaman karmaşıklığı O(lgN) olur. Önerilen yeni veri yapısı uygulamalı olarak ikili arama ağaçları, kırmızı-siyah ağaçlar ve atlamalı liste veri yapıları ile kıyaslanmış sonuçları incelenmiştir. Ayrıca atlamalı halka temelli yeni bir sıralama ve arama algoritması önerilmiştir. Önerilen bu algoritmalar mevcut sıralama ve arama algoritmaları ile uygulamalı karşılaştırılmıştır. Sonuç olarak, atlamalı liste ve dairesel bağlı listelerin özeliklerinden faydalanılarak geliştirilen atlamalı halka (skip ring) veri yapısı ağaç temelli bazı veri yapıları ile karşılaştırılmış iyi sonuçlar elde edilmiştir. Ayrıca sıralama (sorting), arama (searching) gibi her zaman güncel bazı alanlara etkin bir şekilde uygulanabilirliği gösterilmiştir.

Özet (Çeviri)

Linked lists are used in skip list data structure. Skip list data structure consists of layered structure and all nodes are in the lowest layer. These nodes are reduced by half towards upper layers and are formed a pyramid-shaped structure. Thus, it is aimed to enable searching, insertion and deletion. Besides, this data structure can be improved further. The purpose of our study is to identify problems in data structure by analyzing skip list data structure, to make improvements in skip list data structure by resolving the identified problems and to implement and then to apply these improvements to the new data structure that we proposed. New data structure that we proposed by considering improvements in skip list is formed by utilizing skip ring, circular linked list and skip list data structure. New data structure that we proposed composes of circular linked list in cone-shaped cohesive layers. Thus, time complexity of search, insertion and deletion progress is O(lgN) in N-Element skip list data structure. Proposed new data structure was compared practically with binary search trees, red-black trees and skip list data structures and the results was evaluated. Moreover, a new sorting based on skip ring and search algorithm were proposed. These proposed algorithms were compared practically with current sorting and search algorithms. Consequently, skip ring data structure which was improved by utilizing the properties of skip list and circular linked lists was compared with some tree-based data structures and good results were obtained. And also, effective applicability in some areas such as sorting and searching was demonstrated.

Benzer Tezler

  1. Alevi - Bektaşi semahları, bölümleri ve melodik yapılar!

    Flame - Bektaş world, sections and melodic structures!

    DAİMİ CENGİZ

    Yüksek Lisans

    Türkçe

    Türkçe

    1988

    Güzel Sanatlarİstanbul Teknik Üniversitesi

    Musiki Ana Sanat Dalı

    DOÇ. DR. FİKRET DEĞERLİ

  2. Giresun ve Ordu yöresi kol havaları

    Giresun and Ordu district kol havaları

    FATMA ÇİÇEK

    Yüksek Lisans

    Türkçe

    Türkçe

    2003

    MüzikEge Üniversitesi

    Türk Halk Müziği Ana Sanat Dalı

    DR. ATINÇ EMNALAR

  3. Backscattering jamming signal to maintain communications using reinforcement learning

    Takviyeli öğrenmeyi kullanarak iletişimi sürdürmek için geri dağılım boğma sinyali

    HIBA HATIF SABEA MALALLAH

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

    Bilim ve TeknolojiAltınbaş Üniversitesi

    Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı

    Assist. Prof. Dr. SEFER KURNAZ

  4. Optimization methodology for application mapping in wireless network-on-chip

    Kablosuz yonga-üstü-ağlar için uygulama eşleme optimizasyon metodolojisi

    ALPEREN ÇAKIN

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. SÜLEYMAN TOSUN

  5. Elazığ iğne oyaları

    Başlık çevirisi yok

    GÖNÜL GÖKALP

    Yüksek Lisans

    Türkçe

    Türkçe

    1991

    El SanatlarıGazi Üniversitesi

    DOÇ.DR. TACİSER ONUK