# 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, C`

performing 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