# REMARKABLE TREES

@bodil

### PERSISTENT DATA STRUCTURES

A data structure that persists its current state when changed.

### THE BAGWELL TRIE

How is vector formed?

What's the problem with cons lists anyway?

### COMPLEXITY

We need a way to talk about the efficiency of operations on data structures.

Big O notation!

### CONSTANT TIME: O(1)

Same amount of work regardless of the size of the data structure.

### LINEAR TIME: O(n)

Number of operations proportional to the size (n) of the data structure.

### LOGARITHMIC TIME: O(log n)

Number of operations logarithmic to the size of the data structure.

### BIG O NOTATION

O(1) = constant time

O(log n) = logarithmic time

O(n) = linear time

O(n log n) = linear × logarithmic time

### AMORTISATION

Spreading the cost over several operations.

car = contents of address register

cdr = contents of decrement register

### THESE NAMES COMPOSE!

cadr = car of cdr = second element

caddr = car of cdr of cdr = third element

cddr = cdr of cdr = third element onward

caar = car of car = first element of first element

tail →

TRIES

and the hardest problem in computer science

### TRIES

Tries are prefix or radix based search trees.

Phil Bagwell

Rich Hickey

# HICKEY TRIE

INVARIANT:

Only the rightmost node at each level can be underfull.

### HICKEY TRIE BIG O

Push/pop back: O(logₖ n)

Push/pop front: O(n)

Lookup: O(logₖ n)

Concat: O(n)

Split: O(n)

### HICKEY TRIES: FINAL VERDICT

Push/pop back: O(1) amortised

Push/pop front: O(n)

Lookup: O(logₖ n)

Concat: O(n)

Split: O(n)

INVARIANT:

Rightmost and leftmost nodes can be underfull.

### IMMUTABLE.JS TRIES

Push/pop back: O(logₖ n)

Push/pop front: O(logₖ n)

Lookup: O(logₖ n)

Concat: O(n)

Split: O(logₖ n)

### IM.JS WITH HEAD + TAIL

Push/pop back: O(1) amortised

Push/pop front: O(1) amortised

Lookup: O(logₖ n)

Concat: O(n)

Split: O(logₖ n)

DO YOU HAVE A MOMENT TO TALK ABOUT

### RRB TREES

Push/pop: O(logₖ n)

Lookup: O(logₖ n)

Concat: O(logₖ n)

Split: O(logₖ n)

### RRB TREES WITH HEAD + TAIL

Push/pop: O(1) amortised

Lookup: O(logₖ n)

Concat: O(logₖ n)

Split: O(logₖ n)

# Thank you!

bodil.lol/bagwell/

immutable.rs

@bodil

BELKA & STRELKA