Get new post automatically.

Enter your email address:


4.3.1 Binary Trees

The simplest form of tree is a binary tree. A binary tree consists of
  1. a node (called the root node) and
  2. left and right sub-trees.
    Both the sub-trees are themselves binary trees.

You now have a recursively defined data structure. (It is also possible to define a list recursively: can you see how?)
A binary tree
The nodes at the lowest levels of the tree (the ones with no sub-trees) are called leaves.
In an ordered binary tree,
  1. the keys of all the nodes in the left sub-tree are less than that of the root,
  2. the keys of all the nodes in the right sub-tree are greater than that of the root,
  3. the left and right sub-trees are themselves ordered binary trees.

Data Structure

The data structure for the tree implementation simply adds left and right pointers in place of the next pointer of the linked list implementation. [Load the tree struct.]
The AddToCollection method is, naturally, recursive. [Load the AddToCollection method.]
Similarly, the FindInCollection method is recursive. [Load the FindInCollection method.]

Analysis

Complete Trees

Before we look at more general cases, let's make the optimistic assumption that we've managed to fill our tree neatly, ie that each leaf is the same 'distance' from the root.








A complete tree
 This forms a complete tree, whose height is defined as the number of links from the root to the deepest leaf.
First, we need to work out how many nodes, n, we have in such a tree of height, h.
Now,

n = 1 + 21 + 22 + .... + 2h
From which we have,
n = 2h+1 - 1
and
h = floor( log2n )
Examination of the Find method shows that in the worst case, h+1 or ceiling( log2n ) comparisons are needed to find an item. This is the same as for binary search.
However, Add also requires ceiling( log2n ) comparisons to determine where to add an item. Actually adding the item takes a constant number of operations, so we say that a binary tree requires O(logn)both adding and finding an item - a considerable improvement over binary search for a dynamic structure which often requires addition of new items. operations for
Deletion is also an O(logn) operation.

General binary trees

However, in general addition of items to an ordered tree will not produce a complete tree. The worst case occurs if we add an ordered list of items to a tree. What will happen? Think before you click here!
This problem is readily overcome: we use a structure known as a heap. However, before looking at heaps, we should formalise our ideas about the complexity of algorithms by defining carefully what O(f(n)) means.


struct t_node {
    void *item;
    struct t_node *left;
    struct t_node *right;
    };

typedef struct t_node *Node;

struct t_collection {
    int size;    /* Needed by FindInCollection */
    Node root;
    };


static void AddToTree( Node *t, Node new ) {
    Node base;
    base = *t;
    /* If it's a null tree, just add it here */
    if ( base == NULL ) {
        *t = new;
        return;
        }
    else {
        if ( KeyLess( ItemKey( new->item ), ItemKey( base->item ) ) )
            {
            AddToTree( &(base->left), new );
            }
        else
            AddToTree( &(base->right), new );
        }
    }

void AddToCollection( Collection c, void *item ) {
    Node new, node_p;
    assert( c != NULL );
    assert( item != NULL );
    /* Allocate space for a node for the new item */
    new = (Node)malloc(sizeof(struct t_node));
    /* Attach the item to the node */
    new->item = item;
    new->left = new->right = (Node)0;
    AddToTree( &(c->node), new );
    }


/* Binary tree implementation of a collection */

/* Now we need to know whether one key is less, equal or greater than
   another
*/
extern int KeyCmp( void *a, void *b );
/* Returns -1, 0, 1 for a < b, a == b, a > b */


void *FindInTree( Node t, void *key ) {
    if ( t == (Node)0 ) return NULL;
    switch( KeyCmp( key, ItemKey(t->item) ) ) {
        case -1 : return FindInTree( t->left, key );   
        case 0: return t->item;
        case +1 : return FindInTree( t->right, key );
        }
    }

void *FindInCollection( collection c, void *key ) {
/* Find an item in a collection
   Pre-condition: (c is a collection created by a call to ConsCollection) &&
                  (key != NULL)
   Post-condition: returns an item identified by key if
                    one exists, otherwise returns NULL
*/
    assert( c != NULL );
    assert( key != NULL );
    /* Select node at head of list */
    return FindInTree( c->root, key );
    }



Key terms

Root Node
Node at the "top" of a tree - the one from which all operations on the tree commence. The root node may not exist (a NULL tree with no nodes in it) or have 0, 1 or 2 children in a binary tree.
Leaf Node
Node at the "bottom" of a tree - farthest from the root. Leaf nodes have no children.
Complete Tree
Tree in which each leaf is at the same distance from the root. A more precise and formal definition of a complete tree is set out later.
Height
Number of nodes which must be traversed from the root to reach a leaf of a tree.