5,337
edits
Data Structures: Difference between revisions
no edit summary
(→Trees) |
No edit summary |
||
| Line 1: | Line 1: | ||
Data Structures from CMSC420 and more. | 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.<br> | |||
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== | ==Trees== | ||
===Heap=== | |||
===AVL=== | ===AVL=== | ||
===Red-Black=== | ===Red-Black=== | ||
| Line 10: | Line 26: | ||
Insert using BST insert and then heapify using AVL rotations. | Insert using BST insert and then heapify using AVL rotations. | ||
===Splay Tree=== | ===Splay Tree=== | ||
==Spatial Data Structures== | ==Spatial Data Structures== | ||
===PM Quadtree=== | ===PM Quadtree=== | ||
Simple to implement. See my implementation [https://github.com/dli7319/unity-data-structures here]. | |||
===PR Quadtree=== | ===PR Quadtree=== | ||
===MX Quadtree=== | ===MX Quadtree=== | ||
===K-d Tree=== | ===K-d Tree=== | ||