Data Structures

Amortised analysis

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

B-tree deletion

Hash-tables

Open addressing

Binary heap

Binomial heap

Fibonacci heap

Analysis using potentials

Relationship to Fibonacci numbers