Index

amortized cost

1.5.0.0.1

amortized running time

ancestor

array

circular: 2.3

$\mathtt{ArrayDeque}$

2.4

$\mathtt{ArrayQueue}$

2.3

arrays

$\mathtt{ArrayStack}$

2.1

asymptotic notation

1.3.3

AVL tree

9.4

-tree

-tree

-tree

14.2

backing array

$\mathtt{Bag}$

$\mathtt{BDeque}$

3.3

Bibliography on Hashing

big-Oh notation

1.3.3

binary heap

10.

binary logarithm

binary search

13.2 | 14.2.1

binary search tree

6.2

height balanced: 9.4
partial rebuilding: 8.
random: 7.1
randomized: 7.3
red-black: 9.
size-balanced: 6.3
versus skiplist: 4.5

binary search tree property

6.2

binary tree

complete: 10.1
heap-ordered: 10.1
search: 6.2

binary-tree traversal

6.1.2

$\mathtt{BinaryHeap}$

$\mathtt{BinarySearchTree}$

6.2

$\mathtt{BinaryTree}$

6.1

$\mathtt{BinaryTrie}$

13.1

binomial coefficients

binomial heap

black node

black-height property

block

14. | 14.

block store

14.1

$\mathtt{BlockStore}$

14.1

borrow

14.2.3

bounded deque

3.3

$\mathtt{BPlusTree}$

breadth-first traversal

6.1.2

breadth-first-search

12.3.1

celebrity

see universal sink

$\mathtt{ChainedHashTable}$

chaining

child

left: 6.
right: 6.

circular array

2.3

coin toss

1.3.4 | 4.4

collision resolution

colour

$\mathtt{compare(x,y)}$

1.2.4

comparison tree

11.1.4

comparison-based sorting

11.1

complete binary tree

complexity

space: 1.5
time: 1.5

conflict graph

connected components

connected graph

contact list

correctness

$\mathtt{CountdownTree}$

counting-sort

11.2.1

credit invariant

14.2.4

credit scheme

8.1.1 | 14.2.4

$\mathtt{CubishArrayStack}$

cuckoo hashing

cycle

cycle detection

12.3.2

$\mathtt{DaryHeap}$

$\mathtt{decreaseKey(u,y)}$

degree

12.2

dependencies

1.7

depth

depth-first-search

12.3.2

deque

1.2.1

bounded: 3.3

descendant

dictionary

directed edge

directed graph

disk access model

divide-and-conquer

11.1.1

$\mathtt{DLList}$

3.2

doubly-linked list

3.2

$\mathtt{DualArrayDeque}$

2.5

dummy node

3.2

Dyck word

$\mathtt{DynamiteTree}$

(Euler's constant)

edge

emergency services

Euler's constant

expected cost

1.5.0.0.2

expected running time

1.3.4 | 1.5

expected value

exponential

Ext4

external memory

external memory hashing

external memory model

external storage

Eytzinger's method

factorial

family tree

$\mathtt{FastArrayStack}$

Fibonacci heap

FIFO queue

1.2.1

file system

finger

4.5 | 7.3

finger search

in a skiplist: 4.5
in a treap: 7.3

fusion tree

13.4

general balanced tree

git

Google

1.1.0.0.3

graph

connected: 12.4
strongly-connected: 12.4

(harmonic number)

hard disk

harmonic number

hash code

5. | 5.3

for arrays: 5.3.2
for compound objects: 5.3.2
for primitive data: 5.3.1
for strings: 5.3.2

hash function

perfect: 5.4

hash table

cuckoo: 5.4
two-level: 5.4

hash value

$\mathtt{hash(x)}$

hashing

multiplicative: 5.1.1 | 5.4
multiply-add: 5.4
tabulation: 7.3
universal: 5.4

hashing with chaining

5.1 | 5.4

heap

10.

binary: 10.
binomial: 10.3
Fibonacci: 10.3
leftist: 10.3
pairing: 10.3
skew: 10.3

heap order

heap property

heap-ordered binary tree

heap-sort

11.1.3

height

in a tree: 6.
of a skiplist: 4.1
of a tree: 6.

height-balanced

9.4

HFS+

I/O model

in-order number

in-order traversal

in-place algorithm

11.3

incidence matrix

indicator random variable

interface

1.2

Java Collections Framework

leaf

left child

left rotation

left-leaning property

9.2.2

left-leaning red-black tree

9.2.2

leftist heap

LIFO queue

1.2.1 | see alsostack

linear probing

5.2

$\mathtt{LinearHashTable}$

5.2

linearity of expectation

linked list

doubly-: 3.2
singly-: 3.1
space-efficient: 3.3
unrolled: see also $\mathtt{SEList}$

$\mathtt{List}$

1.2.2

logarithm

binary: 1.3.1
natural: 1.3.1

lower-bound

11.1.4

map

matched string

$\mathtt{MeldableHeap}$

10.2

$\mathtt{memcpy(d,s,n)}$

merge

9.1.2 | 14.2.3

merge-sort

3.4 | 11.1.1

min-wise independence

7.3

$\mathtt{MinDeque}$

$\mathtt{MinQueue}$

$\mathtt{MinStack}$

modular arithmetic

2.3

multiplicative hashing

5.1.1 | 5.4

multiply-add hashing

$\mathtt{n}$

1.6

natural logarithm

no-red-edge property

NTFS

number

in-order: 6.3
post-order: 6.3
pre-order: 6.3

notation

1.3.3

open addressing

5.2 | 5.4

Open Source

ordered tree

pair

pairing heap

palindrome

parent

partial rebuilding

path

pedigree family tree

6.3 | 10.3

perfect hash function

perfect hashing

permutation

random: 7.1

pivot element

11.1.2

planarity testing

post-order number

post-order traversal

potential

2.5.1

potential method

2.5.1 | 3.3.5 | 9.3

pre-order number

pre-order traversal

prime field

5.3.3

priority queue

1.2.1 | see alsoheap

probability

queue

FIFO: 1.2.1
LIFO: 1.2.1
priority: 1.2.1

quicksort

11.1.2

radix-sort

11.2.2

RAM

1.4

random binary search tree

random permutation

randomization

randomized algorithm

randomized binary search tree

7.3

randomized data structure

$\mathtt{RandomQueue}$

reachable vertex

recursive algorithm

6.1.1

red node

red-black tree

9. | 9.2.2

$\mathtt{RedBlackTree}$

9.2.2

remix

right child

right rotation

rooted tree

$\mathtt{RootishArrayStack}$

2.6

rotation

run

5.2.1

running time

amortized: 1.5
expected: 1.3.4 | 1.5
worst-case: 1.5

scapegoat

$\mathtt{ScapegoatTree}$

8.1

search path

in a $\mathtt{BinaryTrie}$: 13.1
in a binary search tree: 6.2.1
in a skiplist: 4.1

secondary structure

13.3

$\mathtt{SEList}$

3.3

sentinel node

4.1

$\mathtt{Sequence}$

share

simple path/cycle

singly-linked list

3.1

size-balanced

skew heap

skiplist

4.1

versus binary search tree: 4.5

$\mathtt{SkiplistList}$

4.3

$\mathtt{SkiplistSSet}$

4.2

$\mathtt{SLList}$

3.1

social network

solid-state drive

sorting algorithm

comparison-based: 11.1

sorting lower-bound

11.1.4

source

space complexity

spanning forest

speciation event

species tree

split

9.1.1 | 14.2.2

square roots

2.6.4

$\mathtt{SSet}$

1.2.4

stable sorting algorithm

11.2.1

stack

1.2.1

$\mathtt{std::copy(a0,a1,b)}$

Stirling's Approximation

stratified tree

13.4

string

matched: 1.8

strongly-connected graph

successor search

1.2.4

$\mathtt{System.arraycopy(s,i,d,j,n)}$

tabulation hashing

5.2.3 | 7.3

target

tiered-vector

time complexity

traversal

breadth-first: 6.1.2
in-order: 6.3
of a binary tree: 6.1.2
post-order: 6.3
pre-order: 6.3

$\mathtt{Treap}$

$\mathtt{TreapList}$

7.3

tree

-ary: 10.3
binary: 6.
ordered: 6.
rooted: 6.

tree traversal

6.1.2

$\mathtt{Treque}$

two-level hash table

underflow

14.2.3

universal hashing

universal sink

unrolled linked list

see also $\mathtt{SEList}$

$\mathtt{USet}$

van Emde Boas tree

13.4

vertex

wasted space

2.6.2

web search

$\mathtt{WeightBalancedTree}$

word

1.4

word-RAM

1.4

worst-case running time

$\mathtt{XFastTrie}$

13.2

XOR-list