Index

9-1-1
1.
abstract data type
see interface
adjacency list
12.2
adjacency matrix
12.1
algorithmic complexity attack
5.4
amortized cost
1.5.0.0.1
amortized running time
1.5
ancestor
6.
array
circular
2.3
$ \mathtt{ArrayDeque}$
2.4
$ \mathtt{ArrayQueue}$
2.3
arrays
2.
$ \mathtt{ArrayStack}$
2.1
asymptotic notation
1.3.3
AVL tree
9.4
$ B^*$-tree
14.3
$ B^+$-tree
14.3
$ B$-tree
14.2
backing array
2.
$ \mathtt{Bag}$
1.8
$ \mathtt{BDeque}$
3.3
Bibliography on Hashing
5.4
big-Oh notation
1.3.3
binary heap
10.
binary logarithm
1.3.1
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
6.
complete
10.1
heap-ordered
10.1
search
6.2
binary-tree traversal
6.1.2
$ \mathtt{BinaryHeap}$
10.1
$ \mathtt{BinarySearchTree}$
6.2
$ \mathtt{BinaryTree}$
6.1
$ \mathtt{BinaryTrie}$
13.1
binomial coefficients
1.3.2
binomial heap
10.3
black node
9.2
black-height property
9.2
block
14. | 14.
block store
14.1
$ \mathtt{BlockStore}$
14.1
borrow
14.2.3
bounded deque
3.3
$ \mathtt{BPlusTree}$
14.3
breadth-first traversal
6.1.2
breadth-first-search
12.3.1
celebrity
see universal sink
$ \mathtt{ChainedHashTable}$
5.1
chaining
5.1
child
6.
left
6.
right
6.
circular array
2.3
coin toss
1.3.4 | 4.4
collision resolution
5.4
colour
9.2
$ \mathtt{compare(x,y)}$
1.2.4
comparison tree
11.1.4
comparison-based sorting
11.1
complete binary tree
10.1
complexity
space
1.5
time
1.5
conflict graph
12.
connected components
12.4
connected graph
12.4
contact list
1.
correctness
1.5
$ \mathtt{CountdownTree}$
8.2
counting-sort
11.2.1
credit invariant
14.2.4
credit scheme
8.1.1 | 14.2.4
$ \mathtt{CubishArrayStack}$
2.7
cuckoo hashing
5.4
cycle
12.
cycle detection
12.3.2
$ \mathtt{DaryHeap}$
10.3
$ \mathtt{decreaseKey(u,y)}$
10.3
degree
12.2
dependencies
1.7
depth
6.
depth-first-search
12.3.2
deque
1.2.1
bounded
3.3
descendant
6.
dictionary
1.2.3
directed edge
12.
directed graph
12.
disk access model
14.3
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
1.8
$ \mathtt{DynamiteTree}$
8.2
$ e$ (Euler's constant)
1.3.1
edge
12.
emergency services
1.
Euler's constant
1.3.1
expected cost
1.5.0.0.2
expected running time
1.3.4 | 1.5
expected value
1.3.4
exponential
1.3.1
Ext4
14.3
external memory
14.
external memory hashing
14.3
external memory model
14.
external storage
14.
Eytzinger's method
10.1
factorial
1.3.2
family tree
6.3
$ \mathtt{FastArrayStack}$
2.2
Fibonacci heap
10.3
FIFO queue
1.2.1
file system
1.
finger
4.5 | 7.3
finger search
in a skiplist
4.5
in a treap
7.3
fusion tree
13.4
general balanced tree
8.2
git
Why
Google
1.1.0.0.3
graph
12.
connected
12.4
strongly-connected
12.4
$ H_k$ (harmonic number)
7.1
hard disk
14.
harmonic number
7.1
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
5.
cuckoo
5.4
two-level
5.4
hash value
5.1
$ \mathtt{hash(x)}$
5.1
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
10.1
heap property
7.2
heap-ordered binary tree
10.1
heap-sort
11.1.3
height
in a tree
6.
of a skiplist
4.1
of a tree
6.
height-balanced
9.4
HFS+
14.3
I/O model
14.3
in-order number
6.3
in-order traversal
6.3
in-place algorithm
11.3
incidence matrix
12.4
indicator random variable
1.3.4
interface
1.2
Java Collections Framework
1.8
leaf
6.
left child
6.
left rotation
7.2
left-leaning property
9.2.2
left-leaning red-black tree
9.2.2
leftist heap
10.3
LIFO queue
1.2.1 | see alsostack
linear probing
5.2
$ \mathtt{LinearHashTable}$
5.2
linearity of expectation
1.3.4
linked list
3.
doubly-
3.2
singly-
3.1
space-efficient
3.3
unrolled
see also $ \mathtt{SEList}$
$ \mathtt{List}$
1.2.2
logarithm
1.3.1
binary
1.3.1
natural
1.3.1
lower-bound
11.1.4
map
1.2.3
matched string
1.8
$ \mathtt{MeldableHeap}$
10.2
$ \mathtt{memcpy(d,s,n)}$
2.2
merge
9.1.2 | 14.2.3
merge-sort
3.4 | 11.1.1
min-wise independence
7.3
$ \mathtt{MinDeque}$
3.4
$ \mathtt{MinQueue}$
3.4
$ \mathtt{MinStack}$
3.4
modular arithmetic
2.3
multiplicative hashing
5.1.1 | 5.4
multiply-add hashing
5.4
$ \mathtt{n}$
1.6
natural logarithm
1.3.1
no-red-edge property
9.2
NTFS
14.3
number
in-order
6.3
post-order
6.3
pre-order
6.3
$ O$ notation
1.3.3
open addressing
5.2 | 5.4
Open Source
Why
ordered tree
6.
pair
1.2.3
pairing heap
10.3
palindrome
3.4
parent
6.
partial rebuilding
8.
path
12.
pedigree family tree
6.3 | 10.3
perfect hash function
5.4
perfect hashing
5.4
permutation
1.3.2
random
7.1
pivot element
11.1.2
planarity testing
12.4
post-order number
6.3
post-order traversal
6.3
potential
2.5.1
potential method
2.5.1 | 3.3.5 | 9.3
pre-order number
6.3
pre-order traversal
6.3
prime field
5.3.3
priority queue
1.2.1 | see alsoheap
probability
1.3.4
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
7.1
random permutation
7.1
randomization
1.3.4
randomized algorithm
1.3.4
randomized binary search tree
7.3
randomized data structure
1.3.4
$ \mathtt{RandomQueue}$
2.7
reachable vertex
12.
recursive algorithm
6.1.1
red node
9.2
red-black tree
9. | 9.2.2
$ \mathtt{RedBlackTree}$
9.2.2
remix
Why
right child
6.
right rotation
7.2
rooted tree
6.
$ \mathtt{RootishArrayStack}$
2.6
rotation
7.2
run
5.2.1
running time
1.5
amortized
1.5
expected
1.3.4 | 1.5
worst-case
1.5
scapegoat
8.
$ \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}$
8.2
share
Why
simple path/cycle
12.
singly-linked list
3.1
size-balanced
6.3
skew heap
10.3
skiplist
4.1
versus binary search tree
4.5
$ \mathtt{SkiplistList}$
4.3
$ \mathtt{SkiplistSSet}$
4.2
$ \mathtt{SLList}$
3.1
social network
1.
solid-state drive
14.
sorting algorithm
comparison-based
11.1
sorting lower-bound
11.1.4
source
12.
space complexity
1.5
spanning forest
12.4
speciation event
6.3
species tree
6.3
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)}$
2.2
Stirling's Approximation
1.3.2
stratified tree
13.4
string
matched
1.8
strongly-connected graph
12.4
successor search
1.2.4
$ \mathtt{System.arraycopy(s,i,d,j,n)}$
2.2
tabulation hashing
5.2.3 | 7.3
target
12.
tiered-vector
2.7
time complexity
1.5
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}$
7.2
$ \mathtt{TreapList}$
7.3
tree
6.
$ d$-ary
10.3
binary
6.
ordered
6.
rooted
6.
tree traversal
6.1.2
$ \mathtt{Treque}$
2.7
two-level hash table
5.4
underflow
14.2.3
universal hashing
5.4
universal sink
12.4
unrolled linked list
see also $ \mathtt{SEList}$
$ \mathtt{USet}$
1.2.3
van Emde Boas tree
13.4
vertex
12.
wasted space
2.6.2
web search
1.
$ \mathtt{WeightBalancedTree}$
8.2
word
1.4
word-RAM
1.4
worst-case running time
1.5
$ \mathtt{XFastTrie}$
13.2
XOR-list
3.4
$ \mathtt{YFastTrie}$
13.3



opendatastructures.org