.. _SkipList:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "SkipList";ODSA.SETTINGS.MODULE_LONG_NAME = "SkipLists";ODSA.SETTINGS.MODULE_CHAPTER = "Slides"; ODSA.SETTINGS.BUILD_DATE = "2019-04-01 22:21:50"; ODSA.SETTINGS.BUILD_CMAP = true;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:



.. odsalink:: DataStructures/SkipList.css

.. odsalink:: AV/SearchStruct/SkipListIntroCON.css

.. odsalink:: AV/SearchStruct/SkipListInsertCON.css
.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012-2013 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer


=========
SkipLists
=========

SkipList Idea
~~~~~~~~~~~~~
   .. inlineav:: SkipListIntroCON ss
      :output: show


SkipList Reality
~~~~~~~~~~~~~~~~
   .. inlineav:: SkipListInsertCON ss
      :output: show
   

Analysis
~~~~~~~~
   * Best-case behavior is "balanced": :math:`\Theta(\log n)` (like a
     BST).
   * Worst-case behavior: All nodes at the same level (regardless of
     what level): Effectively degenerates to a linked list (like a
     BST).
   * Reality: Its behavior is not so dependent on order of inserts as
     a BST. Its similar to what BST cost would be if we randomized the
     input order. A huge improvement in expected performance!

Programming Principles
~~~~~~~~~~~~~~~~~~~~~~
   #. All container classes should be general.
   #. Any container class's initial state should be identical to its
      empty state.

.. odsascript:: DataStructures/SkipList.js
.. odsascript:: AV/SearchStruct/SkipListIntroCON.js
.. odsascript:: AV/SearchStruct/SkipListInsertCON.js