John F. Bergin
Bellevue, WA
(425) 242-1394
John.F.Bergin@Comcast.net Resume
Word Formatted Resume (Right Click and "Save Target As")
Cover Letter White Papers Code Examples
Senior
Software Engineer
Code Examples by John F. Bergin
The Binary Tree
The following code demonstrates the use of Binary Trees. For this example, a database of records describing different dictionary words is
created using a Binary Tree. Each record will contain the word and a definition of the word.
The following structure is used to hold the Binary Tree data:
public struct WordNode
{
char *Word;
char *Definition;
WordNode *LeftNode;
WordNode *RightNode;
};
The structure contains character pointers for the word and definition, and "node" pointers to the left and right child nodes. The following
figure graphically illustrates a "Balanced" Binary Tree:
Figure 1 - A "Balanced" Binary Tree
The main benefit of the Binary Tree is fast search times (provided the tree is balanced). In the above illustration, you would only need
to check 3 nodes to find any particular record. In a balanced Binary Tree, you can eliminate half of the child nodes with each record
checked, so the Big-O performance analysis for searching a Binary Tree is log2(N), where N is the total number of records. For the
tree illustrated above with 7 records, log2(7) equals approximately 3. For a tree with a billion records, only about 30 nodes need to
be checked!
Aside from the Big-O analysis, Binary Trees are good for demonstrating the use of recursion, where a program calls itself a number of
times. The following code uses recursion to search a Binary Tree:
// Lookup a Word in the Binary Tree
static WordNode *LookupWord(char Word[25], WordNode *lookupNode){
WordNode *CurrentNode = new WordNode;
int strCompare = strcmp(lookupNode->Word, Word);
if ( strCompare > 0 )
{
if ( lookupNode->LeftNode != NULL )
{
CurrentNode = lookupNode->LeftNode;
lookupNode = LookupWord(Word, CurrentNode);
}
else
{
CurrentNode->Definition = "***Word Not Found***";
return CurrentNode;
}
}
else if ( strCompare < 0 )
{
if ( lookupNode->RightNode != NULL )
{
CurrentNode = lookupNode->RightNode;
lookupNode = LookupWord(Word, CurrentNode);
}
else
{
CurrentNode->Definition = "***Word Not Found***";
return CurrentNode;
}
}
return lookupNode;
}
Recursion can also be used to insert records into the Binary Tree:
// Insert a Word record into the Binary Tree
static bool InsertWord(char Word[25], char Definition[100], WordNode *rootNode){
// Check node's word
int strCompare = strcmp(rootNode->Word, Word);if ( strCompare == 0 )
{
// Word already in tree
return 1;}
else if ( strCompare > 0 )
{
//Try to add to left node
if ( rootNode->LeftNode == NULL ){
// Add it here
WordNode *NewNode = new WordNode;
NewNode->Word = Word;
NewNode->Definition = Definition;
NewNode->LeftNode = NULL;
NewNode->RightNode = NULL;
rootNode->LeftNode = NewNode;
return 0;
}
else
{
// Try to add to lower node
return InsertWord( Word, Definition, rootNode->LeftNode );}
}
else if ( strCompare < 0 )
{
//Try to add to right node
if ( rootNode->RightNode == NULL ){
// Add it here
WordNode *NewNode = new WordNode;
NewNode->Word = Word;
NewNode->Definition = Definition;
NewNode->LeftNode = NULL;
NewNode->RightNode = NULL;
rootNode->RightNode = NewNode;
return 0;
}
else
{
// Try to add to lower node
return InsertWord( Word, Definition, rootNode->RightNode );}
}
return 0;
}
Test the Code
The following Test Window shows the results of a program that builds and tests a Binary Tree using the code samples from above:
The reason Binary Tree's are not a good choice for practical use is because all of the perceived benefits assume a "balanced" tree, where
there are as many child nodes on the left of each node as there are on the right. Given the tree shown in Figure 1, and using the code samples
from above, adding the following records in the order listed will produce the tree shown in Figure 2:
Jet - A fast plane.
Ice - Frozen water
Hard - Not soft.
Figure 2 - An "Un-Balanced" Binary Tree
As seen in Figure 2, a search for the word "Hard" would entail checking 6 nodes, which is almost double the advertised log2(N) search time.
It gets worse, as a completely "Un-Balanced" tree is in fact a "Linked List", whose Big-O performance analysis for searching is N. As the
tree becomes more and more unbalanced, the Big-O performance for searching the un-balanced Binary Tree approaches N.
The reason why Binary Trees are rarely used in practice is ultimately a maintenance issue. To achieve the benefits of the Binary Tree, and additional
process to balance the tree is needed (this process is inherently unnecessary with a Linked List). The Big-O performance analysis of the process
of balancing a Binary Tree is N2! By the rules of Big-O analysis, the overall performance of the Binary Tree system is N2. Therefore, Binary Trees
ultimately require more maintenance in exchange for worse overall performance.
____________________________
Copyright © 2010 by John F. Bergin.