Binary Search Tree and 1-dimensional Random Packing

Yoshiaki Itoh

Institute of Statistical Mathematics, Tokyo, Japan

Algorithms Seminar

September 22, 1997

[summary by Hosam M. Mahmoud]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

This talk surveys some models of random trees underlying continuous partitioning processes:
  1. One-dimensional random sequential packing;
  2. Kakutani's interval splitting;
  3. The random sequential bisection model;
  4. The continuous binary search tree.

1   One-Dimensional Random Sequential Packing

The first model was introduced in [5]. In this model we place a unit interval I1 at a random position in the interval [0,x]. We assume that the initial point x1 of the interval I1 is Uniform-[0,x-1]. The interval (x1, x1+1) is removed and whichever among the remaining intervals [0,x1] and [x1+1, x] has length that permits further partitioning (i.e., greater than 1) is partitioned in a recursive fashion. The process continues as follows---if the intervals I1,I2,...,Ik have already been chosen, the next randomly chosen interval will be kept only if it does not intersect any of the intervals I1,I2,...,Ik. In this case this interval will be denoted by Ik+1. If it intersects any of the intervals I1,I2,...,Ik, we ignore it and choose a new interval. The procedure is continued until none of the lengths of gaps generated by the intervals placed in [0,x] is greater than 1.

A parameter of interest is the number of intervals packed in [0,x] by this procedure. We denote its mean value by M(x). We can now formulate a differential equation (with delay) for M(x). By conditioning on the initial point of the first interval and invoking its uniform distribution we obtain:
M(x+1)=
2
x
ó
õ
x


0
M(y)dy+1;
for brevity many obvious boundary conditions are omitted in this overview of the talk. We can obtain the limiting behavior of this mean value via the Laplace transform and the method of undetermined coefficients. It then follows from a Tauberian theorem that, as x®¥,
M(x)
x
® ó
õ
¥


0
exp æ
ç
ç
ç
ç
è		 -2 ó
õ
t


0
1-e-u
u
du ö
÷
÷
÷
÷
ø		   dt
 
·
=		 0.748.

Another parameter of interest is L(x), the minimal gap length generated by the random packing. Again by conditioning on the position of the leftmost end of the first interval packed [2], we obtain an integral equation
P ( L(x+1) ³ h ) =
1
x
ó
õ
x


0
P ( L(y) ³ h ) P ( L(x-y) ³ h )   dy.
A similar integral equation can be obtained for the maximal gap length.

2   A Unified Model for Kakutani's Interval Splitting and Rényi's Random Packing

Rényi's partitioning process has an interpretation as a parking problem: One can park a car of length 1, if there is a space of length at least 1.

In a more general setting, one may consider parking cars (or packing intervals) of length l, for a space of length at least 1. The expected number of cars is then
M(x+l) =
1
x
ó
õ
x


0
( M(y)+M(x-y)+1 )   dy.

Rényi's problem is the case l=1, whereas Kakutani considers the case l = 0. For this variation Komaki and Itoh [3] find the limiting behavior
 
lim
x ® ¥
M(x)
x
= ó
õ
¥


0
( 1+(1-l) ) e
-(1-l)t
 
exp æ
ç
ç
ç
ç
è		 -2 ó
õ
t


0
1-e
-l u
 
u
  du ö
÷
÷
÷
÷
ø		   dt.
For the probability distribution of the minimum of gaps, giving f(x) for 0 £ x £ 1, you get the functional form
f(x+l,h) =
1
x
ó
õ
x


0
f(x-y, h)f(y,h)  dy.

3   The Height of a Continuous-Type Binary Search Tree

Consider a random permutation of 1,2, ..., n, with all n! permutations equiprobable. Insert the elements of the permutation in a binary search tree. Let H(n) be the height of the tree so obtained. This height satisfies the equation
P ( H(n+1) £ h ) =
1
n
n
å
m=0
P ( H(n-m) £ h-1 ) P ( H(m) £ h-1 ) .
Note that the continuous analogue
P ( H (x+1) £ h ) =
1
x
ó
õ
x


0
P ( H(x-y) £ h-1 ) P ( H(y) £ h-1 ) dy
is of the type we obtained in the continuous models considered earlier. Robson [6], Flajolet and Odlyzko [1], Mahmoud and Pittel [4] have considered heights of similar discrete-type random trees.

4   Random Sequential Bisection Model

Applying the idea for the analysis of random packing, a continuous model is studied as a random sequential bisection model [7].

Among the possible 2d nodes at the d-th level, 1 £ d, of the associated tree the proportions of the expected number of the internal and external nodes are the Poisson-like expressions
1
x
¥
å
k=d
(log x)k
k!
,
and
1
x
(log x)d-1
(d-1)!
,
respectively.

Let Ni (x,d) and Ne (x,d) denote the numbers of the internal and external nodes at the d-th level respectively. Let mi (x,d) and me (x,d) denote their expected values respectively. Then
mi (x,d) =
1
x
ó
õ
x


0
( mi (x-y,d-1)+mi (y,d-1))  dy.
From this we have
mi (x,d) =
2d
x
¥
å
k=d
(log x)k
k!
,     for   1 £ x,
for d=0,1,2,....

In any binary tree Ni (x,d-1) internal nodes have 2Ni (x,d-1) son nodes, among which Ni (x,d) are internal, therefore Ne (x,d)=2 Ni (x,d-1)-Ni (x,d), for d=1,2,.... The expectation of this equality shows that for d=1,2,..., me (x,d)=2 mi (x,d-1)-mi (x,d). As x and d increase to infinity in such a way that d = c log x, we find
mi (x,d) =
1
(2 p d)1/2
e
-dg (c)
 
+O(1/d),
if c > 1. If c<1,
mi (x,d)= 2d -
1
(2 p d)1/2
e
-dg (c)
 
+O(1/d),
where g (c)= 1/c + log (c/2) - 1. It follows that
 
lim
x ® ¥
me (x,d)=
 
lim
x ® ¥
mi (x,d)=
ì
í
î
0,   for c^ £ c < ¥;
¥,   for 1 £ c < c^,
and, on the other hand,
 
lim
x ® ¥
me (x,d)=
 
lim
x ® ¥
{2d- mi (x,d)}=
ì
í
î
0,   for 0 £ c < c;
¥,   for c £ c < 1,
where c^=· 4.311 and c=· 0.3734 are the positive solutions of g (c)= 1/c +log (c/2) - 1=0.

References

[1]
Flajolet (P.) and Odlyzko (A.). -- The average height of binary trees and other simple trees. Journal of Computer and System Sciences, vol. 25, 1982, pp. 171--213.

[2]
Itoh (Yoshiaki). -- On the minimum of gaps generated by one-dimensional random packing. Journal of Applied Probability, vol. 17, n°1, 1980, pp. 134--144.

[3]
Komaki (Fumiyasu) and Itoh (Yoshiaki). -- A unified model for Kakutani's interval splitting and Rényi's random packing. Advances in Applied Probability, vol. 24, n°2, 1992, pp. 502--505.

[4]
Mahmoud (Hosam) and Pittel (Boris). -- On the most probable shape of a search tree grown from a random permutation. SIAM Journal on Algebraic and Discrete Methods, vol. 5, n°1, 1984, pp. 69--81.

[5]
Rényi (Alfréd). -- On a one-dimensional problem concerning random space filling. Magyar Tud. Akad. Mat. Kutató Int. Közl., vol. 3, n°1/2, 1958, pp. 109--127.

[6]
Robson (J. M.). -- The height of binary search trees. The Australian Computer Journal, vol. 11, n°4, 1979, pp. 151--153.

[7]
Sibuya (Masaaki) and Itoh (Yoshiaki). -- Random sequential bisection and its associated binary tree. Annals of the Institute of Statistical Mathematics, vol. 39, n°1, 1987, pp. 69--84.
This document was translated from LATEX by HEVEA.