# Data Structures

Data Structures from CMSC420 and more.

## Contents

## Lists

### XOR Linked List

### 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

### Heap

### AVL

### Red-Black

### 2-3

### Treap

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

#### Insertion

Insert using BST insert and then heapify using AVL rotations.

### Splay Tree

## Spatial Data Structures

### Point Quadtree

Extension of BST.

### PM Quadtree

Polygonal Map Quadtree

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 ).

### PR Quadtree

Point Region Quadtree

### MX Quadtree

### K-d Tree

### Restricted Quadtree

Reference

Extension of AVL quadtree where the depth differs by at most one between your 4 children.