Data Structures: Difference between revisions

← Older edit Newer edit →

Revision as of 18:30, 5 November 2019

Data Structures from CMSC420 and more.

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 \(\displaystyle k \times k\)).

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.

@@ Line 28: / Line 28: @@
 ==Spatial Data Structures==
+===Point Quadtree===
+Extension of BST.
 ===PM Quadtree===
+Polygonal Map Quadtree<br>
 Simple to implement. See my implementation [https://github.com/dli7319/unity-data-structures here].
+Requires a known range (region) of values.<br>
+O(log k) where k is the region divided by the distance between the two closest points (i.e. your grid is <math>k \times k</math>).
 ===PR Quadtree===
+Point Region Quadtree<br>
 ===MX Quadtree===
 ===K-d Tree===
+===Restricted Quadtree===
+[https://pdfs.semanticscholar.org/ae3d/922cb5ac1eef9bab178e0a976b5eced069dd.pdf Reference]<br>
+Extension of AVL quadtree where the depth differs by at most one between your 4 children.