Introduction to Algorithms, Third Edition

Superimposing a tree of constant height
What happens if we superimpose a tree with greater degree? Let us assume that
the size of the universe is
u
D
2
2k
for some integer
k
, so that
p
u
is an integer.
Instead of superimposing a binary tree on top of the bit vector, we superimpose a
tree of degree
p
u
. Figure 20.2(a) shows such a tree for the same bit vector as in
Figure 20.1. The height of the resulting tree is always
2
.
As before, each internal node stores the logical-or of the bits within its sub-
tree, so that the
p
u
internal nodes at depth
1
summarize each group of
p
u
val-
ues. As Figure 20.2(b) demonstrates, we can think of these nodes as an array
summary
Œ0 : :
p
u
1
, where
summary
Œi 
contains a
1
if and only if the subar-
ray
AŒi
p
u : : .i
C
1/
p
u
1
contains a
1
. We call this
p
u
-bit subarray of
A
the
i
th
cluster
. For a given value of
x
, the bit
AŒx
appears in cluster num-
ber
b
x=
p
u
c
. Now I
NSERT
becomes an
O.1/
-time operation: to insert
x
, set
both
AŒx
and
summary
Œ
b
x=
p
u
c
to
1
. We can use the
summary
array to perform

---

20.1
Preliminary approaches
535
0
0
0
1
1
2
1
3
1
4
1
5
0
6
1
7
0
8
0
9
0
10
0
11
0
12
0
13
1
14
1
15
1
1
1
0
1
(a)
0
0
0
1
1
2
1
3
1
4
1
5
0
6
1
7
0
8
0
9
0
10
0
11
0
12
0
13
1
14
1
15
(b)
1
0
1
1
0
2
1
3
A
A
summary
p
u
bits
p
u
bits
Figure 20.2
(a)
A tree of degree
p
u
superimposed on top of the same bit vector as in Figure 20.1.
Each internal node stores the logical-or of the bits in its subtree.
(b)
A view of the same structure,
but with the internal nodes at depth
1
treated as an array
summary
Œ0 : :
p
u
1
, where
summary
Œi 
is
the logical-or of the subarray
AŒi
p
u : : .i
C
1/
p
u
1
.
each of the operations M
INIMUM
, M
AXIMUM
, S
UCCESSOR
, P
REDECESSOR
, and
D
ELETE
in
O.
p
u/
time:
To find the minimum (maximum) value, find the leftmost (rightmost) entry in
summary
that contains a
1
, say
summary
Œi 
, and then do a linear search within
the
i
th cluster for the leftmost (rightmost)
1
.
To find the successor (predecessor) of
x
, first search to the right (left) within its
cluster. If we find a
1
, that position gives the result. Otherwise, let
i
D b
x=
p
u
c
and search to the right (left) within the
summary
array from index
i
. The first
position that holds a
1
gives the index of a cluster. Search within that cluster
for the leftmost (rightmost)
1
. That position holds the successor (predecessor).
To delete the value
x
, let
i
D b
x=
p
u
c
. Set
AŒx
to
0
and then set
summary
Œi 
to the logical-or of the bits in the
i
th cluster.
In each of the above operations, we search through at most two clusters of
p
u
bits
plus the
summary
array, and so each operation takes
O.
p
u/
time.
At first glance, it seems as though we have made negative progress. Superimpos-
ing a binary tree gave us
O.
lg
u/
-time operations, which are asymptotically faster
than
O.
p
u/
time. Using a tree of degree
p
u
will turn out to be a key idea of van
Emde Boas trees, however. We continue down this path in the next section.