Skip to content

Data structures

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.

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)!} $$

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

B-Tree

Particular form of tree that extends that binary search tree

According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:

  • Every node has at most m children.
  • Every internal node has at least ⌈m/2⌉ children.
  • Every non-leaf node has at least two children.
  • All leaves appear on the same level.
  • A non-leaf node with k children contains k−1 keys.

Each internal node's keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: a1 and a2. All values in the leftmost subtree will be less than a1, all values in the middle subtree will be between a1 and a2, and all values in the rightmost subtree will be greater than a2.

Tools

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