Information Technology Reference
In-Depth Information
Fig. 10.4
The labels of consecutive leaves grow at most by 1
the root to some p
i
. Since the path from the root to p
1
contains at most
d
log n
eC
1
pages, we have
X
k
M
d
log n
eC
1
C
M.p
ii
;p
i
/:
(10.2)
iD2
We d e fi n e a
label
b for each leaf as follows. For any non-leaf page, q we label
the leftmost edge from q with 0 and all other edges with 1. Then the label b.p/ of a
leaf page p is the integer whose binary representation is the sequence of 0's and 1's
on the path from the root to p.
Clearly, b.p
i
/
b.p
i1
/
p
i
p
i1
for i
D
2;:::;k. This is because the labels
of consecutive leaves grow at most by 1; cf. Fig.
10.4
.
In order to operate with the label sequences, we need some results from the binary
arithmetic. For any nonnegative integer x, we denote by
v
.x/ the number of one bits
in the binary representation of x.
Lemma 10.11
Let
x
and
y
be nonnegative integers, and let
c
be the number of
carries when the binary representations of
x
and
y
are added. Then v
.x/
C
v
.y/
D
v
.x
C
y/
C
c
.
t
Lemma 10.12
Let
x
and
y
be nonnegative integers, such that
x<y
, and let
i
be
the number of bits to the right of and including the leftmost bit in which the binary
representations of
x
and
y
differ. Then
i
v
.x/
v
.y/
C
2
d
log.y
x
C
1/
e
:
Proof
Let c be the number of carries when x and y
x are added. By Lemma
10.11
,
v
.x/
C
v
.y
x/
D
v
.y/
C
c.Whenx and y
x are added, at least i
d
log.y
x
C
1/
e
carries are required to produce a number which differs from x in the i th bit. Thus,
i
d
log.y
x
C
1/
e
c, and we conclude that
