Select Git revision
-
Martin Mareš authoredMartin Mareš authored
abtree.tex 17.30 KiB
\ifx\chapter\undefined
\input adsmac.tex
\singlechapter{3}
\fi
\chapter[abtree]{(a,b)-trees}
In this chapter, we will study an extension of binary search trees.
It will store multiple keys per node, so the nodes will have more than
two children. The structure of such trees will be more complex, but we
will gain much more straightforward balancing operations.
\section{Definition and operations}
\defn{
A~\df{multi-way search tree} is a~rooted tree with specified order
of children in every node. Nodes are divided to internal and external.
Each~\em{internal node} contains one or more distinct keys, stored in
increasing order. A~node with keys $x_1 < \ldots < x_k$ has $k+1$ children
$s_0,\ldots,s_k$. The keys in the node separate keys in the corresponding
subtrees. More formally, if we extend the keys by sentinels $x_0=-\infty$ and
$x_{k+1}=+\infty$, every key~$y$ in the subtree $T(s_i)$ satisfies $x_i < y < x_{i+1}$.
\em{External nodes} carry no data and they have no children. These are the
leaves of the tree. In a~program, we can represent them by null pointers.
}
\obs{
Searching in multi-way trees is similar to binary trees. We start at the root.
In each node, we compare the desired key with all keys of the node. Then we either
finish or continue in a~uniquely determined subtree. When we reach an external node,
we conclude that the requested key is not present.
The universe is split to open intervals by the keys of the tree. There is a~1-to-1
correspondence between these intervals and external nodes of the tree. This means
that searches for all keys from the same interval end in the same extrnal node.
}
As in binary search trees, multiway-trees can become degenerate. We therefore need
to add further invariants to keep the trees balanced.
\defn{
An~\em{(a,b)-tree} for parameters $a\ge 2$ and $b\ge 2a-1$ is a~multi-way
search tree, which satisfies:
\tightlist{n.}
\:The root has between 2 and~$b$ children (unless it is a~leaf, which happens
when the set of keys is empty). Every other internal node
has between $a$ and~$b$ children.
\:All external nodes have the same depth.
\endlist
}
The requirements on $a$ and~$b$ may seem mysterious, but they will become
clear when we define operations.
The minimum working type of $(a,b)$-trees are $(2,3)$-trees --- see
figure~\figref{abexample} for examples. Internal nodes are drawn round,
external nodes are square.
\figure[abexample]{ab-example.pdf}{}{Two $(2,3)$-trees for the same set of keys}
Unlike in other texts, we will \em{not} assume that $a$ and~$b$ are constants,
which can be hidden in the~$\O$. This will help us to examine how the performance
of the structure depends on these parameters.
We will start with bounding the height of $(a,b)$-trees. Height will be measured
in edges, a~tree of height~$h$ has the root at depth~0 and external nodes at depth~$h$.
We will call the set of nodes at depth~$i$ the $i$-th \em{level.}
\lemma{