\documentclass[twocolumn]{article}
\title{The Dynamic Binary search tree}
\author{}
\begin{document}
\maketitle
\section{Introduction}
Binary trees are an important data organization in which searching for
an element is performed in $O(\log{n})$ steps. Dynamic trees were new
elements can be added and removed may become unbalanced and thus more
sophisticated binary tree implementations have been suggested to keep
the tree in $O(\log{n})$ limits.
Our goal is controlling the height of a tree to small values. A balanced
tree fulfills this goal but a tree need not necessarily be balanced to have
its height controlled.
The algorithm for an efficient implementation of dynamic tree is described,
along with comparisons with existing dynamic tree implementations.
\section{Description of the tree}
The basic idea is using a simple binary search tree and setting a limit on
it's height. Let us use for the rest of this study the number 32 as height
limit. This restricts the total number of nodes to no more than $2^{32}$ as
long as duplicate elements are not allowed.
We should notice that due to the logarithmic nature of complexity,
in real-life applications a balanced tree will never reach such values for
it's height.
Supposing we can efficiently fulfill this condition, locating an element in
the tree will be performed in no more than 32 steps. Typically
$O(32)data, n->data) > 0)
if (np->less == n) break;
else np = np->less;
else
if (np->more == n) break;
else np = np->more;
if (!(n->less && n->more))
{
if (isroot) root = (n->less) ? n->less : n->more;
else
if (np->less == n) np->less = (n->less) ? n->less : n->more;
else np->more = (n->less) ? n->less : n->more;
return;
}
for (i = 0, nlp = NULL, nl = n->less; nl->more; i++)
nlp = nl, nl = nl->more;
for (j = 0, nrp = NULL, nr = n->more; nr->less; j++)
nrp = nr, nr = nr->less;
if (i >= j)
{
if (isroot) root = nl;
else
if (np->less == n) np->less = nl;
else np->more = nl;
if (nlp)
{
nlp->more = nl->less
nl->less = n->less;
}
nl->more = n->more;
} else {
if (isroot) root = nr;
else
if (np->less == n) np->less = nr;
else np->more = nr;
if (nrp)
{
nrp->less = nr->more
nr->more = n->more;
}
nr->less = n->less;
}
}
\end{verbatim}
\subsection{Balancing}
\label{code:balance}
The algorithm for reconstructing a balanced tree.
{\tt alloca} is a stack allocation mechanism.
Special care should be taken that the variables {\tt i, j, D, k} in
{\tt balance()} are 64 bit integers. If not then the algorithm will fail for
trees with more than about 65000 nodes.
\begin{verbatim}
unsigned int suint;
node **snpp;
void count_nodes (node *n)
{
++suint;
if (n->less) count_nodes (n->less);
if (n->more) count_nodes (n->more);
}
void tree_to_array (node *n)
{
if (!n) return;
tree_to_array (n->less);
*snpp++ = n;
tree_to_array (n->more);
}
void balance ()
{
node **npp;
long int i, j, D, k, k2, k3;
/** Generate a sorted array **/
suint = 0;
count_nodes (root);
npp = snpp = (node**) alloca (sizeof (node*) * suint);
tree_to_array (root);
/** Insert the top 2^k -1 nodes **/
root = npp [suint / 2];
for (i = 4; i <= suint + 1; i *= 2)
for (j = 2; j < i; j += 4)
{
k2 = suint * j / i;
npp [k2]->less = npp [suint * (j - 1) / i];
npp [k2]->more = npp [suint * (j + 1) / i];
}
/** Test whether there are nodes left **/
if ((k = suint + 1 - i / 2)) == 0)
{
for (i /= 2, j = 1; j < i; j += 2)
k2 = suint * j / i,
npp [k2]->less = npp [k2]->more = NULL;
return;
}
/** Proceed normally but for specific nodes **/
for (j = 2; j < i; j += 4)
{
k3 = suint * j / i;
D = (k2 = suint * (j - 1) / i) * (i / 2) % suint;
if (D >= k || D == 0) /* k2 Excluded */
npp [k3]->less = NULL;
else { /* k2 Inserted */
npp [k3]->less = npp [k2];
npp [k2]->less = npp [k2]->more = NULL;
}
D = (k2 = suint * (j + 1) / i) * (i / 2) % suint;
if (D >= k || D == 0)
npp [k3]->more = NULL;
else {
npp [k3]->more = npp [k2];
npp [k2]->less = npp [k2]->more = NULL;
}
}
insert (npp [0]);
}
\end{verbatim}
\subsection{Inserting a node}
The procedure is similar to that of a simple binary search tree.
\begin{verbatim}
int insert (node *n)
{
node *np;
int h;
n->less = n->more = NULL;
if (!(np = root))
{
root = n;
return 0;
}
for (h = 0;; h++)
if (compare (np->data, n->data) > 0)
if (!np->less) { np->less = n; break; }
else np = np->less;
else
if (!np->more) { np->more = n; break; }
else np = np->more;
if (h == MAX_HEIGHT)
{
balance ();
return 0;
} else if (h > MAX_HEIGHT) {
// If that ever happens please send me a mail and I'll send
// you 10.000$ for having a tree with 4bill nodes
// or make MAX_HEIGHT 34 and go to 16bills
printf ("Tree full. Reached 2^%i nodes\n", MAX_HEIGHT);
return -1;
}
return h;
}
\end{verbatim}
\end{document}