\input  CS445Hdr.tex
\begfile{Fringe.tex of December 16, 1982  12:30 AM - Stolfi}
\def\rtitle{}
\def\ltitle{}
\def\header{}
\vskip 15mm
\ctrline{{\:= Remarks on the paper}}
\ctrline{{\:= ``The analysis of a fringe heuristic for binary search trees''}}
\ctrline{{\:< of P. V. Poblete and I. J. Munro}}
\vskip 15mm

\def\pin{\par\hangindent 20pt after0 }

\def\lg{\mathop{\hbox{lg}}}

\def\ctrfmt{\ctr{$ ## $}}
\def\kr{\cr }
\def\hhal{\halign}

\def\reploop{\xdef\accum{\accum\ctrfmt}\advcount4 by-1\ifpos4{\xdef\accum{\accum\hskip7pt |}\reploop}\else{\xdef\accum{\accum\kr}}}

\def\matrix#1#2{\setcount4 #1\xdef\accum{}\reploop\xdef\accum{\hhal{\accum #2}}\left(\vcenter{\accum}\right)}

\sect{Page 2}

{\:O  Line 3 of sec. 2:} {\it Replace} ... that a $k$ comparisons... {\it by} ... that $k$ comparisons...\par

{\:O  Next-to-last paragraph:} (For naively formed...)
\pin I feel it would be better to combine this paragraph with the
first one on page 6, perhaps presenting the results as a table
$$\halign{\hskip2cm\ctr{#}|\hskip0.7cm\rt{#}|\hskip0.7cm\rt{#}\cr
\ |\hbox{Naive}|\hbox{Heuristic}\cr
$C
N$|$\approx ?\lg n$|$\approx 1.19\lg n$\cr
$V
N$|$\approx 1.4\lg n$|$\approx .6\lg n$\cr}$$
\pin In any case, the numerical value of 2ln2 should be given, to make the comparison between $C
N$ and $C
N\pr$ clear.

\sect{Page 3}

{\:O  Second paragraph:} (For the usual...)
\pin The definition of types A, B and C is obscure (what is a ``single node''?).

{\:O  Third paragraph onwards:} 

\pin I believe the exposition could be shortened a little bit by a change in notation. Call the trees of fig 2 (and their mirror images) {\it 2-bags} or {\it 3-bags}, according to the number of external nodes in them. Therefore, a tree constructed using the fringe heuristic (with $n\geq 2$) can be seen as a binary search tree whose external nodes have been replaced by such bags. 

\pin Let $F
{nk}$ and $G
{nk}$ be respectively the average number of 2-bags and 3-bags whose root is at level $k$ of the tree. Then
$$\eqalign{P
{nk}|= {1\over n}(2F
{n, k-1} + G
{n, k-1} + 2G
{n, k-2})\quad\forall k\geq1, \forall n\geq2\cr\vc
G
{2,k}|=0\quad\forall k\cr\va
F
{2,0}|=1\cr\va
F
{2,k}|=0\quad\forall k\neq0\cr}$$

\pin The probabilities of inserting a new node in a 2-bag and a 3-bag rooted at level $k$ are respectively ${2\over n}F
{nk}$ and ${3\over n}G
{nk}$. Upon insertion, the first becomes a 3-bag at level $k$, and the second becomes two 2-bags at level $k+1$. Therefore, 
$$\eqalign{F
{n+1,k}|=(1-{2\over n})F
{nk}+2{3\over n}G
{n,k-1}\cr\vc
G
{n+1,k}|=(1-{3\over n})G
{nk}+{2\over n}F
{nk}\cr}$$
or
$$\eqalign{F
{n+1}(z)|=(1-{2\over n})F
{n}(z)+2z{3\over n}G
{n}(z)\cr\vc
G
{n+1}(z)|={2\over n}F
{n}(z)+(1-{3\over n})G
{n}(z)\cr}$$
\pin So, in matrix form
$$\matrix1{F
{n+1}(z)\cr\va G
{n+1}(z)\cr}=\biglp I - {1\over n}\matrix2{-2|2z\cdot 3\cr\va 2 | -3\cr}\bigrp\matrix1{F
n(z)\cr\va G
n(z)\cr}$$

\pin The eigenvalues of the matrix above are 
$${-5\pm\sqrt{1+48z}}\over2$$The rest of the derivation proceeds as in the paper.

\pin I feel that with the notation above the extension to the case of larger bags is more immediate, and it allows also ``non-tree'' bags (see comments about page 8).

\sect{Page 6}

{\:O  Line 2:} {\it Replace} thees {\it by} trees

{\:O  Second paragraph:} perhaps make a separate subsection, ``Worst-case behavior''.

\sect{Page 7}

{\:O  Next-to-last paragraph onwards:} (How the elements...)

\pin The bags do not even have to be represented as trees. For example, a bag may be stored as a linear array (sorted or unsorted) with space for $2t-2$ keys; this may be simpler and/or faster and/or more space-effective, at least for small $t$s. Note that schema 8a requires extensive reorganization at each insertion, and both 8a and 8b waste a lot of space in null pointers.

\sect{Page 8}

{\:O  Line 4 after figure:} {\it Replace}
\pin ...and by $[e
0↑{(j)}, e
1↑{(j)}, \ldots]$ its number of external nodes in each level, starting from the bottom.
\pin {\it by}
\pin  ... and by $\bar e↑{(j)}=[e
0↑{(j)}, e
1↑{(j)}, \ldots]$ the number of external nodes in each level of $T
j$, starting from the bottom.

{\:O  Second paragraph:} {\it Replace}
\pin $h↑{(3)}=3$; $[2, 1, 0]$
\pin {\it by}
\pin $h↑{(3)}=3$; $\quad\bar e↑{(3)}=[2, 1, 0]$
\pin {\it and so forth on all examples}.

{\:O  Third paragraph onwards:}

\pin The notation proposed for section 2 can be extended to the general case, providing some simplification of the formulas and replacing the matrix $H(z)$ by one with a significantly simpler structure. Furthermore, the analysis becomes almost independent of the structure of the bags, so it can be applied also to hybrid trees like the one suggested above.

\def\j{↑{(j)}}
\pin Define a $j$-bag ($t\leq j < 2t$) as a fringe subset containing $j$ external nodes. Let $F
{nk}\j$ be the number of $j$-bags whose root is at level $k$ of the tree. Let $X
r\j$ be the number of external nodes in a $j$-bag which are at level $r$ from the root of the bag. (In your notation, $X
r\j=e
{h\j-r}\j$ and $F
{nk}\j=nA
{n,k+h\j}\j/e
0\j$. The definitions of $\bar e\j$ and $h\j$ can be omitted.) Then the probability that an external node is in a $j$-bag rooted at level $k$ is ${j\over n}F
{nk}\j$; the probability that an external node is in level $k$ in the whole tree is 
$$\eqalign{P
{nk}|=\sum
{t\leq j<2t}\sum
r {j\over n}F
{n,k-r}\j\, {1\over j}X
r\j\cr\vc
\null|={1\over n}\sum
{t\leq j<2t}\sum
r F
{n,k-r}\j\, X
r\j\cr}$$
Then
$$P
{n}(z)={1\over n}\sum
{t\leq j<2t}F
{n}\j(z)\,X\j(z)$$
or
$$P
n(z)=\matrix4{X↑{(t)}(z)|X↑{(t+1)}(z)|\cdots|X↑{(2t-1)}(z)\cr}\,\,{1\over n}\,\,\matrix1{F
n↑{(t)}(z)\cr F
n↑{(t+1)}(z)\cr \vdots \cr F
n↑{(2t-1)}(z)\cr}$$
When a new node is inserted, a $j$-bag at level $k$ becomes a $(j+1)$ bag at the same level, except that a $(2t-1)$-bag becomes two $t$-bags at level $k+1$. So,
$$\eqalign{F
t\j(z)|=0\quad\forall j\neq t\cr\vb
F
t↑{(t)}(z)|=1\cr\vb
F
{n+1}↑{(t)}(z)|=\biglp 1-{t\over n} \bigrp F
n(z)↑{(t)} + 2z{{2t-1}\over n}F
n↑{(2t-1)}(z)\quad\quad\forall n>t,\forall k\geq0\cr\vb
F
{n+1}\j(z)|=\biglp 1-{j\over n} \bigrp F
n(z)\j + {{j-1}\over n}F
n↑{(j-1)}(z)\quad\quad\forall n>t, \forall k\geq0, \forall j \relv t<j<2t\cr}$$

\pin In matrix form
$${\baselineskip18pt\matrix1{F
{n+1}↑{(t)}(z)\cr F
{n+1}↑{(t+1)}(z)\cr \vdots \cr F
{n+1}↑{(2t-1)}(z)\cr}}=\biglp I + {1\over n}{\baselineskip18pt\matrix5{-t|0|0|\cdots|(2t-1)\cdot 2z\cr
t|-(t+1)|0|\cdots|0\cr
0|t+1|-(t+2)|\cdots|0\cr
\null|\vdots|\null|\null|\vdots\cr
0|0|0|\cdots|-(2t-1)\cr}}\bigrp\,\,{\baselineskip18pt\matrix1{F
n↑{(t)}(z)\cr\vc F
n↑{(t+1)}(z)\cr \vdots \cr F
n↑{(2t-1)}(z)\cr}}$$

\pin The characteristic polynomial of the matrix above is the basically the same as that of $H(z)$, so the rest of the analysis goes through essentially unchanged. The matrix above has a simple structure, so its eigenvectors may be easier to compute than those of $H(z)$.

\sect{Page 9}

{\:O  Lemma 3.1:} {\it Insert a} ``$z$''  {\it after the term} ``$(2t)$''.

\par\vfill\eject\end