Skip to content
Snippets Groups Projects
Select Git revision
  • 5e3a7d776df99af523b92bd14ecfcb6914e505cb
  • master default protected
  • jiri-skrobanek/persistence
  • om-graphs
  • vk-dynamic
  • fs-succinct
  • pm-streaming
7 results

abtree.tex

Blame
  • 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{