# Data structures

Name Insert Deletion Search Note
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

1. add the root node to a queue
2. pop the last node from the queue and return it
3. 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)!}$$

## Tools

• visualgo.net: visualising data structures and algorithms through animation