Today I Learned

Some of the things I've learned every day since Oct 10, 2016

124: Skip List Search Algorithm

The following is an informal description of the algorithm for searching for an element in a skip list:

If you look the shape of the nodes that the algorithm visits on a given example, the general case of the search time being $O(\log{} n)$ makes intuitive sense.

123: Skip Lists (Intro)

skip list is a data structure similar to a linked list which stores an ordered sequence of elements and is built specifically for fast search within the sequence. The way it’s commonly implemented is as a hierarchy of linked lists, with the first list containing all the elements of the skip list, and each successive linked list containing a sparser subset of the elements in the previous one.

To search for an element within the skip list one then starts with the sparsest linked list, getting as ‘close’ to the desired element as possible, then moves directly down to that same position in the next linked list and continues searching until the item is found (or not).

This animation depicts the insertion of the element 80 into a skip list of positive integers (insertion being equivalent to searching):

Credit: Artyom Kalinin

In the average case, the skip list uses $O(n)$ space and takes just $O(\log{} n)$ time for searching operations.

114: Iterative Deepening Search

Iterative deepening depth-first search is a graph traversal algorithm which visits (new) nodes in effectively the same order as breadth-first search, but with lower memory usage and a runtime of $O(b^d)$ (where $b$ is the branching factor of the graph and $d$ is the depth of the goal node.

The algorithm does pretty much what the name describes: it iteratively performs a typical depth-first search up do a set maximum depth, incrementing the depth with each iteration. In this way, nodes are seen for the first time in the order they would be seen by BFS while using lower amounts of memory. In addition, since it runs on DFS the algorithm uses just $O(d)$ space, where $d$ is the depth of the goal.