# Data Structures

Data Structures from CMSC420 and more.

## Lists

### Skip List

Technically a linked-list but looks like a tree if you squint.

## Hash

Use this all the time if you don't need to iterate through the data structure in order.
Probabilistic O(1) insertion.

#### Linear Probing

One way to handle collisions.

#### Double hashing

Another way to handle collisions.

#### Separate chaining

Another way to handle collisions. Each bucket is a pointer to a linked-list of values.

## Trees

### Treap

A tree and a heap. O(logn) with high probability.

#### Insertion

Insert using BST insert and then heapify using AVL rotations.

## Spatial Data Structures

Extension of BST.

Simple to implement. See my implementation here. Requires a known range (region) of values.
O(log k) where k is the region divided by the distance between the two closest points (i.e. your grid is ${\displaystyle k\times k}$).