Web developers notes,programming tutorials.

About binary trees

Say you have a list or array holding N numbers of elements, and want to search for a specific element. You then have to go through (aka traverse) each element one by one until you find it (or find out that it is not in the list).

The worst case (if the element is last in the list, or isn’t there at all) you’d have to make N comparisons, which can be quite a treat if the list/array is VeryVeryBig(tm).

By having the elements stored in a tree rather a list you get some key benefits:

• Faster search (don’t have to compare with all elements)
• Elements are automatically sorted as they are added

How does it work then

In a linked list you have a line of elements, each elements pointing to the next:
Fig. 1. A linked list

In a binary tree, each element instead point to two other elements, one “down to the left” (left child) and one “down to the right” (right child).
The left child’s key value is less than its parent’s, and the right child’s key value is greater than or equal than its parent’s:

Fig. 2. A binary tree

Thanks to this, can you fairly easy decide where to search (and where to not search) for a particular element.
If the current node doesn’t match the search criteria, query the left or the right child, depending of wheter the search criteria is < or >= than current node’s key value.

Sorting

Since all elements are stored according to their key values, you can easily retrieve them in an ordered (or reversed) manner. Oh, and when working with trees, you really see the benefits of using recursion…Example of printing the elements in order:

  PrintElement(pTopMostElement)
.
.
void PrintElement(TreeElement* pElement)
{
if (pElement)
{
PrintElement(pElement->LeftChild)
pElement->PrintMe()
PrintElement(pElement->RightChild)
}
}

Example of printing the elements in reversed order:

  PrintElementReversed(pTopMostElement)
.
.
void PrintElementReversed(TreeElement* pElement)
{
if (pElement)
{
PrintElementReversed(pElement->RightChild)
pElement->PrintMe()
PrintElementReversed(pElement->LeftChild)
}
}

This entry was posted on Monday, February 26th, 2007 at 10:23 am and is filed under c++ programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.