Data Structures: Difference between revisions

Revision as of 14:16, 24 February 2020

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

Wikipedia: Red–black tree
Geeks for geeks introduction
Geeks for geeks insertion
Geeks for geeks deletion

A red-black tree follows the following rules

Each node is either red or black.
The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
All leaves (NIL) are black.
If a node is red, then both its children are black.
Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

Intuition

Consider any tree with a left and right child. From rule 4, we see that at most n/2 nodes are red. At least half will be black. Red nodes or levels are those interspersed between black levels. If the left child has \(\displaystyle m\) levels then at most the right child can have \(\displaystyle 2m\) levels.

Intuitively, this is more relaxed than AVL trees so they will have fewer operations for insert/delete but will be less balanced.
Red-black trees are used in in C++ (ordered_map, ordered_set) and Java (TreeMap, TreeSet).

=Complexity

\(\displaystyle 2\log (n+1)\) height.
\(\displaystyle O(\log n)\) insert, delete

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 20: / Line 20: @@
 ===AVL===
 ===Red-Black===
+[[Wikipedia: Red–black tree]]<br>
+[https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/ Geeks for geeks introduction]<br>
+[https://www.geeksforgeeks.org/red-black-tree-set-2-insert/ Geeks for geeks insertion]<br>
+[https://www.geeksforgeeks.org/red-black-tree-set-3-delete-2/ Geeks for geeks deletion]<br>
+A red-black tree follows the following rules
+# Each node is either red or black.
+# The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
+# All leaves (NIL) are black.
+# If a node is red, then both its children are black.
+# Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.
+====Intuition====
+Consider any tree with a left and right child.
+From rule 4, we see that at most n/2 nodes are red. At least half will be black.
+Red nodes or levels are those interspersed between black levels.
+If the left child has <math>m</math> levels then at most the right child can have <math>2m</math> levels.
+Intuitively, this is more relaxed than AVL trees so they will have fewer operations for insert/delete but will be less balanced.<br>
+Red-black trees are used in in C++ (ordered_map, ordered_set) and Java (TreeMap, TreeSet).
+====Complexity===
+<math>2\log (n+1)</math> height.<br>
+<math>O(\log n)</math> insert, delete
 ===2-3===
 ===Treap===