AVERAGE CASE-ANALYSIS OF PRIORITY TREES: A STRUCTURE FOR PRIORITY QUEUE ADMINISTRATION

ALOIS PANHOLZER AND HELMUT PRODINGER

Abstract. Priority trees (p-trees) are a certain variety of binary trees of size n constructed from permutations of the numbers 1, …, n. In this paper we analyse several parameters depending on n (the size) and j (a number between 1 and n), such as the length of the left path (connecting the root and the leftmost leaf), the height of node j (= distance from the root), the number of left edges on the path from the root to the node j, the number of descendants of node j, the number of key comparisons when inserting an element between j and j + 1, the number of key comparisons when cutting the p-trees into two p-trees, the number of nodes with 0, 1 or 2 children. Methodologically, recursions are set up according to a fundamental decomposition of the family A of p-trees (using auxiliary quantities B and C); using generating functions, they lead to systems of differential equations that can be solved explicitly with some efforts. The quantities of interest can then be identified as coefficients in the explicit forms of the generating functions.

1. Introduction

Priority trees (or “p-trees” for short) are a data structure to implement priority queues. There exist applications of priority queues e. g. in operating systems like job scheduling or resource management and in discrete event simulation models. Each element in a priority queue has a fixed associated key value which determines its priority. The lower the key value of an element in the queue is, the higher is its priority. Such a queue must support the two basic operations of inserting an element with an arbitrary given priority (Insert) and of removing the element with the highest priority (Delete).

A p-tree is either empty or it consists of a sequence of nodes with non-increasing keys, the so called “left path,” such that to each node on the left path except the last one, there is associated a possibly empty p-tree, the “right subtree.” If z is a node on the left path with key l and x being its left successor with key k, then all nodes y_{i} of the right path associated with z have key values s_{i} ranked between k and l, or more precisely k ≤ s_{i} < l. The element with the smallest key value (i. e. with the highest priority) is the terminal node of the left path and is called the “left leaf.”

To insert a new element p into a p-tree T the following recursive algorithm Insert can be applied:

• If T is empty or the root of T has a key not greater than p, then let p be the new root and T its left subtree.

• Otherwise search down the left path of T for the first node x that has a key that is not greater than p.

This research was supported by the Austrian Research Society (FWF) under the project number P12599-MAT. Additional new results about priority trees may be found in [14].

Date: December 19, 1997.

step 0  ∅  (empty tree)
step 1  3  (insert element 3)
step 2  [figure: 1; 3]  (insert element 1)
step 3  [figure: 1; 3; 6]  (insert element 6)
step 4  [figure: 1; 3; 6; 4]  (insert element 4)
step 5  [figure: 1; 3; 6; 5; 4]  (insert element 5)
step 6  [figure: 1; 3; 6; 5; 4; 2]  (insert element 2)

Figure 1. Generation of a p-tree.

– If no such node exists, then append p to the left path as the new left leaf.

– Otherwise denote the predecessor of x by z, so that the key of p is ranked between the keys of x and z. In this case the algorithm Insert (of node p) will be applied recursively to the right subtree of z.

As an example how the algorithm Insert works we show in Figure 1 the generation of the p-tree from the permutation 3 1 6 4 5 2.

2. The mathematical methods

For the mathematical analysis of this data structure we consider the model that all n! permutations of the numbers 1, …, n generating a p-tree of size n are equally likely.

We will not decompose the p-tree into the left path and the right subtrees and treat the components separately as it was done in [10], but rather work with 3 families of combinatorial objects A, B and C. The family A are the ordinary p-trees, that are generated from random permutations by starting with the empty tree, the family B are p-trees that are generated by starting with one additional element “+∞” and the family C are p-trees that are generated by starting with the extra element “−∞.”

For the following we assume that these additional elements are not counted for the size of an object, which means that the size of an object is the number of nodes, without the elements −∞ and +∞. Again all n! permutations from 1 to n are assumed to be equally likely to generate an object of size n from the families A, B and C.

For the forthcoming analysis the following decompositions of the families A, B and C w. r. t. the first element k of a random permutation of the numbers from 1, 2, ⋯, n are essential as is shown in Figures 2, 3 and 4.

The parameters of the p-trees that we are going to analyse in this paper satisfy recursions which are consequences of the decompositions of the families A, B and C. Using generating functions, these recurrences translate into a system of differential equations. Although in

AVERAGE CASE-ANALYSIS OF PRIORITY TREES 3

[figure] k

object of C with nodes k+1, …, n

object of B with nodes 1, …, k−1

Figure 2. Decomposition of the family A

[figure]

[figure] +∞

k

object of B with nodes 1, …, k−1

object of A with nodes k+1, …, n

Figure 3. Decomposition of the family B

[figure]

[figure] k

−∞

object of C with nodes k+1, …, n

object of A with nodes 1, …, k−1

Figure 4. Decomposition of the family C

most cases these differential equations for the distributions seem to be not tractable, we can at least compute the expectations for the considered parameters. Here is an example

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11]

Figure 5. A p-tree constructed from the permutation 8 11 9 3 4 1 7 10 6 2 5. The lenght of the left path is 4, the height of node 7 is 3, the number of descendants of node 7 is 4, the number of left edges leading to node 4 is 2, the number of nodes with 0,1,2 successors is 5,2, 4. The number of comparisons to insert a node 8.5 is 4.

3. The length of the left path

In order to use the p-trees as a data structure for priority queue administration it is necessary to be able to remove on demand the element with the highest priority (i. e. with the smallest key) from the queue. In a p-tree this element, is the leaf of the left path starting at the root.

In the following we consider the distributions of the height of the element with highest priority in p-trees. Therefore we have to consider the distributions of the length of the left paths in in the families A, B and C. That means, we have to count the number of nodes on the direct path from the root to the left leaf. To obtain easier recurrences it is advantageous to count the element +∞ for the length of the left path in the family B but not the element −∞ in the family C.

Decomposing the families A, B and C according to the first element k of a random permutation with n elements as described above, we obtain the following recurrences for the probabilities A_{n,m}, B_{n,m} and C_{n,m}, that an object of these families with size n has a left path of length m:

A_{n,m} = \frac{1}{n} ∑_{k=1}^{n} ∑_{i=0}^{m} C_{n−k,i} B_{k−1,m−i} for n ≥ 1 ,  (1a)

B_{n,m} = \frac{1}{n} ∑_{k=1}^{n} B_{k−1,m−1} for n ≥ 1 ,  (1b)

C_{n,m} = \frac{1}{n} ∑_{k=1}^{n} C_{n−k,m−1} for n ≥ 1 ,  (1c)
A_{0,m} = δ_{0,m} , B_{0,m} = δ_{1,m} , and C_{0,m} = δ_{0,m} .  (1d)

With the bivariate generating functions

A(z, v) = ∑_{n≥0} ∑_{m≥0} A_{n,m}z^{n}v^{m}, B(z, v) = ∑_{n≥0} ∑_{m≥0} B_{n,m}z^{n}v^{m}, and C(z, v) = ∑_{n≥0} ∑_{m≥0} C_{n,m}z^{n}v^{m}

we get from (1) by multiplying with nz^{n−1}v^{m} and summing up over all m ≥ 0 and n ≥ 1 the following system of differential equations

\frac{∂}{∂z} A(z, v) = B(z, v) C(z, v) ,  (2a)
\frac{∂}{∂z} B(z, v) = \frac{v}{1 − z} B(z, v) ,  (2b)
\frac{∂}{∂z} C(z, v) = \frac{v}{1 − z} C(z, v) ,  (2c)

with initial values A(0, v) = 1, B(0, v) = v, and C(0, v) = 1.

From (2b) we obtain

\frac{d (B(z, v))}{B(z, v)} = d (log B(z, v)) = \frac{v}{1 − z} dz ,  (3)

which leads through integration and adjusting to the initial values to the solution

B(z, v) = \frac{v}{(1 − z)^{v}} .  (4)

Analogously we get from (2c) for C(z, v) the solution

C(z, v) = \frac{1}{(1 − z)^{v}} .  (5)

With (2a) these expressions for B(z, v) and C(z, v) lead to the following equations for A(z, v)

\frac{∂}{∂z} A(z, v) = \frac{v}{(1 − z)^{2v}} ,  (6)

from which we get by integration the solution

A(z, v) = \frac{1}{1 − 2v} (1 − v − \frac{v}{(1 − z)^{2v−1}} ) .  (7)

In the following we denote the signless Stirling numbers of the first kind by \left[{n \atop m}\right]. They are given by the relation (see e. g. [4])

∑_{n≥0} ∑_{m=0}^{n} \left[{n \atop m}\right]\frac{z^{n}}{n!} v^{m} = \frac{1}{(1 − z)^{v}} .  (8)

With this equation the coefficients of B(z, v) and C(z, v) are obtained immediately whereas for the coefficients of A(z, v) we get

\begin{aligned}A_{n,m} & = \frac{1}{n}[z^{n−1}v^{m}]\frac{∂}{∂z} A(z, v) = \frac{1}{n}[z^{n−1}v^{m}]\frac{v}{(1 − z)^{2v}} \\ & = \frac{2^{m−1}}{n} [z^{n−1}v^{m−1}]\frac{1}{(1 − z)^{v}} = \frac{2^{m−1}\left[{n−1 \atop m−1}\right]}{n!} . \end{aligned}

This leads to the following

Theorem 3.1. The probabilities A_{n,m}, B_{n,m} and C_{n,m} of the length of the left paths in objects of the families A, B and C of size n, i. e. the probabilities, that an object of size n has a left path length m, are given by

A_{n,m} = \frac{2^{m−1}\left[{n−1 \atop m−1}\right]}{n!} for n ≥ 1 ,  (9a)
B_{n,m} = \frac{\left[{n \atop m−1}\right]}{n!} for n ≥ 1 ,  (9b)
C_{n,m} = \frac{\left[{n \atop m}\right]}{n!} for n ≥ 1 .  (9c)

To get the expectations A_{n}, B_{n} and C_{n} of the length of the left paths in objects of size n in the families A, B and C we define

A(z) = \frac{∂}{∂v} A(z, v)|_{v=1} , B(z) = \frac{∂}{∂v} B(z, v)|_{v=1} and C(z) = \frac{∂}{∂v} C(z, v)|_{v=1} .  (10)

Then these expectations are given by A_{n} = [z^{n}]A(z), B_{n} = [z^{n}]B(z) and C_{n} = [z^{n}]C(z).

Differentiating the equations (4), (5) and (6) with respect to v and evaluating at v = 1 leads to

\frac{∂}{∂z} A(z) = \frac{∂}{∂v} (\frac{∂}{∂z} A(z, v))|_{v=1} = \frac{2}{(1 − z)^{2}} log (\frac{1}{1 − z} ) + \frac{1}{(1 − z)^{2}} ,  (11a)

B(z) = \frac{∂}{∂v} B(z, v)|_{v=1} = \frac{1}{1 − z} + \frac{1}{1 − z} log (\frac{1}{1 − z} ) ,  (11b)

C(z) = \frac{∂}{∂v} C(z, v)|_{v=1} = \frac{1}{1 − z} log (\frac{1}{1 − z} ) .  (11c)

To extract the coefficients of such expressions we need the formulas (see [9])

[z^{n}] \frac{1}{(1 − z)^{α+1}} log (\frac{1}{1 − z} ) = (H_{n+α} − H_{α}) \binom{n + α}{n} ,  (12a)
[z^{n}] \frac{1}{(1 − z)^{α+1}} log^{2} (\frac{1}{1 − z} ) = ((H_{n+α} − H_{α})^{2} − (H_{n+α}^{(2)} − H_{α}^{(2)})) \binom{n + α}{n} ,  (12b)

where H_{n} = ∑_{k=1}^{n} \frac{1}{k} respectively H_{n}^{(m)} = ∑_{k=1}^{n} \frac{1}{k^{m}} denote the harmonic numbers.

Then with (12a) we obtain from (11)

Theorem 3.2. The expectations A_{n}, B_{n} and C_{n} for the lengths of the left paths in objects of size n in the families A, B and C are given by

A_{n} = 2H_{n} − 1 for n ≥ 1 , A_{0} = 0 ,  (13a)
B_{n} = H_{n} + 1 for n ≥ 1 , B_{0} = 1 ,  (13b)
C_{n} = H_{n} for n ≥ 1 , C_{0} = 0 .  (13c)

In the following we denote by Ă_{n} the second factorial moment of the length of the left path in p-trees of size n. Furthermore we define Ă(z) = \frac{∂^{2}}{∂v^{2}} A(z, v)|_{v=1}. Then the auxiliary quantity

Ă_{n} is given by Ă_{n} = [z^{n}]Ă(z).

Differentiating (6) two times with respect to v and evaluating at v = 1 leads to

\frac{∂}{∂z} Ă(z) = \frac{4}{(1 − z)^{2}} log^{2} (\frac{1}{1 − z} ) + \frac{4}{(1 − z)^{2}} log (\frac{1}{1 − z} ) .  (14)

With (12) we get the coefficients Ă_{n} and so we have

Lemma 3.3. The second factorial moment Ă_{n} of the length of the left path in p-trees of size n is given by

Ă_{n} = 4H_{n}^{2} − 4H_{n} − 4H_{n}^{(2)} + 4 for n ≥ 1 , Ă_{0} = 0 .  (15)

The variance Â_{n} of the length of the left path in p-trees of size n is given by the relation

Â_{n} = Ă_{n} + A_{n} − A_{n}^{2}

and therefore we get

Theorem 3.4. The variance Â_{n} of the length of the left path in p-trees of size n is given by

Â_{n} = 2H_{n} − 4H_{n}^{(2)} + 2 for n ≥ 1 , Â_{0} = 0 .  (16)

The asymptotic behaviour of the lengths of the left paths in p-trees is described in the following theorem.

Theorem 3.5. The sequence of random variables

Ω_{n}^{∗} = \frac{Ω_{n} − μ_{n}}{σ_{n}}

converges weakly to the standard normal (Gaussian) distribution. Here the random variables Ω_{n} denote the distributions of the lengths of the left paths in p-trees of size n with expectation μ_{n} and variance σ_{n}^{2}. That means we have

ℙ (a < Ω_{n}^{∗} < b) → \frac{1}{\sqrt{2π}} ∫_{a}^{b} e^{− \frac{t^{2}}{2}} dt  (17)

and further

μ_{n} = 2 log n + O(1) and σ_{n}^{2} = 2 log n + O(1)

for n → ∞.

Proof. With the asymptotic expansions of the harmonic numbers

H_{n} = log n + γ + \frac{1}{2n} − \frac{1}{12n^{2}} + O (\frac{1}{n^{4}} ) ,  (18a)
H_{n}^{(2)} = \frac{π^{2}}{6} − \frac{1}{n} + \frac{1}{2n^{2}} + O (\frac{1}{n^{3}} )  (18b)

we get from the exact formulas (13a) and (16) immediately

μ_{n} = A_{n} = 2 log n + O(1) and σ_{n}^{2} = Â_{n} = 2 log n + O(1) .

To prove the theorem we use a method that is described in [6]. We start with the sequence of the characteristic functions ϕ_{Ω_{n}^{∗}}(t) = 𝔼(e^{iΩ_{n}^{∗}t}) of the Ω_{n}^{∗} and show, that this sequence

converges pointwise to the characteristic function e^{− \frac{t^{2}}{2}} of the standard normal distribution. In other words, we show, that

ϕ_{Ω_{n}^{∗}}(t) → e^{− \frac{t^{2}}{2}}  (19)

for every t ∈ ℝ and n → ∞. By the continuity theorem for characteristic functions of Paul Lévy (see e. g. [3]), we can then deduce from (19) the weak convergence of the distribution functions (17).

From the bivariate generating function A(z, v) of the probabilities A_{n,m}, that the length of the left path in a p-tree of size n is equal m as given by (7), we obtain with

A_{n}(v) = [z^{n}]A(z, v)

the probability generating function of the Ω_{n}. First we obtain

A_{n}(v) = \frac{1}{n}[z^{n−1}]\frac{∂}{∂z} A(z, v) = \frac{1}{n}[z^{n−1}]\frac{v}{(1 − z)^{2v}} = \frac{v}{2v − 1}\binom{n + 2v − 2}{n} .

With the asymptotic expansion for fixed α

\binom{n + α}{n} = \frac{(n + α) · (n + α − 1) ⋯ (n + 1)}{Γ(α + 1)} = \frac{n^{α}}{Γ(α + 1)} · (1 + O (\frac{1}{n})) ,

we get

A_{n}(v) = \frac{v}{2v − 1}\binom{n + 2v − 2}{n} = \frac{v n^{2v−2}}{Γ(2v)} · (1 + O (\frac{1}{n}))  (20)

for fixed v and n → ∞.

For the characteristic functions ϕ_{Ω_{n}^{∗}}(t) of the Ω_{n}^{∗} we have then

ϕ_{Ω_{n}^{∗}}(t) = 𝔼(e^{iΩ_{n}^{∗}t}) = ∑_{m} ℙ(Ω_{n}^{∗} = m) · e^{imt} = ∑_{m} ℙ(Ω_{n} = μ_{n} + σ_{n}m) · e^{imt}

= ∑_{m≥0} ℙ(Ω_{n} = m) · e^{it \frac{m−μn}{σn}} = ∑_{m≥0} A_{n,m}e^{it \frac{m−μn}{σn}} = e^{− \frac{iμnt}{σn}} A_{n}(e^{\frac{it}{σn}}) .

With (20) we get the expansion

A_{n}(e^{\frac{it}{σn}}) = \frac{e^{i \frac{t}{σn}}}{Γ(2e^{i \frac{t}{σn}})} exp (2 log n(e^{i \frac{t}{σn}} − 1)) · (1 + O (\frac{1}{n}))

= exp (2 log n(e^{i \frac{t}{σn}} − 1)) · (1 + o(1)) = exp (2 log n\frac{it}{σ_{n}} − \frac{t^{2}}{2σ_{n}^{2}} ) · (1 + o(1))

= exp (2 log n\frac{it}{σ_{n}} − \frac{t^{2}}{2} ) · (1 + o(1)) .

This leads to

ϕ_{Ω_{n}^{∗}}(t) = e^{− \frac{iμnt}{σn}} A_{n}(e^{\frac{it}{σn}}) = exp (−2 log n\frac{it}{σ_{n}} ) exp (2 log n\frac{it}{σ_{n}} − \frac{t^{2}}{2} ) · (1 + o(1))

= e^{− \frac{t^{2}}{2}} · (1 + o(1)) → e^{− \frac{t^{2}}{2}}

for a fixed t and n → ∞. With the continuity theorem of Lévy the theorem is completely proved.

4. The height of the nodes

In the following we consider the distributions of the height of the nodes with key j of objects of size n in the families A, B and C. To be precise, we say that the height of a node j is the number of nodes between the root and the node j.

With A_{n,j,m}, B_{n,j,m} and C_{n,j,m} we denote the probabilities, that the node with key j in an corresponding object of size n has height m. To get a recurrence for these quantities, we use the already treated distribution of the length of the left path in objects of the family C. To avoid confusion, from now on the probability, that the length of the left path in an object of size n in the family C is equal m, is denoted by p_{n,m}. With (5) and (9c) we have for p_{n,m}, respectively its generating function p(z, v) = ∑_{n≥0} ∑_{m≥0} p_{n,m}z^{n}v^{m},

p_{n,m} = \frac{\left[{n \atop m}\right]}{n!} and p(z, v) = \frac{1}{(1 − z)^{v}} .  (21)

With these remarks we get by means of decomposing the families A, B and C according to the first element k of a random permutation following recurrences for 1 ≤ j ≤ n

A_{n,j,m} = \frac{1}{n} (∑_{k=1}^{j−1} C_{n−k,j−k,m} + p_{n−j,m−1} + ∑_{k=j+1}^{n} ∑_{i=0}^{m} p_{n−k,i} B_{k−1,j,m−i}) ,  (22a)

B_{n,j,m} = \frac{1}{n} (∑_{k=1}^{j−1} A_{n−k,j−k,m−1} + δ_{m,2} + ∑_{k=j+1}^{n} B_{k−1,j,m−1}) ,  (22b)

C_{n,j,m} = \frac{1}{n} (∑_{k=1}^{j−1} C_{n−k,j−k,m} + p_{n−j,m−1} + ∑_{k=j+1}^{n} ∑_{i=0}^{m−1} p_{n−k,i} A_{k−1,j,m−1−i}) .  (22c)

Introducing the trivariate generating functions

A(z, u, v) = ∑_{j≥1} ∑_{n≥j} ∑_{m≥0} A_{n,j,m}z^{n}u^{j}v^{m} , B(z, u, v) = ∑_{j≥1} ∑_{n≥j} ∑_{m≥0} B_{n,j,m}z^{n}u^{j}v^{m} and
C(z, u, v) = ∑_{j≥1} ∑_{n≥j} ∑_{m≥0} C_{n,j,m}z^{n}u^{j}v^{m} ,

we get from (22) by multiplying with nz^{n−1}u^{j}v^{m} and summing up over all n ≥ j ≥ 1 and m ≥ 0 the following system of linear differential equations

\frac{∂}{∂z} A(z, u, v) = \frac{u}{1 − uz} C(z, u, v) + \frac{vu}{1 − uz} p(z, v) + p(z, v) B(z, u, v) ,  (23a)
\frac{∂}{∂z} B(z, u, v) = \frac{vu}{1 − uz} A(z, u, v) + \frac{v^{2}u}{(1 − z)(1 − uz)} + \frac{v}{1 − z} B(z, u, v) ,  (23b)

\frac{∂}{∂z} C(z, u, v) = \frac{u}{1 − uz} C(z, u, v) + \frac{vu}{1 − uz} p(z, v) + v p(z, v) A(z, u, v) .  (23c)

This system of differential equations seems to be not tractable, but it is helpful to get factorial moments of the distribution of the height of nodes in p-trees, in particular the expectation.

Then the ordinary generating functions

A(z, u) = ∑_{n≥1} ∑_{j=1}^{n} A_{n,j}z^{n}u^{j} , B(z, u) = ∑_{n≥1} ∑_{j=1}^{n} B_{n,j}z^{n}u^{j} , C(z, u) = ∑_{n≥1} ∑_{j=1}^{n} C_{n,j}z^{n}u^{j}

of the expectations A_{n,j}, B_{n,j} and C_{n,j} of the heights of the node j in objects of size n in the families A, B and C fulfill the relations

A(z, u) = \frac{∂}{∂v} A(z, u, v)|_{v=1} , B(z, u) = \frac{∂}{∂v} B(z, u, v)|_{v=1} , C(z, u) = \frac{∂}{∂v} C(z, u, v)|_{v=1} .

Differentiating (23) with respect to v and evaluating at v = 1 leads to the following system of linear differential equation for A(z, u), B(z, u) and C(z, u)

\frac{∂}{∂z} A(z, u) = \frac{u}{1 − uz} C(z, u) + \frac{1}{1 − z} B(z, u) + f_{1}(z, u) ,  (24a)
\frac{∂}{∂z} B(z, u) = \frac{u}{1 − uz} A(z, u) + \frac{1}{1 − z} B(z, u) + f_{2}(z, u) ,  (24b)
\frac{∂}{∂z} C(z, u) = \frac{u}{1 − uz} C(z, u) + \frac{1}{1 − z} A(z, u) + f_{3}(z, u)  (24c)

with

f_{1}(z, u) = \frac{u}{(1 − z)(1 − uz)} + \frac{u}{(1 − z)(1 − uz)} log (\frac{1}{1 − z} )

+ \frac{uz}{(1 − z)^{2}(1 − uz)} log (\frac{1}{1 − z} ) ,

f_{2}(z, u) = \frac{u^{2}z}{(1 − z)(1 − uz)^{2}} + \frac{2u}{(1 − z)(1 − uz)} + \frac{uz}{(1 − z)^{2}(1 − uz)} ,
f_{3}(z, u) = \frac{u}{(1 − z)(1 − uz)} + \frac{u}{(1 − z)(1 − uz)} log (\frac{1}{1 − z} ) + \frac{uz}{(1 − z)^{2}(1 − uz)}

+ \frac{uz}{(1 − z)^{2}(1 − uz)} log (\frac{1}{1 − z} ) .

In the following this system of differential equations will be converted to a single differential equation for A(z, u). To do this, we introduce two functions B̃(z, u) and C̃(z, u) which are given by the relations B(z, u) = \frac{B̃(z,u)}{1−z} and C(z, u) = \frac{C̃(z,u)}{1−uz}.

Then we get from (24)

\frac{∂}{∂z} A(z, u) = \frac{u}{(1 − uz)^{2}} C̃(z, u) + \frac{1}{(1 − z)^{2}} B̃(z, u) + f_{1}(z, u) ,  (25a)

\frac{1}{1 − z} \frac{∂}{∂z} B̃(z, u) = \frac{u}{1 − uz} A(z, u) + f_{2}(z, u) ,  (25b)
\frac{1}{1 − uz} \frac{∂}{∂z} C̃(z, u) = \frac{1}{1 − z} A(z, u) + f_{3}(z, u) .  (25c)

To eliminate B̃(z, u), we extract it from (25a), differentiate with respect to z and multiply by \frac{1}{1−z}. This leads to

B̃(z, u) = (1 − z)^{2} \frac{∂}{∂z} A(z, u) − \frac{u(1 − z)^{2}}{(1 − uz)^{2}} C̃(z, u) − (1 − z)^{2}f_{1}(z, u) ,  (26a)
\frac{1}{1 − z} \frac{∂}{∂z} B̃(z, u) = −2\frac{∂}{∂z} A(z, u) + (1 − z)\frac{∂^{2}}{∂z^{2}} A(z, u) − \frac{u(1 − z)}{(1 − uz)^{2}} \frac{∂}{∂z} C̃(z, u)
− \frac{2u(u − 1)}{(1 − uz)^{3}} C̃(z, u) − \frac{1}{1 − z} \frac{∂}{∂z} ((1 − z)^{2}f_{1}(z, u)) .  (26b)

Inserting (26b) in (25) leads to the following system of differential equations for A(z, u) and C̃(z, u)

\begin{matrix}\frac{u}{1 − uz} A(z, u) + 2\frac{∂}{∂z} A(z, u) − (1 − z)\frac{∂^{2}}{∂z^{2}} A(z, u) + \frac{u(1 − z)}{(1 − uz)^{2}} \frac{∂}{∂z} C̃(z, u) \\ + \frac{2u(u − 1)}{(1 − uz)^{3}} C̃(z, u) = −f_{2}(z, u) − \frac{1}{1 − z} \frac{∂}{∂z} ((1 − z)^{2}f_{1}(z, u)) , \end{matrix}  (27a)

\frac{1}{1 − uz} \frac{∂}{∂z} C̃(z, u) = \frac{1}{1 − z} A(z, u) + f_{3}(z, u) .  (27b)

To eliminate also C̃(z, u), we insert equation (27b) in (27a) and solve for C̃(z, u). This leads to

C̃(z, u) = − \frac{(1 − uz)^{2}}{u − 1} A(z, u) − \frac{(1 − uz)^{3}}{u(u − 1)} \frac{∂}{∂z} A(z, u) + \frac{(1 − z)(1 − uz)^{3}}{2u(u − 1)} \frac{∂^{2}}{∂z^{2}} A(z, u)
− \frac{(1 − uz)^{3}}{2u(u − 1)}f_{2}(z, u) − \frac{(1 − uz)^{3}}{2u(u − 1)(1 − z)} \frac{∂}{∂z} ((1 − z)^{2}f_{1}(z, u))  (28)

− \frac{(1 − uz)^{2}(1 − z)}{2(u − 1)}f_{3}(z, u) .

Differentiating this equation with respect to z and multiplying by \frac{1}{1−uz} gives a differential equation for A(z, u) after insertion in (27a).

\begin{matrix}\frac{2uz − u − 1}{(1 − z)(1 − u)}A(z, u) − 2\frac{1 − uz}{1 − u} \frac{∂}{∂z} A(z, u) − \\ − \frac{3}{2} \frac{(1 − uz)(2uz − u − 1)}{u(1 − u)} \frac{∂^{2}}{∂z^{2}} A(z, u) − \frac{1}{2} \frac{(1 − uz)^{2}(1 − z)}{u(1 − u)} \frac{∂^{3}}{∂z^{3}} A(z, u) \\ = f_{3}(z, u) + \frac{1}{1 − uz} \frac{∂}{∂z} [\frac{(1 − uz)^{3}}{2u(u − 1)}f_{2}(z, u)+ \\ + \frac{(1 − uz)^{3}}{2u(u − 1)(1 − z)} \frac{∂}{∂z} ((1 − z)^{2}f_{1}(z, u)) + \frac{(1 − uz)^{2}(1 − z)}{2(u − 1)}f_{3}(z, u)] . \end{matrix} (29)

Resubstituting f_{1}(z, u), f_{2}(z, u) and f_{3}(z, u) and taking the initial values A_{0,0} = 0, A_{1,1} = 1, A_{2,1} = 2 and A_{2,2} = 1 into account leads to the following linear differential equation of order 3 for A(z, u) with the given initial conditions:

\begin{matrix}\frac{2uz − u − 1}{(1 − z)(1 − u)}A(z, u) − 2\frac{1 − uz}{1 − u} \frac{∂}{∂z} A(z, u) − \frac{3}{2} \frac{(1 − uz)(2uz − u − 1)}{u(1 − u)} \frac{∂^{2}}{∂z^{2}} A(z, u) \\ − \frac{1}{2} \frac{(1 − uz)^{2}(1 − z)}{u(1 − u)} \frac{∂^{3}}{∂z^{3}} A(z, u) = \frac{uz + u − 2}{(1 − z)^{3}(1 − u)} , \\ A(0, u) = 0 , \frac{∂}{∂z} A(z, u)|_{z=0} = u , \frac{∂^{2}}{∂z^{2}} A(z, u)|_{z=0} = 2 (2u + u^{2}) . \end{matrix} (30)

Now we have to find 3 linearly independent solutions of the corresponding homogeneous differential equation

\begin{matrix}\frac{2uz − u − 1}{(1 − z)(1 − u)}A_{h}(z, u) − 2\frac{1 − uz}{1 − u} \frac{∂}{∂z} A_{h}(z, u) − \\ − \frac{3}{2} \frac{(1 − uz)(2uz − u − 1)}{u(1 − u)} \frac{∂^{2}}{∂z^{2}} A_{h}(z, u) − \frac{1}{2} \frac{(1 − uz)^{2}(1 − z)}{u(1 − u)} \frac{∂^{3}}{∂z^{3}} A_{h}(z, u) = 0 , \end{matrix}  (31)

then we can apply the variation of the parameter method [11] in order to solve (30).

From the homogeneous system of linear differential equations corrresponding to system (24)

\frac{∂}{∂z} A_{h}(z, u) = \frac{u}{1 − uz} C_{h}(z, u) + \frac{1}{1 − z} B_{h}(z, u) ,  (32a)
\frac{∂}{∂z} B_{h}(z, u) = \frac{u}{1 − uz} A_{h}(z, u) + \frac{1}{1 − z} B_{h}(z, u) ,  (32b)
\frac{∂}{∂z} C_{h}(z, u) = \frac{u}{1 − uz} C_{h}(z, u) + \frac{1}{1 − z} A_{h}(z, u)  (32c)

it is easy to see that there exists a one dimensional solution space with A_{h}(z, u) = B_{h}(z, u) = C_{h}(z, u). The corresponding differential equation

\frac{∂}{∂z} A_{h}(z, u) = \frac{u}{1 − uz} A_{h}(z, u) + \frac{1}{1 − z} A_{h}(z, u)  (33)

has the solution

A_{h}(z, u) = \frac{k_{1}(u)}{(1 − z)(1 − uz)} .  (34)

To reduce the order of the differential equation (31), we substitute

A(z, u) = \frac{E(z, u)}{(1 − z)(1 − uz)} and F (z, u) = \frac{∂}{∂z} E(z, u)

with functions E(z, u) and F (z, u) (method of d’Alembert [11]). This leads to the linear differential equation of order 2

\frac{1}{(1 − z)(1 − u)}F (z, u) − \frac{1}{2} \frac{1 − uz}{(1 − u)u} \frac{∂^{2}}{∂z^{2}} F (z, u) = 0 .  (35)

Using the substitution z = 1+ \frac{1−u}{u}t and the notation F̃(t, u) = F (1+ \frac{1−u}{u}t, u), the differential equation (12) transforms into the hypergeometric equation

t(1 − t)\frac{∂^{2}}{∂t^{2}} F (t, u) + 2F (t, u) = 0 .  (36)

Now we recall [2], that for all c ≠ 1, 2, ⋯ a one dimensional solution space of the hypergeometric differential equation

t(1 − t)f′′(t) + (c − (1 + a + b)t)f′(t) − abf(t) = 0  (37)

is in a neighborhood of t = 0 given by

k(t)t^{1−c} _{2}F_{1}( {a − c + 1, b − c + 1 \atop 2 − c}| t) ,  (38)

where _{2}F_{1} denotes a hypergeometric function [8].

In our instance the parameters are c = 0, a = −2 and b = 1, thus the above hypergeometric function degenerates to a polynomial, and we get one solution of (36) as

F̃(t, u) = t − t^{2} .  (39)

Resubstituting leads to a one dimensional solution space

F (z, u) = k_{2}(u)(1 − z)(1 − uz)  (40)

of (35).

Introducing new functions G(z, u) and H(z, u) by

F (z, u) = (1 − z)(1 − uz)G(z, u) and H(z, u) = \frac{∂}{∂z} G(z, u) ,  (41)

we get from (35) a linear differential equation of order one:

−\frac{(2uz − u − 1)(1 − uz)}{(1 − u)u}H(z, u) − \frac{1}{2} \frac{(1 − z)(1 − uz)^{2}}{(1 − u)u} \frac{∂}{∂z} H(z, u) = 0 .  (42)

This equation has the solution

H(z, u) = \frac{k_{3}(u)}{(1 − z)^{2}(1 − uz)^{2}} ,  (43)

with a function k_{3}(u), depending only on u.

Adding the three linearly independent solutions (34), (40) and (43) we get by resubstituting the complete solution of the homogeneous differential equation (31)

\begin{aligned}A_{h}(z, u) & = \frac{c_{1}(u)}{(1 − z)(1 − uz)} + \frac{c_{3}(u)}{(1 − z)(1 − uz)} ∫_{0}^{z}(1 − t)(1 − ut)dt \\ & + \frac{c_{3}(u)}{(1 − z)(1 − uz)} ∫_{0}^{z} [(1 − x)(1 − ux) ∫_{0}^{x} \frac{1}{(1 − t)^{2}(1 − ut)^{2}} dt] dx \end{aligned}  (44)

or, integrated,

\begin{aligned}A_{h}(z, u) & = \frac{c_{1}(u)}{(1 − z)(1 − uz)} + c_{2}(u)\frac{z(6 − 3uz − 3z + 2uz^{2})}{(1 − z)(1 − uz)} \\ & + c_{3}(u) [ − \frac{6(1 − uz)(2uz − 3u + 1)}{1 − z} log (\frac{1}{1 − uz} ) \\ & + \frac{6(1 − z)(2uz − 3 + u)u^{2}}{1 − uz} log (\frac{1}{1 − z} ) \\ & − \frac{(u − 1)(12u^{2}z^{2} − 12u(u + 1)z − 5u^{2} + 4u − 5)}{(1 − z)(1 − uz)}] . \end{aligned}  (45)

Now the variation of the parameter method leads after insertion of the initial conditions to the following solution of the generating function A(z, u) of the expectations of the height of node j in a p-tree of size n:

A(z, u) = \frac{1}{3}(2u^{2}z − u^{2} − u) ∫_{0}^{z} \frac{1}{(1 − t)^{2}(1 − ut)^{2}} log (\frac{1}{1 − t}) dt

+ \frac{1}{3} \frac{(1 − u)^{2}}{1 − z} ∫_{0}^{z} \frac{1}{(1 − t)^{2}(1 − ut)^{2}} log (\frac{1}{1 − t}) dt

+ \frac{1}{3} \frac{u}{(1 − z)(1 − uz)} log^{2} (\frac{1}{1 − z} )

+ \frac{1}{3} \frac{u(2u^{2}z − u^{2} + 2uz − 2u + 1)}{(1 − u)^{3}} log (\frac{1}{1 − z} )

+ \frac{7}{3} \frac{u}{(1 − u)(1 − z)} log (\frac{1}{1 − z} ) − \frac{1}{3} \frac{1}{(1 − z)^{2}} log (\frac{1}{1 − z} )

− \frac{1}{3} \frac{(6u − 1)u}{(1 − u)(1 − uz)} log (\frac{1}{1 − z} )

− \frac{1}{3} \frac{u(u + 1)(2uz − u − 1)}{(1 − u)^{3}} log (\frac{1}{1 − uz} ) − \frac{1}{3} \frac{u + 1}{(1 − u)(1 − z)} log (\frac{1}{1 − uz} )

− \frac{4}{3} \frac{u^{2}z}{(1 − u)^{2}} + \frac{u}{(1 − u)(1 − uz)} − \frac{1}{3} \frac{2u + 1}{(1 − u)(1 − z)} + \frac{1}{3} \frac{1}{(1 − z)^{2}} .  (46)

To extract the coefficients from equation (46), we use apart from the formulas (12) also

[z^{n}u^{j}] ∫_{0}^{z} \frac{1}{(1 − t)^{2}(1 − ut)^{2}} log (\frac{1}{1 − t}) dt = \frac{(j + 1)(n − j)}{n}(H_{n−j} − 1) ,  (47a)

\begin{matrix}[z^{n}u^{j}] \frac{1}{1 − z} ∫_{0}^{z} \frac{1}{(1 − t)^{2}(1 − ut)^{2}} log (\frac{1}{1 − t}) dt \\ = (j + 1) ((n − j + 1)H_{n−j} − 2(n − j)) − j(j + 1) ( ∑_{k=j+1}^{n} \frac{H_{k−j}}{k} − (H_{n} − H_{j})) . \end{matrix} (47b)

Theorem 4.1. The expectation A_{n,j} of the height of the node with key j in a p-tree of size n is for 1 ≤ j ≤ n given by

\begin{aligned}A_{n,j} & = −\frac{2}{3} ∑_{k=j+1}^{n} \frac{H_{k−j}}{k} + \frac{1}{3}(H_{n} − H_{j}) + \frac{−\frac{2}{3}l(l + 1)H_{l} + \frac{4}{3}l^{2}}{n − 1} + \frac{\frac{2}{3}(l + 1)^{2}H_{l} − \frac{4}{3}l^{2} − l}{n} \\ & + \frac{1}{3}(H_{l+1}^{2} − H_{l+1}^{(2)}) + \frac{5}{3}H_{l+1} − 1 + \frac{1}{3(l + 1)} with l := n − j . \end{aligned} (48)

Now we evaluate our findings asymptotically, under the assumptions j fixed; j ∼ ρn, with 0 < ρ < 1; n − j fixed. In order to handle the sum ∑_{k=j+1}^{n} \frac{H_{k−j}}{k} asymptotically we state the following relations

∑_{k=j+1}^{n} \frac{H_{k−j}}{k} + ∑_{k=1}^{j−1} \frac{H_{n−k}}{k} = \frac{1}{2} (H_{n}^{2} − H_{n}^{(2)}) − \frac{1}{2} (H_{j−1}^{2} + H_{j−1}^{(2)}) + H_{n}H_{j−1} ,  (49a)

∑_{k=1}^{j} \frac{H_{n−k}}{k} − ∑_{k=1}^{j} \frac{H_{k}}{n − k} = H_{j}H_{n−j−1} ,  (49b)

which can be proved by means of generating functions.

For a fixed ratio ρ = \frac{j}{n} with 0 < ρ < 1 we use for n → ∞ the expansion

∑_{k=1}^{j} \frac{H_{n−k}}{k} = log^{2} n + (log ρ + 2γ) log n + γ^{2} + γ log ρ − dilog(1 − ρ) + o(1) ,  (50)

which can be proved by means of Euler’s summation formula after applying the asymptotics for the harmonic numbers (it can also be found in [12]). We recall the definition of the dilogarithm dilogz (see e. g. [1])

dilogz = ∫_{1}^{z} \frac{log t}{1 − t} dt .  (51)

Combining (18), (49) and (50) we get the following lemma.

Lemma 4.2. The sum ∑_{k=j+1}^{n} \frac{H_{k−j}}{k} has the following asymptotic equivalents:

∑_{k=j+1}^{n} \frac{H_{k−j}}{k} = \frac{1}{2} log^{2} n + γ log n − \frac{π^{2}}{12} + \frac{γ^{2}}{2} − \frac{H_{j}^{2}}{2} + \frac{H_{j}}{j} − \frac{H_{j}^{(2)}}{2} + O (\frac{1}{n})

for fixed j ,

(52a)

∑_{k=j+1}^{n} \frac{H_{k−j}}{k} = O (\frac{1}{n}) for fixed l = n − j ,  (52b)

∑_{k=j+1}^{n} \frac{H_{k−j}}{k} = − log ρ log n + O(1) for j = ρn and 0 < ρ < 1 .  (52c)

With the relations (18) and (52) we get from (48) the following corollary.

Corollary 4.3. The expectation A_{n,j} of the height of the node with key j in a p-tree of size n is for n → ∞ asymptotically given by

A_{n,j} = 2 log n + O(1) for fixed j ,  (53a)
A_{n,j} = \frac{1}{3}H_{l+1}^{2} + \frac{5}{3}H_{l+1} − \frac{1}{3}H_{l+1}^{(2)} − 1 + \frac{1}{3(l + 1)} + O (\frac{1}{n}) for fixed l = n − j ,  (53b)

A_{n,j} = \frac{1}{3} log^{2} n + (−\frac{2}{3}ρ^{2} + \frac{2}{3}ρ + \frac{2}{3}γ + \frac{5}{3} + \frac{2}{3} log ρ + \frac{2}{3} log(1 − ρ)) log n + O(1)

for j = ρn and 0 < ρ < 1 ,

(53c)

Also of interest are the expectations A_{n} of the height of a random node in a p-tree of size n. Because of

A_{n} = \frac{1}{n} ∑_{j=1}^{n} A_{n,j}

these parameters are easily obtained by summing up (48). With basic summation formulas for the harmonic numbers and the relation

∑_{j=1}^{n} ∑_{k=j+1}^{n} \frac{H_{k−j}}{k} = ∑_{k=1}^{n} \frac{1}{k} ∑_{j=1}^{k−1} H_{k−j} = ∑_{k=1}^{n} \frac{1}{k} (kH_{k} − k) = ∑_{k=1}^{n} H_{k} − n = (n + 1)H_{n} − 2n , (54)

we get

Corollary 4.4. The expectation A_{n} of the height of a randomly chosen node in a p-tree of size n is given by

A_{n} = \frac{n + 1}{3n}H_{n}^{2} + \frac{2(2n + 5)}{9n}H_{n} − \frac{n + 1}{3n}H_{n}^{(2)} − \frac{13n + 1}{27n} for n ≥ 2 and A_{1} = 1  (55)

or asymptotically by

A_{n} = \frac{1}{3} log^{2} n + (\frac{2}{3}γ + \frac{4}{9}) log n + O(1) for n → ∞ .  (56)

5. The number of left edges to a node

As opposed to the previous section we consider here the edges from the root to a specified node, but only the leftsided edges. In this way we get an impression of the leftist shape of the tree.

Here we denote by A_{n,j}^{[L]}, B_{n,j}^{[L]} and C_{n,j}^{[L]} the expectations of the number of leftsided edges from the root to the node with key j in objects of size n in the families A, B and C.

To obtain recurrences for these parameters, we use the already computed expectation of the length of the left path of objects in the family C of size n. As was shown in section 3, this expectation is H_{n}.

Decomposing the families A, B and C according to the first element k of a random permutation, we get for 1 ≤ j ≤ n the following recurrences

A_{n,j}^{[L]} = \frac{1}{n} (∑_{k=1}^{j−1} C_{n−k,j−k}^{[L]} + H_{n−j} + ∑_{k=j+1}^{n} (B_{k−1,j}^{[L]} + H_{n−k})) ,  (57a)

B_{n,j}^{[L]} = \frac{1}{n} (∑_{k=1}^{j−1} A_{n−k,j−k}^{[L]} + 1 + ∑_{k=j+1}^{n} (B_{k−1,j}^{[L]} + 1)) ,  (57b)
C_{n,j}^{[L]} = \frac{1}{n} (∑_{k=1}^{j−1} C_{n−k,j−k}^{[L]} + H_{n−j} + ∑_{k=j+1}^{n} (A_{k−1,j}^{[L]} + H_{n−k})) ,  (57c)

with initial values A_{0,0}^{[L]} = 0, B_{0,0}^{[L]} = 0 and C_{0,0}^{[L]} = 0. With the bivariate generating functions A^{[L]}(z, u) = ∑_{j≥1} ∑_{n≥j} A_{n,j}^{[L]}z^{n}u^{j} etc. the above recurrences (multiplied by nz^{n−1}u^{j} and summed up over all n ≥ j ≥ 1) lead to the following system of differential equations

\frac{∂}{∂z} A^{[L]}(z, u) = \frac{u}{1 − uz} C^{[L]}(z, u) + \frac{1}{1 − z} B^{[L]}(z, u) + f_{1}(z, u) ,  (58a)
\frac{∂}{∂z} B^{[L]}(z, u) = \frac{u}{1 − uz} A^{[L]}(z, u) + \frac{1}{1 − z} B^{[L]}(z, u) + f_{2}(z, u) ,  (58b)
\frac{∂}{∂z} C^{[L]}(z, u) = \frac{u}{1 − uz} C^{[L]}(z, u) + \frac{1}{1 − z} A^{[L]}(z, u) + f_{3}(z, u) ,  (58c)

with

f_{1}(z, u) = \frac{u}{(1 − z)(1 − uz)} log (\frac{1}{1 − z} ) + \frac{uz}{(1 − z)^{2}(1 − uz)} log (\frac{1}{1 − z} ) ,
f_{2}(z, u) = \frac{u}{(1 − z)(1 − uz)} + \frac{uz}{(1 − z)^{2}(1 − uz)} ,
f_{3}(z, u) = \frac{u}{(1 − z)(1 − uz)} log (\frac{1}{1 − z} ) + \frac{uz}{(1 − z)^{2}(1 − uz)} log (\frac{1}{1 − z} ) .

This system of differential equations can be solved analogously to (24). This leads to the bivariate generating function A^{[L]}(z, u) of the expectations A_{n,j}^{[L]} of the number of leftsided edges from the root to the node j:

A^{[L]}(z, u) = (\frac{1}{3}u(2uz − u − 1) + \frac{1}{3} \frac{(u − 1)^{2}}{1 − z} ) ∫_{0}^{z} \frac{1}{(1 − t)^{2}(1 − ut)^{2}} log (\frac{1}{1 − t}) dt

+ (−\frac{1}{3} \frac{u^{2}}{(1 − uz)(1 − u)} + \frac{1}{3} \frac{u}{(1 − z)(1 − u)}) log^{2} (\frac{1}{1 − z} )

+ [\frac{2}{3} \frac{(u + 1)(2uz − u − 1)u}{(1 − u)^{3}} + \frac{7}{3} \frac{u}{(1 − z)(1 − u)} − \frac{1}{3} \frac{1}{(1 − z)^{2}} −

− \frac{1}{3} \frac{(5u − 2)u}{(1 − uz)(1 − u)}] log (\frac{1}{1 − z} )

+ (−\frac{2}{3} \frac{(u + 1)(2uz − u − 1)u}{(1 − u)^{3}} − \frac{2}{3} \frac{u + 1}{(1 − z)(1 − u)}) log (\frac{1}{1 − uz} )

+ \frac{8}{3} \frac{u^{2}z}{(1 − u)^{2}} − \frac{1}{3} \frac{4u + 1}{(1 − z)(1 − u)} + \frac{1}{3} \frac{1}{(1 − z)^{2}} + \frac{5}{3} \frac{u}{(1 − uz)(1 − u)} .  (59)

Extracting the coefficients using (12) and (47) we obtain Theorem 5.1. The expectation A_{n,j}^{[L]} of the number of leftsided edges from the root to the node with key j in a p-tree of size n is for 1 ≤ j ≤ n given by

A_{n,j}^{[L]} = −\frac{2}{3} ∑_{k=j+1}^{n} \frac{H_{k−j}}{k} + \frac{1}{3}H_{n−j}^{2} + H_{n} − H_{j} − \frac{1}{3}H_{n−j}^{(2)}

+ (1 + \frac{2}{3} \frac{(j − 1)^{2}}{n} − \frac{2}{3} \frac{(j − 1)(j − 2)}{n − 1} + \frac{2}{3} \frac{1}{n − j + 1}) H_{n−j} − \frac{1}{3} \frac{(3j − 1)(2j − 1)}{n} (60)

+ 2\frac{(j − 1)^{2}}{n − 1} + \frac{5}{3} \frac{1}{n − j + 1} + \frac{1}{3j} − \frac{4}{3} .

The expectation A_{n,j}^{[R]} of the number of rightsided edges from the root to the node j in a p-tree of size n is easy to obtain using the relation

A_{n,j}^{[R]} = A_{n,j} − 1 − A_{n,j}^{[L]} .  (61)

Theorem 5.2. The expectation A_{n,j}^{[R]} of the number of rightsided edges from the root to the node with key j in a p-tree of size n is for n ≥ j ≥ 1 given by

A_{n,j}^{[R]} = \frac{2}{3}H_{n−j} − \frac{2}{3}H_{n} + \frac{2}{3}H_{j} + \frac{1}{3} \frac{2j^{2} − 2j + 1}{n} − \frac{2}{3} \frac{(j − 1)^{2}}{n − 1} + \frac{1}{3} \frac{1}{n − j + 1} − \frac{1}{3j} − \frac{1}{3} . (62)

With the relations (18) and (52) we get the following asymptotic corollaries.

Corollary 5.3. The expectation A_{n,j}^{[L]} of the number of leftsided edges from the root to the node with key j in a p-tree of size n is for n → ∞ asymptotically given by

A_{n,j}^{[L]} = 2 log n + O(1) for fixed j ,  (63a)
A_{n,j}^{[L]} = \frac{1}{3}H_{l}^{2} + H_{l} − \frac{5}{3} − \frac{1}{3}H_{l}^{(2)} + \frac{2}{3} \frac{H_{l}}{l + 1} + \frac{5}{3} \frac{1}{l + 1} + O (\frac{1}{n}) for fixed l = n − j , (63b)

A_{n,j}^{[L]} = \frac{1}{3} log^{2} n + (−\frac{2}{3}ρ^{2} + \frac{2}{3}ρ + \frac{2}{3}γ + 1 + \frac{2}{3} log ρ + \frac{2}{3} log(1 − ρ)) log n + O(1)

for j = ρn and 0 < ρ < 1 .

(63c)

Corollary 5.4. The expectation A_{n,j}^{[R]} of the number of rightsided edges from the root to the node with key j in a p-tree of size n is for n → ∞ asymptotically given by

A_{n,j}^{[R]} = \frac{2}{3}H_{j} − \frac{1}{3} − \frac{1}{3j} + O (\frac{1}{n}) for fixed j ,  (64a)
A_{n,j}^{[R]} = \frac{2}{3}H_{l} − \frac{1}{3} + \frac{1}{3} \frac{1}{l + 1} + O (\frac{1}{n}) for fixed l = n − j ,  (64b)

A_{n,j}^{[R]} = \frac{2}{3} log n − \frac{2}{3}ρ^{2} + \frac{2}{3}ρ − \frac{1}{3} + \frac{2}{3}γ + \frac{2}{3} log ρ + \frac{2}{3} log(1 − ρ) + O (\frac{1}{n})

for j = ρn and 0 < ρ < 1 .

(64c)

6. The number of descendants

In the following we consider the number of descendants of particular nodes in objects of the families A, B and C. The number of descendants of a node x is here defined as the size of the subtree rooted at node x.

To get recurrences for the expectations A_{n,j}, B_{n,j} and C_{n,j} of the number of descendants of the node with key j of objects in the families A, B and C of size n, we introduce auxiliary parameters q_{n,j}, C_{n,j}^{[Q]} and C_{n,j}^{[¬Q]}.

Here q_{n,j} is the probability, that the node with key j in an object of C of size n is positioned on the left path, that means, that node j lies on the path from the root to the left leaf. This is equivalent to the condition, that the node j is a left-to-right maximum in a random permutation of size n, and so we get

q_{n,j} = \frac{1}{n − j + 1} .

With C_{n,j}^{[Q]} we denote the conditional expectation of the number of desendants of node j in an object of C with size n, under the condition, that the node j lies on the left path.

Consequently C_{n,j}^{[¬Q]} denotes the conditional expectation of the number of descendants of node j in an object of C with size n under the condition, that the node j does not lie on the left path.

Decomposing the families A, B and C according to the first element k of a random permutation leads for n ≥ j ≥ 1 to the following recurrences

A_{n,j} = \frac{1}{n} [∑_{k=1}^{j−1} (q_{n−k,j−k} (C_{n−k,j−k}^{[Q]} + k) + (1 − q_{n−k,j−k}) C_{n−k,j−k}^{[¬Q]}) + j + ∑_{k=j+1}^{n} B_{k−1,j}] , (65a)

B_{n,j} = \frac{1}{n} [∑_{k=1}^{j−1} A_{n−k,j−k} + j + ∑_{k=j+1}^{n} B_{k−1,j}] ,  (65b)

C_{n,j} = \frac{1}{n} [∑_{k=1}^{j−1} (q_{n−k,j−k} (C_{n−k,j−k}^{[Q]} + k) + (1 − q_{n−k,j−k}) C_{n−k,j−k}^{[¬Q]}) + j + ∑_{k=j+1}^{n} A_{k−1,j}] . (65c)

With the trivial equivalence

C_{n,j} = q_{n,j}C_{n,j}^{[Q]} + (1 − q_{n,j}) C_{n,j}^{[¬Q]} ,

the system (65) leads for n ≥ j ≥ 1 to the recurrences

A_{n,j} = \frac{1}{n} (∑_{k=1}^{j−1} (C_{n−k,j−k} + \frac{k}{n − j + 1}) + j + ∑_{k=j+1}^{n} B_{k−1,j}) ,  (66a)

B_{n,j} = \frac{1}{n} (∑_{k=1}^{j−1} A_{n−k,j−k} + j + ∑_{k=j+1}^{n} B_{k−1,j}) ,  (66b)
C_{n,j} = \frac{1}{n} (∑_{k=1}^{j−1} (C_{n−k,j−k} + \frac{k}{n − j + 1}) + j + ∑_{k=j+1}^{n} A_{k−1,j}) ,  (66c)

with initial values A_{0,0} = 0, B_{0,0} = 0 and C_{0,0} = 0. Introducing bivariate generating functions A(z, u) = ∑_{j≥1} ∑_{n≥j} A_{n,j}z^{n}u^{j} etc. we get from the system of recurrences (66) by multiplication with nz^{n−1}u^{j} and summing up over all n ≥ j ≥ 1 the following system of differential equations

\frac{∂}{∂z} A(z, u) = \frac{u}{1 − uz} C(z, u) + \frac{1}{1 − z} B(z, u) + f_{1}(z, u) ,  (67a)
\frac{∂}{∂z} B(z, u) = \frac{u}{1 − uz} A(z, u) + \frac{1}{1 − z} B(z, u) + f_{2}(z, u) ,  (67b)
\frac{∂}{∂z} C(z, u) = \frac{u}{1 − uz} C(z, u) + \frac{1}{1 − z} A(z, u) + f_{3}(z, u)  (67c)

with

f_{1}(z, u) = \frac{u^{2}}{(1 − uz)^{3}} log (\frac{1}{1 − z} ) + \frac{u}{(1 − z)(1 − uz)^{2}} ,
f_{2}(z, u) = \frac{u}{(1 − z)(1 − uz)^{2}} ,
f_{3}(z, u) = \frac{u^{2}}{(1 − uz)^{3}} log (\frac{1}{1 − z} ) + \frac{u}{(1 − z)(1 − uz)^{2}} .

This system can be solved analogously to (24), and we get for A(z, u)

A(z, u) = [−\frac{1}{3}uz + \frac{1}{6}u + \frac{1}{6} + \frac{1}{2} \frac{(u − 1)^{2}}{u(1 − z)}

− \frac{2}{3} \frac{(u − 1)^{2}}{1 − uz} ] ∫_{0}^{z} \frac{1}{(1 − t)^{2}(1 − ut)^{2}} log (\frac{1}{1 − t}) dt

+ (−\frac{1}{6} \frac{(2uz − u − 1)u}{(1 − u)^{3}} + \frac{1}{2} \frac{1}{(1 − z)(1 − u)} − \frac{2}{3} \frac{u}{(1 − uz)(1 − u)}) log^{2} (\frac{1}{1 − z} )

+ (+\frac{1}{3} \frac{(2uz − u − 1)u}{(1 − u)^{3}} + \frac{1}{3} \frac{u}{(1 − uz)(1 − u)}) log (\frac{1}{1 − z} ) log (\frac{1}{1 − uz} )

+ (−\frac{1}{6} \frac{(2uz − u − 1)u}{(1 − u)^{3}} − \frac{1}{6} \frac{1}{(1 − z)(1 − u)}) log^{2} (\frac{1}{1 − uz} )

+ [−\frac{2}{3} \frac{u}{(1 − u)^{2}} + \frac{1}{2} \frac{1}{(1 − z)(1 − u)} − \frac{1}{2} \frac{1}{(1 − z)^{2}u} − \frac{1}{2} \frac{u}{(1 − uz)(1 − u)}

+ \frac{5}{3} \frac{u}{(1 − uz)^{2}} ] log (\frac{1}{1 − z} )

+ (\frac{2}{3} \frac{u}{(1 − u)^{2}} − \frac{2}{3} \frac{1}{(1 − z)(1 − u)} + \frac{2}{3} \frac{u}{(1 − uz)(1 − u)}) log (\frac{1}{1 − uz} )

+ \frac{1}{6} \frac{2uz − u − 1}{1 − u} + \frac{1}{6} \frac{u^{2} − 3}{(1 − z)(1 − u)u} + \frac{1}{2} \frac{1}{(1 − z)^{2}u} + \frac{2}{3} \frac{1}{(1 − uz)(1 − u)} . (68)

To extract the coefficients of this expression, we need apart from (12) and (47) the following equations

[z^{n}u^{j}]\frac{1}{(1 − u)^{3}} log (\frac{1}{1 − z} ) log (\frac{1}{1 − uz} )

= − \frac{1}{2}j + \frac{1}{2} \frac{j^{2} + 3j + 2}{n}H_{j} + \frac{1}{2} \frac{n^{2} − 2jn − 3n + j^{2} + 3j + 2}{n} (H_{n−1} − H_{n−j−1}) , (69a)
[z^{n}u^{j}]\frac{1}{(1 − u)(1 − uz)} log (\frac{1}{1 − z} ) log (\frac{1}{1 − uz} ) = ∑_{k=1}^{j} \frac{H_{k}}{n − k} .  (69b)

Then we get from (68) for the desired expectations

A_{n,j} = \frac{1}{3} ∑_{k=1}^{j−1} \frac{H_{k}}{n − k} − ∑_{k=j+1}^{n} \frac{H_{k−j}}{k} − \frac{1}{6}H_{n}^{2} − \frac{2}{3}H_{n−j}^{2} + \frac{4}{3}H_{n−j}H_{n} − \frac{1}{6}H_{j}^{2}

+ \frac{1}{6} \frac{j − 6}{j}H_{n} − \frac{1}{6} \frac{j − 6}{j}H_{n−j} − \frac{1}{6} \frac{n^{2}j − 6n^{2} + 2nj^{2} − nj + 6n − 2j^{3}}{n(n − 1)j} H_{j}  (70)

+ \frac{1}{6}H_{n}^{(2)} − \frac{2}{3}H_{n−j}^{(2)} + \frac{1}{6}H_{j}^{(2)} + \frac{1}{6} \frac{n^{3} + 6n^{2}j − 3nj^{2} − 3nj − n + 2j^{3} − 3j^{2} + j}{n(n − 1)(n − j + 1)} ,

which can be simplified by use of equations (49). This leads to

Theorem 6.1. The expectation A_{n,j} of the number of descendants of the node with key j in a p-tree of size n is for 1 ≤ j ≤ n given by

A_{n,j} = \frac{4}{3} ∑_{k=1}^{j} \frac{H_{n−k}}{k} − \frac{2}{3}H_{n−j}^{2} + \frac{4}{3}H_{n−j}H_{n} − \frac{1}{3}H_{n−j}H_{j} − \frac{2}{3}H_{n}^{2} − H_{n}H_{j} + \frac{1}{3}H_{j}^{2}

− \frac{1}{6}H_{n−j} + \frac{1}{6}H_{n} + (−\frac{1}{6} + \frac{1}{3} \frac{j(j − 1)}{n − 1} − \frac{j^{2}}{3n}) H_{j} − \frac{2}{3}H_{n−j}^{(2)} + \frac{2}{3}H_{n}^{(2)} + \frac{2}{3}H_{j}^{(2)} (71)

+ \frac{j}{n − j + 1} − \frac{1}{3} \frac{j(j − 1)}{n − 1} + \frac{1}{6} \frac{j(2j − 1)}{n} + \frac{1}{6} .

To evaluate our findings asymptotically, under the assumptions j fixed; j ∼ ρn, with 0 < ρ < 1; n − j, we state here the following lemma, that handles the sum ∑_{k=1}^{j} \frac{H_{n−k}}{k} asymptotically. It can be obtained easily from (52) by use of (49).

Lemma 6.2. The sum ∑_{k=1}^{j} \frac{H_{n−k}}{k} has the following asymptotic equivalents:

∑_{k=1}^{j} \frac{H_{n−k}}{k} = H_{j} log n + γH_{j} + O (\frac{1}{n}) for fixed j ,  (72a)

∑_{k=1}^{j} \frac{H_{n−k}}{k} = log^{2} n + 2γ log n + γ^{2} − \frac{π^{2}}{6} + O (\frac{1}{n}) for fixed l = n − j ,  (72b)

∑_{k=1}^{j} \frac{H_{n−k}}{k} = log^{2}(n) + (log ρ + 2γ) log n + γ^{2} + γ log ρ − dilog(1 − ρ) + o(1)
for j = ρn and 0 < ρ < 1 .

(72c)

Now we obtain from (72a) by use of the previous lemma

Corollary 6.3. The expectation A_{n,j} of the number of descendants with key j in a p-tree of size n is for n → ∞ asymptotically given by

A_{n,j} = \frac{1}{3}H_{j}^{2} − \frac{1}{6}H_{j} + \frac{2}{3}H_{j}^{(2)} + \frac{1}{6} + O (\frac{1}{n}) for fixed j ,  (73a)
A_{n,j} = \frac{n}{l + 1} + H_{l} log n + O(1) for fixed l = n − j ,  (73b)

A_{n,j} = \frac{1}{3} log^{2} n + (\frac{1}{3}ρ^{2} − \frac{1}{3}ρ − \frac{1}{6} + \frac{2}{3}γ + \frac{2}{3} log ρ − \frac{1}{3} log(1 − ρ)) log n + O(1)

for j = ρn and 0 < ρ < 1 .

(73c)

7. The number of key comparisons when inserting an element

To insert a new element into a p-tree we need the recursive algorithm Insert as described in section 1. Here we are interested in the average number of key comparisons that are made, when a particular new element is inserted into a random p-tree.

In the following we denote by A_{n,j}^{[I]}, B_{n,j}^{[I]} and C_{n,j}^{[I]} the expectations of the number of key comparisons, that are made when inserting the element with key j + \frac{1}{2} with j ∈ ℤ and 0 ≤ j ≤ n into an object of size n of the families A, B and C.

Decomposing the families A, B and C according to the first element k of a random permutation leads for n ≥ 1 and 0 ≤ j ≤ n to the following recurrences

A_{n,j}^{[I]} = \frac{1}{n} (∑_{k=1}^{j} C_{n−k,j−k}^{[I]} + ∑_{k=j+1}^{n} (B_{k−1,j}^{[I]} + H_{n−k})) ,  (74a)

B_{n,j}^{[I]} = \frac{1}{n} (∑_{k=1}^{j} (A_{n−k,j−k}^{[I]} + 2) + ∑_{k=j+1}^{n} (B_{k−1,j}^{[I]} + 1)) ,  (74b)

C_{n,j}^{[I]} = \frac{1}{n} (∑_{k=1}^{j} C_{n−k,j−k}^{[I]} + ∑_{k=j+1}^{n} (A_{k−1,j}^{[I]} + H_{n−k} + 2)) ,  (74c)

with the initial values A_{0,0}^{[I]} = 0, B_{0,0}^{[I]} = 1 and C_{0,0}^{[I]} = 1.

Multiplying (74) by nz^{n−1}u^{j} and summing up leads by use of the bivariate generating functions

A^{[I]}(z, u) = ∑_{j≥0} ∑_{n≥j} A_{n,j}^{[I]}z^{n}u^{j} , B^{[I]}(z, u) = ∑_{j≥0} ∑_{n≥j} B_{n,j}^{[I]}z^{n}u^{j} , C^{[I]}(z, u) = ∑_{j≥0} ∑_{n≥j} C_{n,j}^{[I]}z^{n}u^{j}

AVERAGE CASE-ANALYSIS OF PRIORITY TREES 23

to the following system of differential equations

\frac{∂}{∂z} A^{[I]}(z, u) = \frac{u}{1 − uz} C^{[I]}(z, u) + \frac{1}{1 − z} B^{[I]}(z, u) + f_{1}(z, u) ,  (75a)
\frac{∂}{∂z} B^{[I]}(z, u) = \frac{u}{1 − uz} A^{[I]}(z, u) + \frac{1}{1 − z} B^{[I]}(z, u) + f_{2}(z, u) ,  (75b)
\frac{∂}{∂z} C^{[I]}(z, u) = \frac{u}{1 − uz} C^{[I]}(z, u) + \frac{1}{1 − z} A^{[I]}(z, u) + f_{3}(z, u)  (75c)

with

f_{1}(z, u) = \frac{1}{(1 − z)^{2}(1 − uz)} log (\frac{1}{1 − z} ) ,
f_{2}(z, u) = \frac{2u}{(1 − z)(1 − uz)^{2}} + \frac{1}{(1 − z)^{2}(1 − uz)} ,
f_{3}(z, u) = \frac{1}{(1 − z)^{2}(1 − uz)} log (\frac{1}{1 − z} ) + \frac{2}{(1 − z)^{2}(1 − uz)} .

Analogously to the previous sections we find as solution of (75) for A^{[I]}(z, u):

A^{[I]}(z, u) = (\frac{2}{3}uz − \frac{1}{3}u − \frac{1}{3} + \frac{1}{3} \frac{(u − 1)^{2}}{(1 − z)u}) ∫_{0}^{z} \frac{1}{(1 − t)^{2}(1 − ut)^{2}} log (\frac{1}{1 − t}) dt

+ (−\frac{1}{3} \frac{u}{(1 − uz)(1 − u)} + \frac{1}{3} \frac{1}{(1 − z)(1 − u)}) log^{2} (\frac{1}{1 − z} )

+ [\frac{1}{3} \frac{(u + 1)(2uz − u − 1)}{(1 − u)^{2}} + \frac{7}{3} \frac{1}{(1 − z)(1 − u)} − \frac{1}{3} \frac{1}{(1 − z)^{2}u}

− \frac{1}{3} \frac{u^{2} + 7u − 1}{(1 − uz)(1 − u)}] log (\frac{1}{1 − z} )

+ (−\frac{1}{3} \frac{(u + 1)(2uz − u − 1)}{(1 − u)^{2}} − \frac{1}{3} \frac{u + 1}{(1 − z)u}) log (\frac{1}{1 − uz} )

+ \frac{4}{3} \frac{uz}{(1 − u)} + \frac{1}{3} \frac{2u^{2} − 2u − 1}{(1 − z)(1 − u)u} + \frac{1}{3} \frac{1}{(1 − z)^{2}u} − \frac{1}{3} \frac{2u − 3}{(1 − uz)(1 − u)} .  (76)

Extracting the coefficients leads to Theorem 7.1. The expectation A_{n,j}^{[I]} of the number of key comparisons, that are made by inserting a new element with key j + \frac{1}{2} with the procedure Insert in a p-tree of size n is given by

\begin{aligned}A_{n,j}^{[I]} & = −\frac{2}{3} ∑_{k=j+1}^{n} \frac{H_{k−j}}{k} + \frac{1}{3}H_{n−j}^{2} + (−\frac{1}{3} − \frac{2}{3j} ) H_{n} + (\frac{1}{3} + \frac{2}{3j} ) H_{j} \\ & + (\frac{7}{3} + \frac{2}{3j} + \frac{2}{3} \frac{j^{2}}{n} − \frac{2}{3} \frac{j(j − 1)}{n − 1}) H_{n−j} − \frac{1}{3}H_{n−j}^{(2)} − \frac{1}{3} \frac{j(2j + 5)}{n} + \frac{2}{3} \frac{j^{2} + j − 1}{n − 1} \\ & + \frac{1}{3} \frac{1}{n − j + 1} + \frac{1}{3} \frac{1}{n − j} − \frac{1}{3} \frac{1}{j + 1} − \frac{1}{3j} for 1 ≤ j ≤ n − 1 , \end{aligned} (77)

A_{n,n}^{[I]} = 1 for n ≥ 1 , A_{0,0}^{[I]} = 0 , A_{n,0}^{[I]} = 2H_{n} − 1 for n ≥ 1 .

We also state the following asymptotic equivalents

Corollary 7.2. The expectation A_{n,j}^{[I]} of the number of key comparisons, that are made when inserting a new element with key j + \frac{1}{2} with the procedure Insert in a p-tree of size n is for n → ∞ asymptotically given by

A_{n,j}^{[I]} = 2 log n + O(1) for fixed j ,  (78a)
A_{n,j}^{[I]} = \frac{1}{3}H_{l}^{2} + \frac{7}{3}H_{l} − \frac{1}{3} − \frac{1}{3}H_{l}^{(2)} + \frac{1}{3l} + \frac{1}{3(l + 1)} + O (\frac{1}{n}) for fixed l = n − j , (78b)

A_{n,j}^{[I]} = \frac{1}{3} log^{2} n + (−\frac{2}{3}ρ^{2} + \frac{2}{3}ρ + \frac{2}{3}γ + \frac{7}{3} + \frac{2}{3} log ρ + \frac{2}{3} log(1 − ρ)) + O(1)

for j = ρn and 0 < ρ < 1 .

(78c)

Furthermore we get for the arithmetic mean A_{n}^{[I]} = \frac{1}{n+1} ∑_{j=0}^{n} A_{n,j}^{[I]} of the number of key comparisons when inserting a new element in a p-tree of size n by summing up (78a)

Corollary 7.3. The expectation A_{n}^{[I]} of the number of key comparisons, that are made when inserting a randomly chosen element from the set \{\frac{1}{2}, \frac{3}{2}, …, \frac{n+1}{2}\} with the algorithm Insert in a p-tree of size n is given by

A_{n}^{[I]} = \frac{1}{3}H_{n+1}^{2} + \frac{10}{9}H_{n+1} − \frac{1}{3}H_{n+1}^{(2)} − \frac{28}{27} for n ≥ 2 , A_{1}^{[I]} = 1 .  (79)

This result can be found already in [10].

8. Analysis of a procedure to split p-trees

Beside the algorithms Insert and Delete to insert resp. remove an element of a p-tree, we consider here the algorithm Cut to split a p-tree at an arbitrary place into two p-trees. This procedure was introduced in [13]. Thereby a tree T will be split into two p-trees according to a given key s in such a way that one tree T_{1} contains all nodes from T with keys less or equal s, whereas the remaining tree T − T_{1} contains all nodes with keys greater than s. The trees obtained in this way might also be empty.

In more detail, the recursive algorithm Cut reads as follows. (We use the abbreviation T (x) for the subtree with node x as root, when x is a node of the tree T.)

1. (a) If T is empty or the root of T has a smaller key than s, then set T_{1} := T, set T := ∅

and terminate.

(b) Otherwise set T_{1} := ∅ and go to step 2.

2. Move along the left path of T until the first node y with key less or equal s is found. (a) If no such node is found, terminate.

(b) Otherwise we denote by z the predecessor of y. Then it is known that s lies between the keys of y and z.

(i) If the right subtree of z is empty, then set T_{1} := T (y) and T := T − T (y). (ii) Otherwise attach the right subtree of z between z and the left son of z and set the right subtree of the node z empty. Search the left leaf of T (z) and connect the node y to it. Finally repeat step 2 starting from the node z.

In [13] it was stated, that the number of key comparisons splitting a randomly generated p-tree according to a key s in this algorithm is the same as the number of key comparisons inserting the element s in the tree. This is not fully correct, although the difference is marginal.

To analyse this parameter, we denote by A_{n,j}^{[C]}, B_{n,j}^{[C]} and C_{n,j}^{[C]} the expectations of the number of key comparisons, that are made by cutting an object of size n of the families A, B and C according to the key j + \frac{1}{2} with j ∈ ℤ and 0 ≤ j ≤ n.

To get recurrences we decompose the object families w. r. t. the first element k of a random permutation. When the tree is cut at the position k + \frac{1}{2}, that means that j = k, then k is compared with the key a second time, whenever the node with key k has a predecessor with nonempty right subtree. In the following recurrence this fact leads in opposition to the recurrence (74) for the insertion algorithm to the additional functions r_{1}(n, j), r_{2}(n, j) and r_{3}(n, j).

We have for n ≥ 1 and n ≥ j ≥ 0

A_{n,j}^{[C]} = \frac{1}{n} (∑_{k=1}^{j} C_{n−k,j−k}^{[C]} + ∑_{k=j+1}^{n} (B_{k−1,j}^{[C]} + H_{n−k}) + r_{1}(n, j)) ,  (80a)

B_{n,j}^{[C]} = \frac{1}{n} (∑_{k=1}^{j} (A_{n−k,j−k}^{[C]} + 2) + ∑_{k=j+1}^{n} (B_{k−1,j}^{[C]} + 1) + r_{2}(n, j)) ,  (80b)

C_{n,j}^{[C]} = \frac{1}{n} (∑_{k=1}^{j} C_{n−k,j−k}^{[C]} + ∑_{k=j+1}^{n} (A_{k−1,j}^{[C]} + H_{n−k} + 2) + r_{3}(n, j)) ,  (80c)

with

r_{1}(n, j) = \begin{cases}1 − \frac{1}{n−j} & for 1 ≤ j ≤ n − 1 , \\ 0 & otherwise , \end{cases}

r_{2}(n, j) = \begin{cases}1 & for 1 ≤ j ≤ n − 1 , \\ 0 & otherwise , \end{cases}

r_{3}(n, j) = \begin{cases}1 − \frac{1}{n−j} & for 1 ≤ j ≤ n − 1 , \\ 0 & otherwise \end{cases}

and the initial values A_{0,0}^{[C]} = 0, B_{0,0}^{[C]} = 1 and C_{0,0}^{[C]} = 1.

Introducing the usual generating functions A^{[C]}(z, u) = ∑_{j≥0} ∑_{n≥j} A_{n,j}^{[C]}z^{n}u^{j} etc. these recurrences lead (by multiplying with nz^{n−1}u^{j} and summing up) to the following system of differential equations,

\frac{∂}{∂z} A^{[C]}(z, u) = \frac{u}{1 − uz} C^{[C]}(z, u) + \frac{1}{1 − z} B^{[C]}(z, u) + f_{1}(z, u) ,  (81a)
\frac{∂}{∂z} B^{[C]}(z, u) = \frac{u}{1 − uz} A^{[C]}(z, u) + \frac{1}{1 − z} B^{[C]}(z, u) + f_{2}(z, u) ,  (81b)

26 A. PANHOLZER AND H. PRODINGER

\frac{∂}{∂z} C^{[C]}(z, u) = \frac{u}{1 − uz} C^{[C]}(z, u) + \frac{1}{1 − z} A^{[C]}(z, u) + f_{3}(z, u)  (81c)

with

f_{1}(z, u) = \frac{1}{(1 − z)^{2}(1 − uz)} log (\frac{1}{1 − z} ) + \frac{uz}{(1 − z)(1 − uz)} − \frac{u}{1 − uz} log (\frac{1}{1 − z} ) ,
f_{2}(z, u) = \frac{2u}{(1 − z)(1 − uz)^{2}} + \frac{1}{(1 − z)^{2}(1 − uz)} + \frac{uz}{(1 − z)(1 − uz)} ,
f_{3}(z, u) = \frac{1}{(1 − z)^{2}(1 − uz)} log (\frac{1}{1 − z} ) + \frac{2}{(1 − z)^{2}(1 − uz)} + \frac{uz}{(1 − z)(1 − uz)}

− \frac{u}{1 − uz} log (\frac{1}{1 − z} ) .

We get the following solution for the generating function

A^{[C]}(z, u) = (\frac{2}{3}uz − \frac{1}{3}u − \frac{1}{3} + \frac{1}{3} \frac{(u − 1)^{2}}{(1 − z)u}) ∫_{0}^{z} \frac{1}{(1 − t)^{2}(1 − ut)^{2}} log (\frac{1}{1 − t}) dt

+ (−\frac{1}{3} \frac{u}{(1 − uz)(1 − u)} + \frac{1}{3} \frac{1}{(1 − z)(1 − u)}) log^{2} (\frac{1}{1 − z} )

+ (\frac{1}{3} \frac{(2uz − u − 1)u}{(1 − u)^{2}} + \frac{7}{3} \frac{1}{(1 − z)(1 − u)} − \frac{1}{3} \frac{1}{(1 − z)^{2}u}

− \frac{1}{3} \frac{(u + 6)u}{(1 − uz)(1 − u)}) log (\frac{1}{1 − z} )

+ (−\frac{1}{3} \frac{(2uz − u − 1)u}{(1 − u)^{2}} − \frac{1}{3} \frac{1}{(1 − z)}) log (\frac{1}{1 − uz} )

+ \frac{2}{3} \frac{uz − u + 1}{1 − u} + \frac{2}{3} \frac{1}{1 − uz} − \frac{1}{3} \frac{4u + 1}{(1 − z)u} + \frac{1}{3} \frac{1}{(1 − z)^{2}u}  (82)

and, by extracting the coefficients, the following theorem. Theorem 8.1. The expectation A_{n,j}^{[I]} of the number of key comparisons, that are made by cutting a p-tree of size n with the algorithm Cut w. r. t. to an element with key j + \frac{1}{2} is given by

\begin{aligned}A_{n,j}^{[C]} & = −\frac{2}{3} ∑_{k=j+1}^{n} \frac{H_{k−j}}{k} + \frac{1}{3}H_{n−j}^{2} + (−\frac{1}{3} − \frac{2}{3j} ) H_{n} + (\frac{1}{3} + \frac{2}{3j} ) H_{j} \\ & + (\frac{7}{3} + \frac{2}{3j} + \frac{2}{3} \frac{j^{2}}{n} − \frac{2}{3} \frac{j(j − 1)}{n − 1}) H_{n−j} − \frac{1}{3}H_{n−j}^{(2)} − \frac{2j^{2} + 3j − 1}{3n} \\ & + \frac{2}{3} \frac{(j − 1)(j + 1)}{n − 1} + \frac{1}{3} \frac{1}{n − j + 1} − \frac{1}{3j} + \frac{1}{3} for 1 ≤ j ≤ n − 1 , \end{aligned}  (83)

A_{n,n}^{[C]} = 1 for n ≥ 1 , A_{0,0}^{[C]} = 0 , A_{n,0}^{[C]} = 2H_{n} − 1 for n ≥ 1 .

We have the following asymptotic equivalents Corollary 8.2. The expectation A_{n,j}^{[I]} of the number of key comparisons, that are made by cutting a p-tree of size n with the algorithm Cut w. r. t. to an element with key j + \frac{1}{2} is for n → ∞ asymptotically given by

A_{n,j}^{[C]} = 2 log n + O(1) for fixed j ,  (84a)
A_{n,j}^{[C]} = \frac{1}{3}H_{l}^{2} + \frac{7}{3}H_{l} − \frac{1}{3}H_{l}^{(2)} + \frac{1}{3(l + 1)} + O (\frac{1}{n}) for fixed l = n − j ,  (84b)

A_{n,j}^{[C]} = \frac{1}{3} log^{2} n + (−\frac{2}{3}ρ^{2} + \frac{2}{3}ρ + \frac{2}{3}γ + \frac{7}{3} + \frac{2}{3} log ρ + \frac{2}{3} log(1 − ρ)) + O(1)

for j = ρn and 0 < ρ < 1 .

(84c)

Furthermore we state

Corollary 8.3. The expectation A_{n}^{[C]} of the number of key comparisons, that are made by cutting a p-tree of size n with the algorithm Cut w. r. t. to a randomly chosen element from the set \{\frac{1}{2}, \frac{3}{2}, …, \frac{n+1}{2}\} is given by

A_{n}^{[C]} = \frac{1}{3}H_{n+1}^{2} + \frac{10}{9}H_{n+1} − \frac{1}{3}H_{n+1}^{(2)} − \frac{19n + 46}{27(n + 1)} for n ≥ 2 , A_{1}^{[C]} = 1 .  (85)

9. The number of nodes with 0, 1 and 2 children

In this section we consider the number of nodes in a randomly generated p-tree with 0, 1 or 2 internal nodes as successors. First we state the following nonobvious relation between the p-trees and binary search trees.

Theorem 9.1. The distribution of the number of nodes with 0, 1 or 2 children in a p-tree of size n is equal to the distribution of the number of nodes with 0, 1 or 2 children in random binary search trees of size n.

Proof. At first we remark, that to prove the theorem it is enough to show, that the number of leaves in p-trees and binary search trees are identically distributed. If we denote in an arbitrary binary tree of size n with n_{0}, n_{1} resp. n_{2} the number of nodes with 0, 1 and 2 children, then we have by counting the nodes and the edges in the tree the following relations

n_{0} + n_{1} + n_{2} = n and n_{1} + 2n_{2} = n − 1 .

Therefore n_{1} and n_{2} are obtained from n_{0} via

n_{1} = n + 1 − 2n_{0} and n_{2} = n_{0} − 1 .

Now we show, that the number of leaves in p-trees and binary search trees of the same size are identically distributed. We denote here by F_{n,m} the number of binary search trees of size n with exactly m leaves. They fulfill for n ≥ 2 the following recurrence

F_{n,m} = \frac{1}{n} ∑_{k=1}^{n} ∑_{l=1}^{m} F_{k−1,l} · F_{n−k,m−l} ,  (86)

with initial values F_{0,0} = 1 and F_{1,1} = 1.

Introducing the bivariate generating function F (z, v) of the F_{n,m}

F (z, v) = ∑_{n≥0} ∑_{m≥0} F_{n,m}z^{n}v^{m} ,

the above recurrence (86) leads (by multiplying with nz^{n−1}v^{m} and summing up) to the linear differential equation

\frac{∂}{∂z} F (z, v) = F^{2}(z, v) + v − 1 , F (0, v) = 1 .  (87)

Now it suffices to show, that the generating function A(z, v) of the number A_{n,m} of p-trees of size n with exactly m leaves fulfill the same differential equation.

Decomposing the objects of the families A, B and C w. r. t. the first element k of a random permutation with n elements, the probabilities A_{n,m}, B_{n,m} resp. C_{n,m}, that an object of size n of the corresponding family has exactly m leaves leads for n ≥ 1 to the following recurrence

A_{n,m} = \frac{1}{n} ∑_{k=1}^{n} ∑_{i=0}^{m} C_{n−k,i} · B_{k−1,m−i} ,  (88a)

B_{n,m} = \frac{1}{n} ∑_{k=1}^{n} ∑_{i=0}^{m} A_{n−k,i} · B_{k−1,m−i} ,  (88b)

C_{n,m} = \frac{1}{n} ∑_{k=1}^{n} ∑_{i=0}^{m} C_{n−k,i} · A_{k−1,m−i}  (88c)

with initial values A_{0,m} = δ_{0,m}, B_{0,m} = δ_{1,m} and C_{0,m} = δ_{0,m}.

Introducing the usual generating functions A(z, v) = ∑_{n≥0} ∑_{m≥0} A_{n,m}z^{n}v^{m} etc. the above recurrences lead by multiplying with nz^{n−1}v^{m} and summing up to the following system of differential equations

\frac{∂}{∂z} A(z, v) = B(z, v) C(z, v) ,  (89a)
\frac{∂}{∂z} B(z, v) = A(z, v) B(z, v) ,  (89b)
\frac{∂}{∂z} C(z, v) = A(z, v) C(z, v) ,  (89c)

with the initial values A(0, v) = 1, B(0, v) = v and C(0, v) = 1.

Differentiating equation (89a) with respect to z leads to

\frac{∂^{2}}{∂z^{2}} A(z, v) = \frac{∂}{∂z} B(z, v) C(z, v) + B(z, v) \frac{∂}{∂z} C(z, v) .  (90)

Now we substitute \frac{∂}{∂z} B(z, v) and \frac{∂}{∂z} C(z, v) in (90) by the corresponding right sides of the equations (89b) and (89c). Then we get

\frac{∂^{2}}{∂z^{2}} A(z, v) = 2A(z, v) B(z, v) C(z, v) .  (91)

Substituting the factor B(z, v) C(z, v) in this equation by \frac{∂}{∂z} A(z, v) according to (89a), we get the following nonlinear differential equation of order 2 for A(z, v):

\frac{∂^{2}}{∂z^{2}} A(z, v) = 2 A(z, v) \frac{∂}{∂z} A(z, v) ,

A(0, v) = 1 , \frac{∂}{∂z} A(z, v)|_{z=0} = v .  (92)

This differential equation is of the type A′′ = f(A, A′), that means the variable z does not appear explicitly. To handle such an equation, we define a function q(A, v) of A and v, with \frac{∂}{∂z} A(z, v) = q(A, v) (see e. g. [15]). We get then from (92) a differential equation for the function q by the following procedure:

\frac{dq}{dA} = \frac{dq}{dz} \frac{dz}{dA} = \frac{dq}{dz} \frac{1}{\frac{dA}{dz}} = \frac{∂^{2}}{∂z^{2}} A \frac{1}{\frac{∂}{∂z} A} = 2 A .  (93)

This differential equation has the solution

q(A, v) = A(z, v)^{2} + c_{1}(v)  (94)

with a function c_{1}(v).

With q(A, v) = \frac{∂}{∂z} A(z, v) and fitting to the initial conditions we get the same first order differential equation for A(z, v) as we obtained for F (z, v)

\frac{∂}{∂z} A(z, v) = A(z, v)^{2} − (1 − v) , A(0, v) = 1 ,  (95)

and this suffices to prove the theorem.

Of course this differential equation can be solved, and we get

A(z, v) = \sqrt{1 − v} − \frac{2 v \sqrt{1 − v}}{v − (1 + \sqrt{1 − v} )^{2} e^{−2\sqrt{1−v} z}} .  (96)

Therefore we can apply theorems that were proved by Devroye in [5] for the distribution of the nodes with 0, 1 and 2 children in binary search trees to the instance of p-trees. Denoting the random variables for the number of nodes with 0, 1 resp. 2 children in p-trees of size n with I_{n}^{(0)}, I_{n}^{(1)} and I_{n}^{(2)}, we get

Theorem 9.2. For the expectations 𝔼 (I_{n}^{(i)}) and the variances 𝕍 (I_{n}^{(i)}) with 0 ≤ i ≤ 2, we have the following asymptotic expansions for n → ∞

𝔼 (I_{n}^{(0)}) ∼ \frac{n}{3} , 𝔼 (I_{n}^{(1)}) ∼ \frac{n}{3} , 𝔼 (I_{n}^{(2)}) ∼ \frac{n}{3} ,

𝕍 (I_{n}^{(0)}) ∼ \frac{2}{45}n , 𝕍 (I_{n}^{(1)}) ∼ \frac{8}{45}n , 𝕍 (I_{n}^{(2)}) ∼ \frac{2}{45}n .

Furthermore the sequence of random variables

\frac{I_{n}^{(0)} − \frac{n}{3}}{\sqrt{\frac{2}{45}n}} , \frac{I_{n}^{(1)} − \frac{n}{3}}{\sqrt{\frac{8}{45}n}} and\frac{I_{n}^{(2)} − \frac{n}{3}}{\sqrt{\frac{2}{45}n}}

is for n → ∞ weakly convergent to the standard (Gaussian) normal distribution N (0, 1).

References

[1] M. Abramowitz and I. A. Stegun, editors. Handbook of Mathematical Functions. Dover Publications, Inc., New York, ninth edition, 1970.

[2] L. Bieberbach. Theorie der gewöhnlichen Differentialgleichungen. Springer Verlag, Berlin, 1965.

[3] K. L. Chung. A course in Probability Theory. Academic Press, San Diego, 1974.

[4] L. Comtet. Advanced Combinatorics. Reidel, Dordrecht, 1974.

[5] L. Devroye. Limit Laws for Local Counters in Random Binary Search Trees. Random Structures and Algorithms, 2:303–315, 1991.

[6] Ph. Flajolet and M. Soria. General combinatorial schemas: Gaussian limit distributions and exponential tails. Discrete Mathematics, 114:159–180, 1993.

[7] G. H. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Structures. Addison-Wesley, Reading, Massachusetts, second edition, 1991.

[8] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley, Reading, Massachusetts, second edition, 1994.

[9] D. H. Greene and D. E. Knuth. Mathematics for the Analysis of Algorithms. Birkhäuser, Boston, second edition, 1982.

[10] A. Jonassen and O.-J. Dahl. Analysis of an Algorithm for Priority Queue Administration. BIT, 15:409– 422, 1975.

[11] E. Kamke. Differentialgleichungen - Lösungsmethoden und Lösungen, volume 1. Teubner, Stuttgart, tenth edition, 1983.

[12] P. Kirschenhofer and H. Prodinger. Comparisons in Hoare’s Find Algorithm. to appear in Combinatorics, Probability & Computing, 1996.

[13] O. Nevalainen and J. Teuhola. The Efficiency of two indexed Priority Queue Algorithms. BIT, 18:320–333, 1978.

[14] A. Panholzer. Untersuchungen zur durchschnittlichen Gestalt gewisser Baumfamilien. Mit besonderer Berücksichtigung von Anwendungen in der Informatik. PhD thesis, Technische Universität Wien, 1997.

[15] H. Wenzel and P. Meinhold. Gewöhnliche Differentialgleichungen. Teubner, Stuttgart, 1994.

Institut für Algebra und Diskrete Mathematik, Technical University of Vienna, Wiedner Hauptstrasse 8–10, A-1040 Vienna, Austria.

E-mail address: Helmut.Prodinger@tuwien.ac.at
E-mail address: e9125354@fbma.tuwien.ac.at (Alois Panholzer)