Gnarley trees
Introduction
(current)
Ordered dictionaries
Introduction
Naïve solutions
Applications
Binary search tree
Balancing trees
AVL tree
2-3 tree
2-3-4 tree
B tree
B
+
tree
Red-black tree
AA tree
Skiplist
Treap
Splay tree
Scapegoat tree
Priority queues
Introduction
Naïve solutions
Applications
Heap
d-ary heap
Leftist heap
Skew heap
Pairing heap
Binomial heap
Lazy binomial heap
Fibonacci heap
Union-find
Introduction
Naïve solutions
Union find
Stringology
Introduction
Trie
Suffix tree
Preliminaries
Different notions of complexity
B
+
-tree
Idea:
like B-tree but all values are stored in leaves
internal nodes store copies of keys and are used for navigation but don't store any data
Advantages:
since internal nodes store no data, we can pack more keys in the same space ⇒ higher branching factor ⇒ smaller depth ⇒ faster search
since all values are in leaves, iterating them is much easier and faster than the tree traversal in B-trees
[You can
download the application
for offline viewing.]
References
R. Bayer and E.M. McCreight. Organization and maintenance of large ordered indexes.
Acta informatica
, 1(3):173-189, 1972. [
bib
] [
pdf
]
D. Comer. Ubiquitous B-tree.
ACM Computing Surveys (CSUR)
, 11(2):121-137, 1979. [
bib
]