binary trees.htm

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

      <P>In an <EM>infix</EM> traversal, the left subtree is traversed and then 
      the root is visited and finally the right subtree is traversed. </P>
      <DL>
        <DD><PRE>[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/Infix.c" target=codewindow>Infix.c</A>]
</PRE></DD></DL>
      <P>In a <EM>postorder</EM> or <EM>postfix</EM> traversal the left and 
      right subtrees are traversed and then the root is visited afterwards 
      (post). </P>
      <DL>
        <DD><PRE>[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/Postfix.c" target=codewindow>Postfix.c</A>]
</PRE></DD></DL>
      <P>This method can be used to generate postfix or <EM>reverse Polish</EM> 
      code for a stack machine. </P>
      <P>Given the following tree, formed by starting with the empty binary 
      search tree and inserting, in turn, the words, <NOBR><I>the <A 
      href="http://www.allisons.org/ll/4/LandRover/" target=_top><FONT 
      color=#000000>land</FONT></A> <A 
      href="http://www.allisons.org/ll/4/LandRover/" target=_top><FONT 
      color=#000000>rover</FONT></A> is a type of motor car,</I></NOBR> </P>
      <DL>
        <DD><PRE>
          |type------|
the-------|
          |          |rover-----|
          |          |          |of--------|
          |          |          |          |motor-----|
          |land------|
          |          |is--------|
          |          |          |          |car-------|
          |          |          |a---------|

<STRONG>Example Tree.</STRONG>

</PRE></DD></DL>
      <P>the three traversals give the following results. The results of yet 
      another method, <EM>breadth-first</EM> traversal, are included for 
      comparison; see the next section. </P>
      <DL>
        <DD><PRE>
infix:   a car is land motor of rover the type
prefix:  the land is a car rover of motor type
postfix: car a is motor of rover land type the
b-first: the land type is rover a of car motor

<STRONG>Traversals.</STRONG>

</PRE></DD></DL>
      <P>Note that the method given for printing a tree is a reversed infix 
      traversal. </P>
      <H3>Breadth-First Traversal</H3>
      <P>A <EM>breadth-first</EM> traversal of a tree starts at the root of the 
      tree. It next visits the children, then the grand-children and so on. </P>
      <DL>
        <DD><PRE>
                     1
                   .   .
                 .       .
                2         3
               . .       . .
              .   .     .   .
             4     5   6     7
            . .       .     . .
           .   .     .     .   .
          8     9   10    11   12
               .         . .
              .         .   .
             13        14   15

         <STRONG>Example: Breadth-First Order.</STRONG>

</PRE></DD></DL>
      <P>The numbers indicate the order in which the nodes are visited, not the 
      contents of the nodes. Because children are only accessible from a parent, 
      they must be stored while the parent's siblings and cousins are visited. A 
      [<A href="http://www.allisons.org/ll/AlgDS/Queue/">queue</A>] is used to 
      do this. </P>
      <DL>
        <DD><PRE>[<A href="http://www.allisons.org/ll/ProgLang/C/Queue/" target=codewindow>C/Queue</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Queue/Queue.h" target=codewindow>Queue.h</A>]
[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/QueueElement.h" target=codewindow>QueueElement.h</A>]
[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/BFirst.c" target=codewindow>BFirst.c</A>]
</PRE></DD></DL>
      <P>Note that the queue is a queue of pointer to node or a queue of tree 
      type. Initially the queue contains just the root of the tree. At each 
      iteration of the algorithm, the first element is removed from the queue. 
      Its children, if any, are pushed onto the end of the queue and the element 
      is processed. The algorithm terminates when the queue is empty. See also 
      the chapter on queues. </P>
      <H3>Recursion</H3>
      <P>Most routines on trees are recursive. This is natural because the tree 
      is a recursive data type. It is possible to write iterative versions of 
      these operations but it is harder to do so than is the case for flat lists 
      because the tree type is <EM>binary recursive</EM>. The flat list and 
      hence most of its operations are <EM>linear recursive</EM> and a linear 
      recursive routine usually has a simple iterative version. It is often 
      necessary to introduce an <EM>explicit</EM> stack into a program when 
      writing a non-recursive tree routine. This is often not worth the effort 
      as the language implementors can usually do a better job with the system 
      stack. </P>
      <P>The object-oriented programming language <A 
      href="http://www.allisons.org/ll/ProgLang/Java/">Java</A> has the notion 
      of an <CODE>Enumeration</CODE>, i.e. an iterator, which steps through the 
      elements of a set of values. An enumerator must implement the predicate 
      <CODE>hasMoreElements</CODE> and the function <CODE>nextElement</CODE>. To 
      program an enumerator which will emit the contents of a tree in one of the 
      standard orders it is useful to a employ a <CODE>Stack</CODE>: </P>
      <DL>
        <DD><PRE><A href="http://www.allisons.org/ll/AlgDS/Java/Tree/egPrefixEnum.txt" target=codewindow>[Java/Tree/egPrefixEnum.txt]</A>
</PRE></DD></DL>
      <H3>Side-Effects</H3>
      <P>The tree operations described so far have no side-effects except for 
      input, output and manipulation of dynamic storage; they are <EM>pure</EM> 
      tree operations. As is the case with lists, it is often necessary or 
      desirable to use operations having side-effects on efficiency grounds. 
      This is particularly natural if a program uses a single tree as a 
      dictionary or database structure. As before, should multiple trees share 
      components, changing one tree may change another and if this is not 
      anticipated it will cause program bugs. </P>
      <H3><A name=search>Search 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 Binary Search (&amp; AVL) Trees [<A 
            href="http://www.allisons.org/ll/AlgDS/Tree/Search/" 
            target=_top>here</A>].<BR></TD></TR></TBODY></TABLE>
      <P>A <EM>binary search tree</EM> can be created so that the elements in it 
      satisfy an ordering property. This allows elements to be searched for 
      quickly. All of the elements in the left subtree are less than the element 
      at the root which is less than all of the elements in the right subtree 
      and this property applies recursively to all the subtrees. The great 
      advantage of this is that when searching for an element, a comparison with 
      the root will either find the element or indicate which <EM>one</EM> 
      subtree to search. The ordering is an invariant property of the search 
      tree. All routines that operate on the tree can make use of it provided 
      that they also keep it holding true. </P>
      <P>It takes O(h) time to search a search tree of height h. Since a tree of 
      height `h' can hold n=2<SUP>h</SUP>-1 elements, the search takes O(log(n)) 
      time under favourable circumstances. The search-tree and its search 
      routine should be compared with the use of the binary search algorithm on 
      sorted arrays in the chapter on tables. </P>
      <P>The use of the tree speeds up the insertion and deletion operations at 
      the price of the space needed to hold the pointers. The tree has the speed 
      advantage when the data in the structure changes rapidly. </P>
      <P>The routine given here to insert an element does so as a side-effect by 
      changing the tree. </P>
      <DL>
        <DD><PRE>[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/Insert.c" target=codewindow>Insert.c</A>]
</PRE></DD></DL>
      <P>If elements are inserted in the order d, b, a, c, e, f, g the following 
      tree is created: </P>
      <DL>
        <DD><PRE>
-----------&gt;d
           . .
          .   .
         .     .
        b       e
       . .       .
      .   .       .
     a     c       f
                    .
                     .
                      g

</PRE></DD></DL>
      <P>Note that an insertion takes O(h) time. Under favourable circumstances, 
      a <EM>balanced</EM> tree is created, as for b, a, c, giving O(log(n)) 
      search time. If the input is sorted however an unbalanced tree 
      approximating a list is created, as for e, f, g, and the search 
      degenerates to an O(n) linear search. This problem is addressed later. 
</P>
      <DL>
        <DD><PRE>
input: the land rover is a type of motor car

Search Tree:

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

<STRONG>Example Search Tree.</STRONG>

</PRE></DD></DL>
      <P>A new element is added to the tree as a new peripheral, leaf node. 
      However if an element can also be deleted it is possible for it to be 
      <EM>internal</EM>. This makes deletion rather more difficult than 
      insertion. </P>
      <P>A leaf element is easily deleted by setting the pointer to it to 
      emptyTree. </P>
      <DL>
        <DD><PRE>
T:-----|                T:emptyTree
       |
       |
       v
       x

  before                 after


<STRONG>Deletion of a Leaf.</STRONG>
</PRE></DD></DL>
      <P>The node becomes garbage and can be freed. </P>
      <P>An element with one child can be deleted by by-passing it. </P>
      <DL>
        <DD><PRE>
T:------|               T:|
        |                 |
        |                 |
        v                 |
        x                 |
       . emptyTree        |
     .                    v
   e                      e
  . .                    . .
 .   .                  .   .

 before                after


<STRONG>Deletion of a Single-Child Parent.</STRONG>
</PRE></DD></DL>
      <P>An internal element x with two children cannot easily be bypassed 
      without loosing one of its subtrees. The solution is to overwrite x with 
      some other element y of the tree and then to delete the original copy of 
      y. There are two obvious elements to choose from - either the largest 
      element `A' less than x or the smallest element `B' greater than x. Each 
      of these has at most one child! The sortedness of the tree is maintained 
      if x is overwritten with either of these. </P>