Data structures
- bigocheatsheet
- Open Data Structures (in pseudocode)
- Coding Interview University A complete computer science study plan to become a software engineer.
- Shenanigans With Hash Tables
- Think Complexity: free book about data structures and algorithm
- The Lost Art of C Structure Packing
- Lynda - Data Structure
| Name | Insert | Deletion | Search | Note |
|---|---|---|---|---|
| Linked list | O(1) | O(1) | O(N) | |
| Array | O(1) | O(1) | O(N) | insertion and deletion should take into account the memory management |
| Stack | O(1) | O(N) | O(N) | there is not proper delete/search operation |
| Queue | O(1) | O(N) | O(N) | there is not proper delete/search operation |
| BST | O(N), O(log N) | O(N), O(log N) | O(N), O(log N) | depend strongly on how balanced is |
| Dictionary | O(1) | O(1) | O(1) |
| Name | Insert | Extract Min | Min |
|---|---|---|---|
| Heap | O(log N) | O(log N) | O(1) |
Hash tables
Multiplicative hashing
We start with defining an hash function that takes a value from w-bit integer and returns a d-bit integer (the hash)
hash(x):
return ((z*x) mod 2**w) >> (w - d)
z is an odd integer chosen at random. Mathematically this works because the set of odd integers module \(2^w\) forms a modular multiplicative group (I know \(x\) can be even but hey, this is not cryptography :P). Moreover
$$ \left(Z/2^k Z\right)^\times\sim C_2\times C_{2^{k - 2}} $$
not being a cyclic group we know that it will not span all the domain.
- multiplicative hashing POC hash.c
Trees
A tree is a graph that is not cyclic.
Binary tree
This is a subset of trees where nodes can only have up to to 2 child, usually named left and right.
There are a couple of ordering mechanism: take the following binary tree
<A>
/ \
<B> <C>
/ \
<D> <E>
pre-order returns A, B, D, E, Cperforming the following steps
- return the root node
- traverse recursively the left subtree
- traverse recursively the right subtree
in-order returns D, B, E, A, C performing the following steps
- traverse recursively the left subtree
- return the root node
- traverse recursively the right subtree
post-order returns D, E, B, C, A instead with the following procedure
- traverse recursively the left subtree
- traverse recursively the right subtree
- return the root node
level-order returns A, B, C, D, E, the steps are
- add the root node to a queue
- pop the last node from the queue and return it
- add all children of popped node to queue and continue from step 2 until queue is empty
The number of unlabeled trees with \(N\) nodes is given by the Catalan's numbers
$$ T(N) = \sum_{i=1}^{N} T(i - 1)\cdot T(N - i) = {(2N)!\over(N + 1)!N!} $$
instead for labeled binary tree we have
$$ T^\prime(N)= N!T(N) = {(2N)!\over(N + 1)!} $$
Links
- Modified pre order traversal tree
- django-mptt/django-mptt Utilities for implementing a modified pre-order traversal tree in django
- Tree traversal algorithms
- Inorder Tree Traversal without Recursion
Tools
- visualgo.net: visualising data structures and algorithms through animation