Contents  Algorithm Analysis  Binary Trees  Binary Search Trees  Non-recursive methods  Source code  Printable version  Discuss this article  in the forums The Series  Introduction  Binary Trees

I was talking to some people about ideas for this article, and when I proposed that it be about simple binary trees, someone said that games have no need for these, and that I should do something closer to game programming, such as BSP trees. I beg to differ here, actually. While the beginner may think that game programming is all about graphics, they are leaving out a critical part of the equation. Games these days are becoming incredibly large, and long dead are the days when a single hacker can throw together a game. It takes engineering skills and discipline, and most of all, an understanding in the basic concepts of data structures. Without knowing what data structures exist, and what they can do, how can anyone ever hope to make a large complex world that doesn’t choke the current line of computers? I feel that leaning about the basic data structures that have been developed and tested ever since computers were invented is an essential part of game programming. Indeed, what good is a carpenter who does not know how to use his tools? And now, without further ado, I give you part II of the Tree’s series.

Last time, we discussed recursion and the basic structure of trees. Now, I would like to get into an important sub-section of hierarchal data structures: Binary Trees. We all (hopefully) know that computers are binary machines, so it makes quite a bit of sense that the most frequently used kind of tree in computer programming is a binary tree. A Binary Tree is simply a tree in which every node has a maximum two children. Binary trees can be used for many things, such as efficient searching, arithmetic expression parsing, and data compression, etc. Before we get into the details, there are a few terms and definitions that need to be explained.

Algorithm Analysis and Big-O Notation

It is important to understand a little bit about how algorithms are rated for efficiency. Michael Abrash has said that "Without good design, good algorithms, and complete understanding of the program’s operation, your carefully optimized code will amount to one of mankinds least fruitful creations - a fast slow program," and he is absolutely correct. You can write the fastest code around, but if your algorithm is inherently slow, nothing will make it efficient. Big-O is a measure of the worst-case scenario (or complexity) of any given algorithm, as the size of the data set increases. It typically consists of an algebraic statement that represents the speed of the algorithm based on the size of the data it operates on. The Big-O of a sequential linked list search, for example, is O(n). Simply put, if you have n items, the worst case is that you would need to search through every item in the list, resulting in n comparisons. There are other Big-O cases, such as O(n^2), which is used to describe doubly nested for loop operations, or even O(2^n) or O(n!) (n-factorial, which is n*n-1*n-2*...3*2*1), which describe algorithms which take immense amounts of time to complete. The other two important worst-case scenarios are O(log n) and O(c), (where c is a constant value). In O(c), the algorithm completion time always takes the same amount of time to complete, no matter what size the data set is. This is used frequently to represent constant time algorithms, such as hash table lookups. O(log n) is the most important complexity when dealing with binary trees. If you don’t know what a logarithm is, don’t worry, it is not essential to the understanding of binary trees. All you need to know is what the graph of a logarithmic function looks like this:

In a base-2 logarithm, the y part of the graph only goes up by one whole integer every time the number of items in the data set (n) is doubled. If an algorithm can attain this level of complexity, it is usually considered pretty efficient. I will show you how to make an O(log n) search function using binary trees later on. Note: I have only dealt with base-2 logarithms here. Logarithms can exist for any base number, but they are not important in this article.

Next : Binary Trees