what is skip list presentation

A skip list is a probabilistic data structure. The skip list is used to store a sorted list of elements or data with a linked list. It allows the process of the elements or data to view efficiently. In one single step, it skips several elements of the entire list, which is why it is known as a skip list.

The skip list is an extended version of the linked list. It allows the user to search, remove, and insert the element very quickly. It consists of a base list that includes a set of elements which maintains the link hierarchy of the subsequent elements.

It is built in two layers: The lowest layer and Top layer.

The lowest layer of the skip list is a common sorted linked list, and the top layers of the skip list are like an "express line" where the elements are skipped.

Working of the Skip list

Let's take an example to understand the working of the skip list. In this example, we have 14 nodes, such that these nodes are divided into two layers, as shown in the diagram.

The lower layer is a common line that links all nodes, and the top layer is an express line that links only the main nodes, as you can see in the diagram.

Suppose you want to find 47 in this example. You will start the search from the first node of the express line and continue running on the express line until you find a node that is equal a 47 or more than 47.

You can see in the example that 47 does not exist in the express line, so you search for a node of less than 47, which is 40. Now, you go to the normal line with the help of 40, and search the 47, as shown in the diagram.

Note: Once you find a node like this on the "express line", you go from this node to a "normal lane" using a pointer, and when you search for the node in the normal line.

Skip list basic operations.

There are the following types of operations in the skip list.

• Insertion operation: It is used to add a new node to a particular location in a specific situation.
• Deletion operation: It is used to delete a node in a specific situation.
• Search Operation: The search operation is used to search a particular node in a skip list.

Algorithm of the insertion operation

Algorithm of deletion operation

Algorithm of searching operation

Example 1: Create a skip list, we want to insert these following keys in the empty skip list.

• 6 with level 1.
• 29 with level 1.
• 22 with level 4.
• 9 with level 3.
• 17 with level 1.
• 4 with level 2.

Step 1: Insert 6 with level 1

Step 2: Insert 29 with level 1

Step 3: Insert 22 with level 4

Step 4: Insert 9 with level 3

Step 5: Insert 17 with level 1

Step 6: Insert 4 with level 2

Example 2: Consider this example where we want to search for key 17.

Advantages of the Skip list

• If you want to insert a new node in the skip list, then it will insert the node very fast because there are no rotations in the skip list.
• The skip list is simple to implement as compared to the hash table and the binary search tree.
• It is very simple to find a node in the list because it stores the nodes in sorted form.
• The skip list algorithm can be modified very easily in a more specific structure, such as indexable skip lists, trees, or priority queues.
• The skip list is a robust and reliable list.

Disadvantages of the Skip list

• It requires more memory than the balanced tree.
• Reverse searching is not allowed.
• The skip list searches the node much slower than the linked list.

Applications of the Skip list

• It is used in distributed applications, and it represents the pointers and system in the distributed applications.
• It is used to implement a dynamic elastic concurrent queue with low lock contention.
• It is also used with the QMap template class.
• The indexing of the skip list is used in running median problems.
• The skip list is used for the delta-encoding posting in the Lucene search.

• Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Interview Questions

Company Questions

Trending Technologies

Artificial Intelligence

Cloud Computing

Data Science

Machine Learning

B.Tech / MCA

Data Structures

Operating System

Computer Network

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Control System

Data Mining

Data Warehouse

SkipList Implementation in Java

Last updated: April 14, 2024

It's finally here:

>> The Road to Membership and Baeldung Pro .

Going into ads, no-ads reading , and bit about how Baeldung works if you're curious :)

Azure Container Apps is a fully managed serverless container service that enables you to build and deploy modern, cloud-native Java applications and microservices at scale. It offers a simplified developer experience while providing the flexibility and portability of containers.

Of course, Azure Container Apps has really solid support for our ecosystem, from a number of build options, managed Java components, native metrics, dynamic logger, and quite a bit more.

To learn more about Java features on Azure Container Apps, visit the documentation page .

You can also ask questions and leave feedback on the Azure Container Apps GitHub page .

Java applications have a notoriously slow startup and a long warmup time. The CRaC (Coordinated Restore at Checkpoint) project from OpenJDK can help improve these issues by creating a checkpoint with an application's peak performance and restoring an instance of the JVM to that point.

To take full advantage of this feature, BellSoft provides containers that are highly optimized for Java applications. These package Alpaquita Linux (a full-featured OS optimized for Java and cloud environment) and Liberica JDK (an open-source Java runtime based on OpenJDK).

These ready-to-use images allow us to easily integrate CRaC in a Spring Boot application:

Improve Java application performance with CRaC support

Modern software architecture is often broken. Slow delivery leads to missed opportunities, innovation is stalled due to architectural complexities, and engineering resources are exceedingly expensive.

Orkes is the leading workflow orchestration platform built to enable teams to transform the way they develop, connect, and deploy applications, microservices, AI agents, and more.

With Orkes Conductor managed through Orkes Cloud, developers can focus on building mission critical applications without worrying about infrastructure maintenance to meet goals and, simply put, taking new products live faster and reducing total cost of ownership.

Try a 14-Day Free Trial of Orkes Conductor today.

To learn more about Java features on Azure Container Apps, you can get started over on the documentation page .

And, you can also ask questions and leave feedback on the Azure Container Apps GitHub page .

Whether you're just starting out or have years of experience, Spring Boot is obviously a great choice for building a web application.

Jmix builds on this highly powerful and mature Boot stack, allowing devs to build and deliver full-stack web applications without having to code the frontend. Quite flexibly as well, from simple web GUI CRUD applications to complex enterprise solutions.

Concretely, The Jmix Platform includes a framework built on top of Spring Boot, JPA, and Vaadin , and comes with Jmix Studio, an IntelliJ IDEA plugin equipped with a suite of developer productivity tools.

The platform comes with interconnected out-of-the-box add-ons for report generation, BPM, maps, instant web app generation from a DB, and quite a bit more:

>> Become an efficient full-stack developer with Jmix

DbSchema is a super-flexible database designer, which can take you from designing the DB with your team all the way to safely deploying the schema .

The way it does all of that is by using a design model , a database-independent image of the schema, which can be shared in a team using GIT and compared or deployed on to any database.

And, of course, it can be heavily visual, allowing you to interact with the database using diagrams, visually compose queries, explore the data, generate random data, import data or build HTML5 database reports.

>> Take a look at DBSchema

Get non-trivial analysis (and trivial, too!) suggested right inside your IDE or Git platform so you can code smart, create more value, and stay confident when you push.

Get CodiumAI for free and become part of a community of over 280,000 developers who are already experiencing improved and quicker coding.

Write code that works the way you meant it to:

>> CodiumAI. Meaningful Code Tests for Busy Devs

The AI Assistant to boost Boost your productivity writing unit tests - Machinet AI .

AI is all the rage these days, but for very good reason. The highly practical coding companion, you'll get the power of AI-assisted coding and automated unit test generation . Machinet's Unit Test AI Agent utilizes your own project context to create meaningful unit tests that intelligently aligns with the behavior of the code. And, the AI Chat crafts code and fixes errors with ease, like a helpful sidekick.

Simplify Your Coding Journey with Machinet AI :

>> Install Machinet AI in your IntelliJ

Since its introduction in Java 8, the Stream API has become a staple of Java development. The basic operations like iterating, filtering, mapping sequences of elements are deceptively simple to use.

But these can also be overused and fall into some common pitfalls.

To get a better understanding on how Streams work and how to combine them with other language features, check out our guide to Java Streams:

Download the E-book

Do JSON right with Jackson

Get the most out of the Apache HTTP Client

Get Started with Apache Maven:

Working on getting your persistence layer right with Spring?

Explore the eBook

Building a REST API with Spring?

Get started with Spring and Spring Boot, through the Learn Spring course:

Explore Spring Boot 3 and Spring 6 in-depth through building a full REST API with the framework:

>> The New “REST With Spring Boot”

Get started with Spring and Spring Boot, through the reference Learn Spring course:

>> LEARN SPRING

Yes, Spring Security can be complex, from the more advanced functionality within the Core to the deep OAuth support in the framework.

I built the security material as two full courses - Core and OAuth , to get practical with these more complex scenarios. We explore when and how to use each feature and code through it on the backing project .

You can explore the course here:

>> Learn Spring Security

1. Overview

In this article, we’ll explore the fundamentals of the SkipList data structure and walk through a Java implementation. SkipLists are versatile and can be applied to various domains and problems due to their efficient search, insert, and delete operations and relatively straightforward implementation compared to more complex data structures like balanced trees.

2. What Is a SkipList ?

A SkipList data structure allows fast search, insert, and delete operations. It achieves this by maintaining several layers of sorted linked lists. The bottom layer contains all the elements in the list, while each successive layer acts as an “express lane”, containing shortcuts for a subset of the elements below it .

These express lanes allow SkipLists to achieve faster search times by jumping over several elements in a single step.

3. Basic Concepts

• Levels: A SkipList consists of several levels. The bottom level (level 0) is a regular linked list of all elements. Each higher level acts as an “express lane”, containing fewer elements and skipping over multiple elements in the lower levels.
• Probability and height: The number of levels at which an element appears is determined probabilistically.
• Head pointers: Each level has a head pointer that points to the first element of that level, facilitating fast access to each level’s elements.

4. Java Implementation

For our Java implementation, we’ll focus on a simplified version of a SkipList that supports basic operations: search, insert, and delete. We’ll use a fixed maximum number of levels for simplicity, although we can adjust this dynamically based on the size of the list.

4.1. Defining the Node Class

First, let’s define a Node class representing an element in the SkipList . Each node will contain a value and an array of pointers to the next node at each level.

4.2. The SkipList Class

Then, we need to create the SkipList class to manage the nodes and levels:

4.3. Insert Operation

Now, let’s add an insert method to our SkipList class. This method will insert a new element into the SkipList , ensuring the structure remains efficient:

4.4. Search Operation

The search method traverses the SkipList from the top level down to level 0, moving forward at each level as long as the next node’s value is less than the search value:

4.5. Delete Operation

Finally, the delete operation removes a value from the SkipList if it exists. Similar to insert, it also needs to update the forward references of the preceding nodes at all levels where the deleted node was present:

5. Time Complexity

The beauty of SkipLists lies in their efficiency:

• Search, insert, and delete operations have an average time complexity of O(log n) , where n is the number of elements in the list.
• The space complexity is O(n) , considering additional pointers at multiple levels for each element.

6. Advantages

SkipLists come with their own set of advantages and disadvantages, of course. Let’s explore the advantages first:

• The simplicity of implementation: Compared to balanced trees like AVL or Red-Black trees, SkipLists are easier to implement and still provide similar average-case performance for search, insertion, and deletion operations.
• Efficient operations: SkipLists offer efficient average-case time complexities of O(log n) for search, insert, and delete operations.
• Probabilistic balancing: Instead of strict rebalancing rules (as in AVL trees or Red-Black trees), SkipLists use a probabilistic method to maintain balance. This randomization often leads to more evenly balanced structures without the need for complex rebalancing code.
• Concurrency: SkipLists can be more amenable to concurrent access/modification. Lock-free and fine-grained locking strategies are easier to implement in SkipLists , making them suitable for concurrent applications.

7. Disadvantages

Now, let’s look at some of their disadvantages:

• Space overhead: Each node stores multiple forward pointers to other nodes, leading to higher space consumption than a singly-linked list or a binary tree.
• Randomization: While beneficial for balance and simplicity, the probabilistic approach introduces randomness into the structure’s performance. The performance can vary slightly between runs, unlike with deterministic data structures.

8. Conclusion

SkipLists offer a compelling alternative to more traditional balanced tree structures, with their probabilistic approach providing both efficiency and simplicity. Our Java implementation offers a solid foundation for understanding how SkipLists work.

The example code from this article can be found over on GitHub .

Baeldung Pro comes with both absolutely No-Ads as well as finally with Dark Mode , for a clean learning experience:

>> Explore a clean Baeldung

Once the early-adopter seats are all used, the price will go up and stay at $33/year.

Looking for the ideal Linux distro for running modern Spring apps in the cloud?

Meet Alpaquita Linux : lightweight, secure, and powerful enough to handle heavy workloads.

This distro is specifically designed for running Java apps . It builds upon Alpine and features significant enhancements to excel in high-density container environments while meeting enterprise-grade security standards.

Specifically, the container image size is ~30% smaller than standard options, and it consumes up to 30% less RAM:

>> Try Alpaquita Containers now.

Explore the secure, reliable, and high-performance Test Execution Cloud built for scale. Right in your IDE:

Basically, write code that works the way you meant it to.

AI is all the rage these days, but for very good reason. The highly practical coding companion, you'll get the power of AI-assisted coding and automated unit test generation . Machinet's Unit Test AI Agent utilizes your own project context to create meaningful unit tests that intelligently aligns with the behavior of the code.

Get started with Spring Boot and with core Spring, through the Learn Spring course:

>> CHECK OUT THE COURSE

Oct 02, 2014

170 likes | 358 Views

Skip Lists. Outline and Reading. What is a skip list ( §9.4 ) Operations ( §9.4.1 ) Search Insertion Deletion Implementation Analysis ( §9.4.2 ) Space usage Search and update times.

Share Presentation

• running time
• coin tosses
• skip list 9
• coin tosses give heads

Presentation Transcript

Outline and Reading • What is a skip list (§9.4) • Operations (§9.4.1) • Search • Insertion • Deletion • Implementation • Analysis (§9.4.2) • Space usage • Search and update times

A skip list for a set S of distinct (key, element) items is a series of lists S0, S1 , … , Sh such that Each list Si contains the special keys + and - List S0 contains the keys of S in non-decreasing order Each list is a subsequence of the previous one, i.e.,S0 S1  … Sh List Sh contains only the two special keys Skip lists are one way to implement the dictionary ADT Java applet - + - 12 23 26 31 34 44 56 64 78 + What is a Skip List S3 S2 - 31 + S1 - 23 31 34 64 + S0

We can implement a skip list with quad-nodes A quad-node stores: item link to the node before link to the node after link to the node below Also, we define special keys PLUS_INF and MINUS_INF, and we modify the key comparator to handle them Implementation quad-node x

We search for a key x in a a skip list as follows: We start at the first position of the top list At the current position p, we compare x with y  key(after(p)) x = y: we return element(after(p)) x > y: we “scan forward” x < y: we “drop down” If we try to drop down past the bottom list, we return NO_SUCH_KEY Example: search for 78 Search S3 - + S2 - 31 + S1 - 23 31 34 64 + S0 - 12 23 26 31 34 44 56 64 78 +

We search for a key x in a a skip list as follows: We start at the first position of the top list At the current position p, we compare x with y  key(after(p)) x = y: we return element(after(p)) x > y: we “scan forward” x < y: we “drop down” If we try to drop down past the bottom list, we return NO_SUCH_KEY Ex 1: search for 64: list the (Si, node) pairs visited and the return value Ex 2: search for 27: list the (Si, node) pairs visited and the return value Exercise: Search S3 - + S2 - 31 + S1 - 23 31 34 64 + S0 - 12 23 26 31 34 44 56 64 78 +

- + - 15 + - 15 23 + - 10 23 36 + 15 Insertion • To insert an item (x, o) into a skip list, we use a randomized algorithm: • We repeatedly toss a coin until we get tails, and we denote with i the number of times the coin came up heads • If i  h, we add to the skip list new lists Sh+1, … , Si +1, each containing only the two special keys • We search for x in the skip list and find the positions p0, p1 , …, pi of the items with largest key less than x in each list S0, S1, … , Si • For j 0, …, i, we insert item (x, o) into list Sj after position pj • Example: insert key 15, with i= 2 S3 p2 S2 S2 - + p1 S1 S1 - + 23 p0 S0 S0 - 10 23 36 +

Deletion • To remove an item with key xfrom a skip list, we proceed as follows: • We search for x in the skip list and find the positions p0, p1 , …, pi of the items with key x, where position pj is in list Sj • We remove positions p0, p1 , …, pi from the lists S0, S1, … , Si • We remove all but one list containing only the two special keys • Example: remove key 34 S3 - + p2 S2 S2 - + - 34 + p1 S1 S1 - + - 23 34 + 23 p0 S0 S0 - 12 23 45 + - 12 23 45 + 34

A randomized algorithm controls its execution through random selection (e.g., coin tosses) It contains statements like: b randomBit() if b= 0 do A … else { b= 1} do B … Its running time depends on the outcomes of the coin tosses Through probabilistic analysis we can derive the expected running time of a randomized algorithm We make the following assumptions in the analysis: the coins are unbiased the coin tosses are independent The worst-case running time of a randomized algorithm is often large but has very low probability (e.g., it occurs when all the coin tosses give “heads”) We use a randomized algorithm to insert items into a skip list to insert in expected O(log n)-time When randomization is used in data structures they are referred to as probabilistic data structures Randomized Algorithms

The space used by a skip list depends on the random bits used by each invocation of the insertion algorithm We use the following two basic probabilistic facts: Fact 1: The probability of getting i consecutive heads when flipping a coin is 1/2i Fact 2: If each of n items is present in a set with probability p, the expected size of the set is np Consider a skip list with n items By Fact 1, we insert an item in list Si with probability 1/2i By Fact 2, the expected size of list Si is n/2i The expected number of nodes used by the skip list is Space Usage Thus, the expected space usage of a skip list with n items is O(n)

The running time of the search an insertion algorithms is affected by the height h of the skip list We show that with high probability, a skip list with n items has height O(log n) We use the following additional probabilistic fact: Fact 3: If each of n events has probability p, the probability that at least one event occurs is at most np Consider a skip list with n items By Fact 1, we insert an item in list Si with probability 1/2i By Fact 3, the probability that list Si has at least one item is at most n/2i By picking i= 3log n, we have that the probability that S3log n has at least one item isat mostn/23log n= n/n3= 1/n2 Thus a skip list with n items has height at most 3log n with probability at least 1 - 1/n2 Height

The search time in a skip list is proportional to the number of drop-down steps, plus the number of scan-forward steps The drop-down steps are bounded by the height of the skip list and thus are O(log n) with high probability To analyze the scan-forward steps, we use yet another probabilistic fact: Fact 4:The expected number of coin tosses required in order to get tails is 2 When we scan forward in a list, the destination key does not belong to a higher list A scan-forward step is associated with a former coin toss that gave tails By Fact 4, in each list the expected number of scan-forward steps is 2 Thus, the expected number of scan-forward steps is O(log n) We conclude that a search in a skip list takes O(log n) expected time The analysis of insertion and deletion gives similar results Search and Update Times

Exercise • You are working for ObscureDictionaries.com a new online start-up which specializes in sci-fi languages. The CEO wants your team to describe a data structure which will efficiently allow for searching, inserting, and deleting new entries. You believe a skip list is a good idea, but need to convince the CEO. Perform the following: • Illustrate insertion of “X-wing” into this skip list. Randomly generated (1, 1, 1, 0). • Illustrate deletion of an incorrect entry “Enterprise” S2 - + S1 Enterprise + - S0 BobaFett Yoda + - Enterprise

A skip list is a data structure for dictionaries that uses a randomized insertion algorithm In a skip list with n items The expected space used is O(n) The expected search, insertion and deletion time is O(log n) Using a more complex probabilistic analysis, one can show that these performance bounds also hold with high probability Skip lists are fast and simple to implement in practice Summary

• More by User

Skip-it. Marketing Communications Professor Wertalik. Table of Contents. Executive Summary pg. 3 Industry Background pg. 4 Company Snapshot pg. 5 Brand Review pg. 6 Competitive Review pg. 7 Buyer Analysis pg. 8 SWOT Analysis pg. 9 Marketing Goals pg. 10

490 views • 30 slides

SKIP LIST &amp; SKIP GRAPH

SKIP LIST &amp; SKIP GRAPH. Many slides adapted from the original slides by James Aspnes Gauri Shah. Definition of Skip List. A skip list for a set L of distinct (key, element) items is a series of linked lists L 0 , L 1 , … , L h such that

779 views • 40 slides

SKIP. KMR Enterprises Software License Agreement for Conditions of Learning and Instructional Design

353 views • 16 slides

SKIP. ǽ Я α™. Registration Number. 1. 4. D. K. A. 0. 8. F. 2. 0. 1. 9. Presented by. Password. Aliyul Adzim bin Abdul Ghapar. ●. ●. ●. ●. ●. ●. ●. ●. Mohd Saifullizam bin Norhman. Sign In. Rudihartono bin Hasnan. Forgot the password? Click here or sign up.

262 views • 13 slides

Skip Lists – Why?

Skip Lists – Why?. BSTs Worse case insertion, search O(n) Best case insertion, search O(log n) Where your run fits in O(n) – O(log n) depends on the order of the data Hard to keep balanced 2-3 trees Guaranteed to be balanced Complicated to implement. Skip List.

202 views • 7 slides

Skip Lists. by Arlen Fletcher and Tim Heuett. What are skip lists?. Developed around 1989 by William Pugh as an alternative to balanced trees A probabilistic data structure based on parallel linked lists (we’ll get to this…). Skip Lists – “Express Lanes”!. Express Lanes. Highway. Roads.

770 views • 12 slides

CMSC420: Skip Lists

CMSC420: Skip Lists. Kinga Dobolyi Based off notes by Dave Mount. What is the purpose of this class?. Data storage Speed Trees Binary search tree Could degenerate into a linked list AVL tree Better performance, difficult to implement Splay tree Good overall performance -- amortized.

250 views • 12 slides

Skip Lists. Michael Oudshoorn. Skip Lists. Binary Search Trees: O(log n) If, and only if, the tree is “balanced” Insertion of partially sorted data is optimally bad for binary search trees. Skip Lists make use of some randomization to maintain O(log n) search and update times

320 views • 12 slides

Skip Lists. 12. 23. 26. 31. 34. 44. 56. 64. 78. Skip List. Question: Can we create a structure that adds the best properties of Array and Linked list Data Structure? Query: O(log n) in sorted Arrays Insert/Removal: O(1) in Linked List.

344 views • 16 slides

Skip Lists. Nov. 2, 2006. Midterm #2. Nov. 9 Thu 7pm. Pseudorandom number generator. Middle-square method (John von Neumann, 1946) Take any number, square it, remove the middle digits of the resulting number as your &quot;random number&quot;, then use that number as the seed for the next iteration

158 views • 9 slides

- . + . - . 15. + . - . 15. 23. + . - . 10. 23. 36. + . 15. Skip Lists. S 3. S 2. S 1. S 0. Outline and Reading. What is a skip list ( §8.4 ) Operations Search ( §8.4.1 ) Insertion ( §8.4.2 ) Deletion ( §8.4.2 ) Implementation Analysis ( §8.4.3 ) Space usage

311 views • 16 slides

- . + . - . 15. + . - . 15. 23. + . - . 10. 23. 36. + . 15. Skip Lists. S 3. S 2. S 1. S 0. A skip list for a set S of distinct (key, element) items is a series of lists S 0 , S 1 , … , S h such that Each list S i contains the special keys +  and - 

189 views • 11 slides

Skip Lists. Linked Lists. Fast modifications given a pointer Slow traversals to random point. Linked Lists. Fast modifications given a pointer Slow traversals to random point What if we add an express lane?. Linked Lists.

488 views • 40 slides

SKIP LIST &amp; SKIP GRAPH. James Aspnes Gauri Shah Many slides have been taken from the original presentation by the authors. Definition of Skip List. A skip list for a set L of distinct (key, element) items is a series of linked lists L 0 , L 1 , … , L h such that

605 views • 40 slides

VinsBins are your Hastings Skip Hire experts. VinsBins provide bin hire and waste management services to Hastings and across the Mornington Peninsula. We have close to 500 skip bins for hire, with many size options available. These include the very popular 3 cubic meter bin that's used for household clean-ups or as a site bin. More- https://www.vinsbins.com/

66 views • 5 slides

Skip Bin Hire|Hire Skip Bins|Skip Bins|Skip Bins Perth|Perth Skip Bin Hire|Skip Hire Perth

Contact Matera Environmental today for Skip Bins Hire in Perth .We provide Online,Cost-Effective and reliable Skip Bin Hire services in Perth,South West of WA.

80 views • 6 slides

CSC401 – Analysis of Algorithms Chapter 3 Search Trees and Skip Lists

CSC401 – Analysis of Algorithms Chapter 3 Search Trees and Skip Lists. Objectives: Review binary search trees and present operations on binary search trees Analyze the performance of binary search tree operations

628 views • 61 slides

144 views • 12 slides

• My presentations

Auth with social network:

Download presentation

We think you have liked this presentation. If you wish to download it, please recommend it to your friends in any social system. Share buttons are a little bit lower. Thank you!

Presentation is loading. Please wait.

Skip Lists S3 + - S2 + - S1 + - S0 + -

Published by Sukarno Darmadi Modified over 5 years ago

Similar presentations

Presentation on theme: "Skip Lists S3 + - S2 + - S1 + - S0 + -"— Presentation transcript:

© 2004 Goodrich, Tamassia Skip Lists1 S0S0 S1S1 S2S2 S3S

Skip Lists. Outline and Reading What is a skip list (§9.4) – Operations (§9.4.1) – Search – Insertion – Deletion Implementation Analysis (§9.4.2) – Space.

The Dictionary ADT: Skip List Implementation

SKIP LISTS Amihood Amir Incorporationg the slides of Goodrich and Tamassia (2004)

Skip Lists Present By PAKDEE PATTANAJEDSADA SITTHICHOK SNANSIENG SIWAKORN THAMMAYTHA PATOMPOL TAESUJI

CSC 172 DATA STRUCTURES. SKIP LISTS Read Weiss

© 2004 Goodrich, Tamassia Hash Tables1  

Expected Running Times and Randomized Algorithms Instructor Neelima Gupta

© 2004 Goodrich, Tamassia Quick-Sort     29  9.

© 2004 Goodrich, Tamassia QuickSort1 Quick-Sort     29  9.

Quick-Sort     29  9.

Data Structures Lecture 13 Fang Yu Department of Management Information Systems National Chengchi University Fall 2010.

© 2004 Goodrich, Tamassia Skip Lists1  S0S0 S1S1 S2S2 S3S3    2315.

CSC401 – Analysis of Algorithms Lecture Notes 7 Multi-way Search Trees and Skip Lists Objectives: Introduce multi-way search trees especially (2,4) trees,

Skip Lists Michael Oudshoorn. CS351 Software Engineering (AY05)2 Skip Lists Binary Search Trees: O(log n) –If, and only if, the tree is “balanced” Insertion.

© 2004 Goodrich, Tamassia Selection1. © 2004 Goodrich, Tamassia Selection2 The Selection Problem Given an integer k and n elements x 1, x 2, …, x n, taken.

© 2004 Goodrich, Tamassia (2,4) Trees

Skip Lists1 Skip Lists William Pugh: ” Skip Lists: A Probabilistic Alternative to Balanced Trees ”, 1990  S0S0 S1S1 S2S2 S3S3 

Introduction To Algorithms CS 445 Discussion Session 2 Instructor: Dr Alon Efrat TA : Pooja Vaswani 02/14/2005.

Skip Lists Mrutyunjay. Introduction ▪ Linked Lists Benefits & Drawbacks: – Benefits: – Easy Insert and Deletes, implementations. – Drawbacks: – Hard to.

About project

© 2024 SlidePlayer.com Inc. All rights reserved.

• Preferences

Skip Lists - PowerPoint PPT Presentation

Something went wrong! Please try again and reload the page.

What is a Skip List. A skip list for a set S of distinct (key, element) items is a series of lists S0, ... We start at the first position of the top list ... – PowerPoint PPT presentation

• Can we create a structure that adds the best properties of Array and Linked list Data Structure?
• Query O(log n) in sorted Arrays
• Insert/Removal O(1) in Linked List
• A skip list for a set S of distinct (key, element) items is a series of lists S0, S1 , , Sh such that
• Each list Si contains the special keys ? and -?
• List S0 contains the keys of S in nondecreasing order
• Each list is a subsequence of the previous one, i.e., S0 ? S1 ? ? Sh
• List Sh contains only the two special keys
• We show how to use a skip list to implement the dictionary ADT
• We search for a key x in a skip list as follows
• We start at the first position of the top list
• At the current position p, we compare x with y ? key(after(p))
• x y we return element(after(p))
• x gt y we scan forward
• x lt y we drop down
• If we try to drop down past the bottom list, we return NO_SUCH_KEY
• Example search for 78
• To insert an item (x, o) into a skip list, we use a randomized algorithm
• We repeatedly toss a coin until we get tails, and we denote with i the number of times the coin came up heads
• If i ? h, we add to the skip list new lists Sh1, , Si 1, each containing only the two special keys
• We search for x in the skip list and find the positions p0, p1 , , pi of the items with largest key less than x in each list S0, S1, , Si
• For j ? 0, , i, we insert item (x, o) into list Sj after position pj
• Example insert key 15, with i 2
• To remove an item with key x from a skip list, we proceed as follows
• We search for x in the skip list and find the positions p0, p1 , , pi of the items with key x, where position pj is in list Sj
• We remove positions p0, p1 , , pi from the lists S0, S1, , Si
• We remove all but one list containing only the two special keys
• Example remove key 34
• We can implement a skip list with quad-nodes
• A quad-node stores
• link to the node before
• link to the node after
• link to the node below
• Also, we define special keys PLUS_INF and MINUS_INF, and we modify the key comparator to handle them
• Consider a skip list with n items
• By Fact 1, we insert an item in list Si with probability 1/2i
• By Fact 2, the expected size of list Si is n/2i
• The expected number of nodes used by the skip list is
• The space used by a skip list depends on the random bits used by each invocation of the insertion algorithm
• We use the following two basic probabilistic facts
• Fact 1 The probability of getting i consecutive heads when flipping a coin is 1/2i
• Fact 2 If each of n items is present in a set with probability p, the expected size of the set is np
• Thus, the expected space usage of a skip list with n items is O(n)
• The running time of the search an insertion algorithms is affected by the height h of the skip list
• We show that with high probability, a skip list with n items has height O(log n)
• We use the following additional probabilistic fact
• Fact 3 If each of n events has probability p, the probability that at least one event occurs is at most np
• By Fact 3, the probability that list Si has at least one item is at most n/2i
• By picking i 3log n, we have the probability that S3log n has at least one item is at most n/23log n n/n3 1/n2
• Thus a skip list with n items has height at most 3log n with probability at least 1 - 1/n2
• The search time in a skip list is proportional to
• the number of drop-down steps, plus
• the number of scan-forward steps
• The drop-down steps are bounded by the height of the skip list and thus are O(log n) with high probability
• To analyze the scan-forward steps, we use yet another probabilistic fact
• Fact 4 The expected number of coin tosses required in order to get tails is 2
• When we scan forward in a list, the destination key does not belong to a higher list
• A scan-forward step is associated with a former coin toss that gave tails
• By Fact 4, in each list the expected number of scan-forward steps is 2
• Thus, the expected number of scan-forward steps is O(log n)
• We conclude that a search in a skip list takes O(log n) expected time
• The analysis of insertion and deletion gives similar results
• A skip list is a data structure for dictionaries that uses a randomized insertion algorithm
• In a skip list with n items
• The expected space used is O(n)
• The expected search, insertion and deletion time is O(log n)
• Using a more complex probabilistic analysis, one can show that these performance bounds also hold with high probability
• Skip lists are fast and simple to implement in practice
• Many sorting algorithms are comparison based.
• They sort by making comparisons between pairs of objects
• Examples bubble-sort, selection-sort, insertion-sort, heap-sort, merge-sort, quick-sort, ...
• Let us therefore derive a lower bound on the running time of any algorithm that uses comparisons to sort n elements, x1, x2, , xn.
• Let us just count comparisons then.
• Each possible run of the algorithm corresponds to a root-to-leaf path in a decision tree
• Example xa, xb, xc
• The height of this decision tree is a lower bound on the running time
• Every possible input permutation must lead to a separate leaf output.
• If not, some input 45 would have same output ordering as 54, which would be wrong.
• Since there are n!12n leaves, the height is at least log (n!)
• Any comparison-based sorting algorithms takes at least log (n!) time
• Therefore, any such algorithm takes time at least
• That is, any comparison-based sorting algorithm must run in O(n log n) time.

PowerShow.com is a leading presentation sharing website. It has millions of presentations already uploaded and available with 1,000s more being uploaded by its users every day. Whatever your area of interest, here you’ll be able to find and view presentations you’ll love and possibly download. And, best of all, it is completely free and easy to use.

You might even have a presentation you’d like to share with others. If so, just upload it to PowerShow.com. We’ll convert it to an HTML5 slideshow that includes all the media types you’ve already added: audio, video, music, pictures, animations and transition effects. Then you can share it with your target audience as well as PowerShow.com’s millions of monthly visitors. And, again, it’s all free.

About the Developers

PowerShow.com is brought to you by  CrystalGraphics , the award-winning developer and market-leading publisher of rich-media enhancement products for presentations. Our product offerings include millions of PowerPoint templates, diagrams, animated 3D characters and more.

Two students, two teachers killed in shooting at Georgia high school; 14-year-old charged as an adult

Two students and two teachers were killed and nine others wounded Wednesday in a school shooting an hour outside of Atlanta, authorities said.

One suspect, a 14-year-old student, was alive and taken into custody following the gunfire at Apalachee High School, Georgia Bureau of Investigation director Chris Hosey said at a news conference late Wednesday afternoon.

The victims of the shooting have been identified as Mason Schermerhorn, 14; Christian Angulo, 14; Richard Aspinwall, 39; Christina Irimie, 53.

Both Aspinwall and Irimie taught math, according to the school’s website. Aspinwall was also a defensive coordinator for the football team.

The suspect, identified as Colt Gray, surrendered to law enforcement immediately after being confronted, Hosey said. He was cooperating with authorities and will be charged with murder and handled as an adult, according to Hosey and Barrow County Sheriff Jud Smith.

“He gave up, got on the ground and the deputy took him into custody,” Smith said.

Hosey said the suspect used an "AR platform-style weapon." He was in custody in the Barrow County Detention Center and will be booked Wednesday night, then transferred to Regional Youth Detention Center, Hosey said.

Smith said authorities do not yet know how the shooter obtained the firearm and how he brought it into the school.

Follow along for live coverage

The nine people injured include eight students and one teacher, the bureau said. All are expected to recover, Hosey said.

Smith said all nine who were taken to hospitals were injured by gunfire in some capacity. He lamented the “pure evil” and “hateful event.”

A motive was unclear. Smith said he was not aware whether the victims were targeted or whether there was a connection between the shooter and the victims.

"I don't know why it happened. I may not ever know. We may not ever know," Smith said.

The evidence does not support the involvement of any additional shooters, Hosey said. He said investigators were working to determine whether there were any associates involved in the shooting.

Investigators are also working to determine whether there are active threats against any other schools in Georgia, Hosey said.

Prior threat investigation

The sheriff's office in Jackson County, Georgia, had prior contact with the suspect in May 2023, when he was 13, in relation to a possible school shooting threat, the FBI office in Atlanta and the sheriff's office said in a joint statement Wednesday.

Jackson County is about 13 miles northeast of Barrow County.

That month, the FBI received “several anonymous tips about online threats to commit a school shooting at an unidentified location and time” that included pictures of guns, the joint statement said.

Within 24 hours, the FBI determined the threats were coming from Georgia, and the sheriff's office located and interviewed the teenager and his father, the statement said.

The statement said the boy denied making the online threats and at the time, there was no probable cause for an arrest, but the county "alerted local schools for continued monitoring of the subject."

The father in the interview with law enforcement said he had hunting guns in their house but that his son didn’t have “unsupervised access” to them, the statement said.

Hosey said Wednesday night investigators are working with the FBI to determine whether that incident had any connection to Wednesday's shooting.

Active shooter call

The first call reporting an “active shooter” came in around 10:30 a.m., Smith said. Hosey said law enforcement officers and two school resource officers responded to the scene within minutes of being alerted to the shooting.

The call came in from a teacher who pressed buttons on an ID that notifies law enforcement of an "active situation at the school," Smith said Wednesday night. He said that all teachers have one of these IDs.

All campuses of Barrow County Schools, based in Winder, Georgia, went into a "soft lockdown" with most of the activity centered around Apalachee H.S. where police cars, fire trucks and ambulances had all converged.

Students could be seen being directed to the school's football stadium.

Eight people, including three with gunshot wounds, were taken to North Georgia Medical Center facilities in Barrow, Gainesville and Braselton, a hospital spokesperson said. Five people had panic attack symptoms.

Grady Memorial Hospital in Atlanta confirmed that it was treating one gunshot victim.

The daughter of one of the injured victims, golf coach David Phenix, said her father’s hip was shattered after he was struck in the foot and hip. In a Facebook post, she said he was in stable condition after surgery.

Gov. Brian Kemp said in statement that he and his family were "heartbroken" by the shooting.

"We continue to work closely with local, state, and federal partners to make any and all resources available to help this community on this incredibly difficult day and in the days to come," he said.

President Joe Biden said he was mourning those who were killed, as he pushed Congress to pass gun safety legislation.

“What should have been a joyous back-to-school season in Winder, Georgia, has now turned into another horrific reminder of how gun violence continues to tear our communities apart,” Biden said in a statement.

“Students across the country are learning how to duck and cover instead of how to read and write,” he added. “We cannot continue to accept this as normal.”  

U.S. Attorney General Merrick Garland said he was “devastated” for the affected families and said the Justice Department was ready to provide support. 

School has been in session at Apalachee High School since Aug. 1 .

Schools will be closed for the rest of the week, Barrow County Schools Superintendent Dallas LeDuff said.

Apalachee High is Barrow County’s second high school, according to its website, and opened in 2000.

Senior Breaking News Reporter

Tom Winter is a New York-based correspondent covering crime, courts, terrorism and financial fraud on the East Coast for the NBC News Investigative Unit.

Jonathan Dienst is chief justice contributor for NBC News and chief investigative reporter for WNBC-TV in New York.

Melissa Chan is a reporter for NBC News Digital with a focus on veterans’ issues, mental health in the military and gun violence.

Rebecca Cohen is a breaking news reporter for NBC News Digital.

9 veterans who could be saying goodbye after the 2024 season

Will Leitch

This past weekend, in response to considerable speculation in the midst of what has been the worst season of his career, Cardinals first baseman Paul Goldschmidt made it clear: He intends to return in 2025 . It was a fair question to ask: The 2022 National League MVP Award winner and potential future Hall of Famer has struggled all season, and his contract expires at the end of the year. But Goldschmidt didn’t hesitate: “Yeah, I want to play next year; I want to continue to play.”

So that answers that question. But he’s not the only guy we were wondering about. It’s a special thing, really, to follow a baseball player throughout his career: These are players whose names we have known for nearly two decades now. It is a reasonable question, though, whether over the final month of the season (or two months, for those on playoff-bound teams), we will be seeing them for the last time.

Thus, we wanted to take a moment to look at nine guys who could be near the end of their careers. While they still might come back next year, it’s possible this is it for them -- none has a guaranteed contract beyond 2024. So appreciate them while you can: Their names will remain in your brain for decades to come.

(Note: We are excluding players like Clayton Kershaw and Charlie Blackmon, veterans of one particular franchise who will surely be invited back by their longtime teams if they decide to return, though they have not yet announced their intentions in either direction.)

Kevin Kiermaier , CF, Dodgers Current age: 34

Kiermaier has already announced that he’ll be retiring at the end of the season , so this is unquestionably the last time we’ll all see him. He remains a useful player the same way he has always been a useful player: He’s a brilliant defensive outfielder who can steal a base late in a game if you need him to. Keep an eye on him if the Dodgers make the World Series: He hit .368 with two homers against them as a Ray in the 2020 Series.

Andrew McCutchen , DH, Pirates Current age: 37

The only player on this list to have won an MVP Award, McCutchen is the active leader in games played and one of the most beloved players in the sport. It has been downright gorgeous to see him back in a Pirates uniform for the past two seasons, and if he wanted to continue signing a series of one-year contracts with the team until he was in his 70s, I don’t think that many people would have a big problem with it. He can still hit, by the way: He remains tied for second on the Pirates in homers, with 18. That gives him 233 with Pittsburgh, seven behind Roberto Clemente for third on the franchise’s all-time list.

Sign up to receive our daily Morning Lineup to stay in the know about the latest trending topics around Major League Baseball.

Rich Hill , LHP, Red Sox Current age: 44

It’s a gift to have Hill around at all, especially back in Boston, which is where he’s from and where he has pitched now four different times in his career. You’d have to think this would be his last run -- there isn’t much room for Jamie Moyer types in baseball today -- but then again, we’ve all said that before about him, and here he is, still pitching, in his 20th consecutive MLB season. Baseball will be a little less fun when Rich Hill is officially gone.

Jason Heyward , OF, Astros Current age: 35

Few players have had a more stirring introduction to the big leagues than Heyward, a Georgia native who, in his first game with the Braves, homered with Hank Aaron in attendance. It looked like we were seeing a future Hall of Famer in the making, and while it didn’t turn out that way, Heyward still holds an undeniable place in MLB history thanks to his time with the Cubs, when he was one of the key leaders on the 2016 team that won the franchise's first World Series in 108 years. (His rain-delay speech will forever be the stuff of legend.) Released by the Dodgers on Aug. 24 amidst a roster crunch, Heyward quickly caught on with the Astros and will have another shot to make a postseason impact this fall.

Justin Turner , 1B, Mariners Current age: 39

It has been quite a journey for Turner, who was a struggling, disappointing Mets prospect before heading to Chavez Ravine to become a spiritual leader -- and consistently underrated hitter -- for the Dodgers for nearly a decade. He has done nothing but hit his entire career (he hasn’t had a below-average OPS+ for 13 straight years, including this one), and he has made every lineup he has been in better. Also, did you remember that he started his career with the Orioles? (I didn’t.)

Kyle Hendricks , RHP, Cubs Current age: 34

The only remaining Cub from that 2016 World Series team, Hendricks has always felt like a throwback: a guy who didn’t throw very hard and didn’t strike out very many people but still found a way to get outs. A lot of them, in fact: Remember, he had a 2.13 ERA in that '16 season and had a 1.00 ERA in two starts in the World Series. His special magic seems to have faded this season, but he’ll be beloved around Wrigley Field for the next 100 years, and for very good reason.

Matt Carpenter , DH, Cardinals Current age: 38

Carpenter actually made his debut with the Cardinals on their 2011 World Series championship team, albeit going 1-for-15 in only seven games. He established himself as an on-base force the very next season, finishing sixth in NL Rookie of the Year voting, and he become a beloved Cardinals staple over the next decade with his preternatural batting eye and, eventually, a power stroke. He finished in the top 12 of MVP voting three times, and he was briefly a folk hero in the Bronx when he went on a power surge for the Yankees in 2022. He’ll likely say goodbye with the Cards over the last month of this season.

Jesse Chavez , RHP, Braves Current age: 41

There is something emotionally satisfying about a crafty reliever still hanging on into his 40s: It’s the role we all imagined we could do (if we were far more athletically gifted than we all actually are). Chavez made his debut with the Pirates way back in 2008 as a reliever, but he had a few years where he started for the A’s and Angels about a decade ago. Chavez has had one of his best stretches out of the bullpen for the Braves the past couple of seasons, and he could maybe find his way back to a roster next year. He’ll forever be crafty!

Yuli Gurriel , 1B, Royals Current age: 40

Gurriel didn’t come over from Cuba until he was 32, which is why you probably didn't realize he’s already 40. However, he has played in four World Series and came away with rings in two of them, all with the Astros, where he was in the lineup nearly every day for seven years. He fell off a cliff a little bit after winning a Gold Glove Award and leading the AL in batting in 2021, but he was just added to an MLB roster for the first time this year by the Royals, who have been hammered by injuries. He left his second game with his new team with hamstring tightness, but as long as that does not prove serious, Gurriel could add to his ring collection in October.