Binary Tree
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:
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) } }
