binary trees.htm

Trees are natural structures for representing certain kinds of hierarchical data. A (rooted) tree co

      <DL>
        <DD><PRE>
T:----------|               T:-----|
            |                      |
            |                      |
            v                      v
            x                      B
          .   .                  .   .
        .       .              .       .
      L           R          L           R
     . .         . .        . .         . .
    .   .       .   .      .   .       .   .
         A     B                A     C
        .       .              .     . .
       .         .            .     .   .
                 C
                . .
               .   .

 before                    after


<STRONG>Deletion of a Two-Child Parent.</STRONG>
</PRE></DD></DL>
      <P>Both of A and B fall into one of the cases previously dealt with. A can 
      be found from x by taking one step left and then as many steps right as 
      possible. B can be found by taking one step right and then as many steps 
      left as possible. </P>
      <P>Deletion takes O(h) time. </P>
      <H4>Notes</H4>
      <UL>
        <LI>[<A href="http://www.allisons.org/ll/AlgDS/Tree/Trie/">Tries</A>] 
        and [<A href="http://www.allisons.org/ll/AlgDS/Tree/PATRICIA/">PATRICIA 
        trees</A>] are an alternatives to binary search trees. 
        <LI>The [<A href="http://www.allisons.org/ll/AlgDS/Tree/Suffix/">Suffix 
        Tree</A>] is a data-structure for solving the string searching problem. 
        </LI></UL>
      <H3><A name=AVL>Height-Balanced Trees</A></H3>
      <TABLE cellSpacing=0 cellPadding=4 width="35%" align=right border=1>
        <TBODY>
        <TR>
          <TD bgColor=#ffffff><B>Demonstration:</B> There is a demonstration 
            of AVL (&amp; bin. s.) Trees [<A 
            href="http://www.allisons.org/ll/AlgDS/Tree/Search/" 
            target=_top>here</A>].<BR></TD></TR></TBODY></TABLE>
      <P>As mentioned above, if elements are inserted into a search tree in 
      sorted order, a tree is created that is equivalent to a list. This will 
      lead to inefficient searches. A <EM>height-balanced</EM> tree or an 
      AVL-tree (after G. M. Adel'son-Velskii and E. M. Landis) is a search tree 
      in which<!-- LAllison Comp Sci --> the height of the right subtree minus 
      the height of the left subtree equals 1, 0, or -1. This property also 
      applies recursively to all subtrees. It can be shown that a 
      height-balanced tree of `n' elements has height O(log(n)) and this 
      guarantees efficient search. Fortunately fast O(log(n)) insertion and 
      deletion is still possible. </P>
      <P>A flag indicating the balance of each subtree is added to the node 
      record. </P>
      <P>There are four crucial cases during insertion. In the first case, the 
      left subtree L grows too tall on its left: </P>
      <DL>
        <DD><PRE>
        T                        L
       . .                      . .
      .   .                    .   .
     L     .     -----&gt;       .     T
    . .    |                  |    . .
   .   .   |                  |   .   .
   .   .   |                  |   .   .
   |   |                      *   |   |
   |   |                      *   |   |
   |   |                      *   |   |
   *       new elt'           rebalanced
   *       disturbs
   *       balance

<STRONG>Left-2 Rotation.</STRONG>

</PRE></DD></DL>
      <P>By rotating about L and T the height balance is restored and the 
      ordering in the tree is maintained. In the second case, L grows too tall 
      on its right: </P>
      <DL>
        <DD><PRE>
        T                      LR
      .   .                   .   .
     .     .                 .     .
    L       .               L       T
   . .      |              . .     . .
  .   .     |  ----&gt;      .   .   .   .
 .    LR    |             .   .   .   .
 |    ..    |             |   |   |   |
 |   .  .   |             |   |   |   |
 |  .    .  |             |   |   |   |
 |  |    |  |             |   |   |   |
 |  |    |  |             |   |   |   |
 |  |    |  |             |   |   |   |
 |  |    |                |   *       |
 |  |    |                |   *       |
 |  |    |                |   *       |
    *
    *
    *

<STRONG>Left-3 Rotation.</STRONG>

</PRE></DD></DL>
      <P>The rotation restores the balance while maintaining the tree ordering. 
      In the above example left(LR) grew; an alternative is that right(LR) grew 
      but the same operations still restore the balance. There are mirror-image 
      right-2 and right-3 rotations. </P>
      <P>Maintaining the balance significantly complicates the tree insertion 
      routine. However a fixed amount of work is done at each node that is 
      visited and so it takes O(h) time. </P>
      <P>Note that if a tree has just grown in height, it can only be perfectly 
      balanced if it is a single (new) leaf. Otherwise one subtree must be 
      higher than the other. </P>
      <DL>
        <DD><PRE>
input: the land rover is a type of motor car

          |          |type------|
          |the-------|
rover-----|
          |          |          |of--------|
          |          |motor-----|
          |          |          |land------|
          |is--------|
          |          |          |car-------|
          |          |a---------|

    <STRONG>Height-Balanced Tree.</STRONG>

</PRE></DD></DL>
      <P>Compare this with the tree given earlier and created by the 
      non-balancing insert. </P>
      <H4>Notes</H4>
      <UL>
        <LI>G. M. Adelson-Velskii and E. M. Landis [AVL]. An algorithm for the 
        organization of information. Soviet Math. Dokl. <B>3</B>, p1259-1263, 
        1962. 
        <LI>N. Wirth. <I>Algorithms and Data Structures.</I> p218, 
        Prentice-Hall, 1986.<BR><FONT size=-1>AVL-tree insertion and 
        deletion.</FONT> 
        <LI>M. A. Weiss. <I>Data Structures and Algorithm Analysis in C</I>. 
        s4.4, pp110. Addison Wesley 1997. </LI></UL>
      <H3>Implementation of Binary Trees by Arrays</H3>
      <P>A binary tree can be implemented as an array of records. </P>
      <DL>
        <DD><PRE>
type TreeT :0..nmax

var Tree: array 1..nmax of
   record elt :Element_Type
          left, right :TreeT
   end record

</PRE></DD></DL>
      <P>The empty tree is represented by zero. Left and right are indexes to 
      left and right subtrees. </P>
      <P>This implementation has no advantage in a language supporting dynamic 
      storage unless random access to nodes is also needed. It is useful in a 
      language without dynamic storage. </P>
      <H3>Full Trees by Arrays</H3>
      <P>It is possible to define a <EM>full</EM> or <EM>weight balanced</EM> 
      tree in contrast to a height balanced tree. The empty tree is a full tree 
      of zero levels. If T and T' are full binary trees of n levels then 
      fork(e,T,T') is a full binary tree of n+1 levels. </P>
      <DL>
        <DD><PRE>
           1
          . .
         .   .
        .     .
       .       .
      2         3
     . .       . .
    .   .     .   .
   4     5   6     7

<STRONG>Full Binary Tree of 3 Levels.</STRONG>

</PRE></DD></DL>
      <P>The numbering of the nodes corresponds to a breadth-first traversal. 
      This suggests that such a tree can be stored in an array: </P>
      <DL>
        <DD><PRE>
const n = 2**Levels - 1

array 1..n of Element_Type

</PRE></DD></DL>
      <DL>
        <DD><PRE>
type tree = 0..n

empty(T)   = T=0
left(T)   = 2*T
right(T)  = 2*T+1
parent(T) = T div 2
leaf(T)   = T &gt;= 2**(Levels-1)

</PRE></DD></DL>
      <P>Such an implementation is very efficient indeed, if the tree is full, 
      because no space at all is used for pointers. See the chapter on sorting 
      for an application of this technique in [<A 
      href="http://www.allisons.org/ll/AlgDS/Sort/Heap/">heap-sort</A>]. </P>
      <H3>Testing and Debugging</H3>
      <P>Programming techniques for trees share a great deal in common with 
      those for lists. Pre and post conditions and assertions should be included 
      where possible. Minimise the use of side-effects in general and the 
      manipulation of global variables in particular. </P>
      <P>Note that there are really just two kinds of tree - emptyTree and 
      non-emptyTree. Most operations on a tree follow this pattern: </P>
      <DL>
        <DD><PRE>
f(emptyTree) = ... |
f(fork(e,T,T')) = ...often f(T)...f(T')...

</PRE></DD></DL>
      <P>If a case is missing it probably indicates an error. The empty case is 
      usually very simple, often returning a constant. The main case often 
      operates on one or both subtrees recursively. </P>
      <P>When testing or debugging a tree routine, test cases should cover the 
      above options. For non-emptyTree trees, it may be appropriate to try a 
      tree of a "few" nodes and a tree of a single node. As usual it is 
      invaluable to write the output routine first. The most common problems 
      are: . unassigned pointers, particularly those that should be emptyTree, . 
      lost pointer values through a wrong ordering of operations, . knotted 
      pointers maybe introducing a cycle, . side-effects through shared 
      pointers, intentional or otherwise. </P>
      <P>The coding of reasonably complex routines such as those on AVL trees is 
      prone to small typographical errors. Nothing can beat careful proof 
      reading but one good testing trick is to use a set of ascending data and 
      then its reversal in which case the mirror image tree should be produced. 
      This test is not sufficient on its own! It is important to exercise all 
      the paths through a complex routine and this requires a great deal of