Succinct Binary Rank
Recall from Wednesday: we were able to equip a bit array with a
collection of lookup tables in such a way that the result is succinct,
and rank () can be implemented in O(1) time.
1
A succinct data structure that supports an O(1) implementation of
select () can be constructed using “similar” techniques (for a
1
generous definition of “similar”).
1/12
Application: Succinct Encoding of Binary Trees
Suppose we want to encode the structure (and not the contents)
of a binary tree with n nodes. How could we do so using a
sequence of bits?
A node can have two children, a left child only, a right child only,
or no children (4 options in total). We could encode each scenario
using a string of 2 bits, then list them in order row by row from
left to right.
2/12
Application: Succinct Encoding of Binary Trees
QUICK EXERCISE. The nodes below are numbered row by row
for reference.
0
1 2
3 4 5
6 7 8
Use the following representation:
11 = two child nodes 10 = left child only
01 = right child only 00 = leaf
Write down the binary number representing the structure of this
tree. Are any bits redundant?
3/12
Application: Succinct Encoding of Binary Trees
QUICK EXERCISE. The nodes below are numbered row by row
for reference.
0
1 2
3 4 5
6 7 8
Answer
The encoding scheme results in the sequence
11 11 01 11 00 10 00 00 00
Since the last node is always a leaf, we could remove the final 0.
4/12
Application: Succinct Encoding of Binary Trees
QUICK EXERCISE. The nodes below are numbered row by row
for reference.
0
1 2
3 4 5
6 7 8
1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Number the digits in the binary sequence as shown.
Where in the binary sequence is the 2-digit representation of node
i? How would you find the left child of i, the right child of i, and
the parent of i?
5/12
Application: Succinct Encoding of Binary Trees
Answer
Node i is represented by the two binary digits located at positions
2i and 2i +1.
Node i has a left child if and only if digit 2i is a 1. Assuming this
is the case, let L = rank (2i). The left child of node i is node L.
1
Similarly, node i has a right child if and only if digit 2i +1 is a 1.
Assuming this is the case, let R = rank (2i +1). The right child of
1
node i is node R.
Node i has a parent node if and only if i > 0. Assuming this is the
case, let P = select (i). The digit at position P is one of the digits
1
of the representation of the parent node. The parent is either node
number P if P is even, or P−1 if P is odd.
2 2
6/12
Application: Succinct Encoding of Binary Trees
Thus an O(1) implementation of the rank () and select ()
1 1
operations on a bit array can be used to navigate this
representation of a binary tree.
7/12
Application: Succinct Encoding of Binary Trees
We have represented the structure of a binary tree using 2n−1
bits. To determine whether this is compact, succinct, or implicit,
we need the information-theoretic lower bound.
Recall that there are 2k distinct binary sequences of length k.
A general principle is that if there are f(n) distinct objects of size
n, then representing one of those objects requires lg(f(n)) bits.
To assess how good our representation of a binary tree is, we need
to determine how many distinct binary trees of size n there are.
8/12
Application: Succinct Encoding of Binary Trees
QUICK EXERCISE. Considering the structure only, draw and
count all of the distinct binary trees of size (a) n = 1, (b) n = 2,
(c) n = 3.
Conjecture a way to calculate the number of distinct binary trees
of size n = 4 using the preceding results.
Let B be the number of distinct binary trees of size n. For
n
convenience, define B = 1 (there is one unique empty tree). State
0
a recurrence relation for B in terms of some or all of B ,...,B .
n 0 n−1
9/12
Application: Succinct Encoding of Binary Trees
Answer
There is 1 binary tree of size n = 1.
There are 2 binary trees of size n = 2.
There are 5 binary trees of size n = 3.
10/12
Application: Succinct Encoding of Binary Trees
To make a binary tree of size n = 4, we need a root node plus a
left and right subtree, where the sizes of the left and right subtrees
sum to 3. The possibilities are:
• left size = 0, right size = 3
• left size = 1, right size = 2
• left size = 2, right size = 1
• left size = 3, right size = 0
Based on the preceding numbers, and noting that there is 1 empty
tree, there are
1×5+1×2+2×1+5×1 = 14
trees of size 4.
11/12
Application: Succinct Encoding of Binary Trees
More generally, a binary tree of size n consists of a root node,
together with a left subtree and a right subtree whose sizes sum to
n−1. Consequently, B is defined by the recurrence relation
n
n−1
(cid:88)
B = B B , ∀n ≥ 1,
n i n−1−i
i=0
and B = 1.
0
Fun math fact. The above recurrence relation has the solution
(cid:18) (cid:19)
1 2n
B = , ∀n ≥ 0.
n
n+1 n
12/12
