Dictionaries – What We Know So Far
The standard Dictionary ADT operations are insert, search and
delete.
When a “good” hash table implementation is used, these
operations can be performed in O(1) time (either worst case or
amortized/expected value, depending on the implementation).
However, hash tables do not facilitate any operations that make
use of an ordering of the keys, such as:
• maximum/minimum
• predecessor/successor
The best we can do is iterate over all the entries in the table. For a
dictionary of size n that is stored in an array of length r, the result
is O(n+r) performance.
1/24
Dictionaries – What We Know So Far
The standard next step in COMP 2140/COMP 3170 is to introduce
balanced trees (AVL trees, red-black trees, B-trees, 2-3 trees...).
On a dictionary of size n:
• Insert, search and delete can be done in O(log(n)) time.
→ worse than a hash table
• Maximum/minimum and predecessor/successor can be done
in O(log(n)) time.
→ better than a hash table
• A dictionary of size n requires n nodes and therefore Θ(n)
memory.
→ better than a hash table
Can we get back down under O(log(n)) time while still only using
Θ(n) space?
2/24
Interlude – What Are We Counting, Exactly?
Any piece of data is stored in computer memory as a sequence of
bits.
Standard assumption: a computer’s memory is organized into
words, where each word consists of w bits for some constant w
(e.g., w = 32 or w = 64).
• Any value from 0 to 2w −1 can be represented by one word.
• More generally, the value M can be represented by Θ(log(M))
words.
• Memory addresses are words. A pointer is assumed to require
O(1) words.
3/24
Interlude – What Are We Counting, Exactly?
“On a balanced search tree of size n, the insert, search and delete
operations can be performed in O(log(n)) time, using Θ(n) space.”
The n in this statement can be viewed as counting words.
• Standard assumption: one dictionary entry requires O(1)
words.
• A balanced search tree with n dictionary entries requires Θ(n)
nodes. Each node consists of O(1) entries plus O(1) pointers,
for a total of O(1) words per node. Thus the total memory
required is Θ(n) words.
• A statement about time complexity conveys a relationship
between the number of words of memory required and the
number of operations required.
4/24
Interlude – What Are We Counting, Exactly?
New assumptions
• Assume that the keys in the dictionary are drawn from some
discrete finite universe of the form U = {0,1,...,u−1},
where u ∈ Z+.
• The largest value in U is the integer u−1. Assume that O(1)
words are required to represent u−1.
Consequently, one word consists of O(log(u)) bits.
In the data structures that we are going to build, the time
complexities of the resulting dictionary operations may depend on
n, u, or both.
5/24
Warm-up: Bit Vectors
Operations of interest: insert, search, delete, and predecessor.
The predecessor and successor operations are mirror images of
each other, so we only consider one of them.
Annoying convention. Let S ⊆ U be the set of keys in a
dictionary. For any x ∈ U, define
predecessor(x) = max{y ∈ S : y ≤ x}.
Consequently, if x ∈ S, then predecessor(x) = x.
In the event that predecessor(x) = x, we can find the next smallest
entry in S by calling predecessor(x −1).
6/24
Warm-up: Bit Vectors
Let S ⊆ U be the set of keys in the dictionary. A bit vector
representation of S is a sequence of bits B of length u such that
B = 1 iff i ∈ S.
i
Example. Let u = 8, and consider the set of keys
S = {0,1,5,6,7}. The corresponding bit vector is:
B 1 1 0 0 0 1 1 1
0 1 2 3 4 5 6 7
QUICK EXERCISE. What are the time complexities for each of
the operations of interest? How much memory space is required?
7/24
Warm-up: Bit Vectors
Answers
• Insert, search and delete all run in O(1) time.
• Predecessor, however, requires O(u) time.
• The bit vector uses Θ(u) bits, or Θ(u/log(u)) words.
Are these results any good? It depends on the relationship between
n and u.
• If u ∈ Θ(n), then we get comparable performance to a hash
table using strictly less space.
• However, if u is large compared to n, then this is no better
than a hash table, and possibly worse.
• The bit vector representation may not be practical for very
large u.
8/24
Bitwise Tries
A trie, or prefix tree, is a tree such that every node contains (or
represents) a sequence (e.g., strings, sequences of bits), and such
that the sequence in node x is the common prefix of the sequences
stored in all of the child nodes of x.
Conventions:
• The root node contains the empty sequence.
• The sequence in node x is exactly one character shorter than
the sequence in a child of x.
A bitwise trie is a trie that is a binary tree. Without loss of
generality, we can assume that the sequences stored by a bitwise
trie consist of 0’s and 1’s.
9/24
Bitwise Tries
Example. Let u = 8, and consider the set of keys
S = {0,1,5,6,7}.
Write each key using its 3-digit binary representation:
S = {000,001,101,110,111}.
The corresponding bitwise trie is:
0 1
00 10 11
000 001 101 110 111
10/24
Bitwise Tries
Comments
• A key in S is always located in a leaf of the trie. If |S| = n,
there are more than n nodes in the trie.
• The lowest common ancestor of any two nodes contains the
prefix common to those two sequences.
• The height of a nonempty trie is always log(u), independent
of n.
QUICK EXERCISE. How do insert(x), search(x) and delete(x)
work on a bitwise trie? What are their time complexities?
11/24
Bitwise Tries
Answer. Each of these algorithms is very similar to the
corresponding operation on a binary search tree. Minor differences:
insert(x) might add more than one node to a branch, and
delete(x) might remove more than one node from a branch.
Here are the nodes that are added to the example trie by calling
insert(011).
0 1
00 01 10 11
000 001 011 101 110 111
12/24
Bitwise Tries
And here are the nodes that are removed from the example trie by
calling delete(101).
0 1
00 01 10 11
000 001 011 101 110 111
In the worst case, each of these algorithms has to traverse the
height of the tree. Thus insert, search and delete run in O(log(u))
time.
13/24
