Data Structures

Amortised analysis

\[\text{aggregate true cost} \leq \text{aggregate amortised cost}\]

Stack ADT

LIFO data structure that only offers operations for the top item

ADT Stack {
    boolean isEmpty();
    void push(Item x);
    Item pop(); // precondition: !isEmpty
    Item top(); // precondition: !isEmpty

Commonly implemented using an array and a TOS (top-of-stack) index or linked list.

List ADT

ADT List {
    boolean isEmpty();
    Item head(); // precondition: !isEmpty
    void prepend(Item x);
    List tail(); // precondition: !isEmpty
    void setTail(List newTail); // precondition: !isEmpty

Queue ADT

Similar to a stack, but is LIFO.

ADT Queue {
    boolean isEmpty();
    void push(Item x);
    Item pop(); // precondition: !isEmpty
    Item first(); // precondition: !isEmpty

A double-ended queue (deque) generalises the stack/queue to a data structure that allows insertions and extractions at the front or rear.

Dictionary ADT

ADT Dictionary {
    void set(Key k, Value v);
    Value get(Key k);
    void delete(Key k);

Priority queue ADT

ADT PriorityQueue {
    void insert(Item x)
    Item first();
    Item popmin();
    void decreasekey();
    void delete(Item x);

Disjoint Set ADT

ADT DisjointSet {
    Handle get_set_with(Item x);
    void add_singleton(Item x);
    void merge(Handle x, Handle y);

Flat forest and deep forest

Lazy forest

Binary Search Tree

Interactive practice

2-3-4 tree

Red Black Tree

Interactive practice

An RBT is a BST that satisfies five invariants:

  1. Every node is either red or black
  2. The root is black
  3. All leaf nodes are black, and don’t contain data
  4. If a node is red, its children are both black.
  5. Any path from a given node to leaves contains the same number of black nodes.

Red black trees are isomorphic to 2-3-4 trees, but has the advantage that it is easier to code:

Operations that don’t modify the tree structure are the same as for BSTs. But in order to preserve the RBT invariants, other operations require rotations.

In the diagram above, D has been rotated to the right, then B has been rotated to the left. These rotations apply to non-root nodes as well.

To rotate a parent x right given its left child y:

if y != null:
    x.l = y.r
    y.r = x
    x = y

Likewise, a left-rotation:

if y != null:
    x.r = y.l
    y.l = x
    x = y

RBT Insertion

Case 1 – red uncle

Case 2 – black uncle, bent

Left-rotate n and we are now in case 3.

Case 3 – black uncle, straight


B-tree deletion

def delete(k):
    if k is in bottom node B:
        if B cannot lose key:
        delete k from B
        swap(k, successor(k))
        # now k is in a bottom node

def refill(B):
    PRECONDITION: B has t-1 keys
    POSTCONDITION: B has more than t-1 keys
    if either sibling can lose keys:
        redistribute keys to B
        # B and all siblings have t-1 keys
        merge B with a sibling
        if B.parent has fewer than t-1 keys:


Open addressing

Binary heap

Binomial heap

Fibonacci heap

def push(k, v):
    h = new heap(k, v) # only one node
    add h to rootlist
    update minroot if k < minroot.key
def popmin():
    min = copy(minroot)
    for child in minroot.children:
        clear child mark
        add child to rootlist
    delete minroot
    minroot = minimum of rootlist
    return min
def cleanup():
    To cleanup, we use an auxiliary array where the index corresponds
    to the degree. If there is already a tree in an index, merge.
    root_array = [None, None, ...]
    for tree t in roots:
        x = t
        while root_array[] is not None:
            u = root_array[]
            root_array[] = None
            x = merge(x, u)
        root_array[] = x
    return [root for root in root_array if root is not None]
def decreasekey(v, new_key):
    let n be the node containing v
    n.key = new_key
    if n violates heap condition:
            p = n.parent
            remove n from p.children
            insert n into rootlist, updaing minroot
            n.loser = False
            n = p
        until p.loser == False
        if p not in rootlist:
            p.loser = True 

Analysis using potentials

\[\Phi = \text{num roots} + 2(\text{num loser nodes})\]

Relationship to Fibonacci numbers

\[N_d \geq N_{d-2} + N_{d-3} + \cdots + N_0 + N_0 + 1\] \[n \geq F_{d+2} \geq \phi^d \implies d_{max} = O(\log n)\]