Community

Upcoming Events

Unite 2010

11/10 - 11/12 @ Montréal, Canada

GDC China

12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010

12/24 - 12/27

GDC 2011

2/28 - 3/4 @ San Francisco, CA

More events...

11/10 - 11/12 @ Montréal, Canada

GDC China

12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010

12/24 - 12/27

GDC 2011

2/28 - 3/4 @ San Francisco, CA

More events...

Quick Stats

66 people currently visiting GDNet.

2406 articles in the reference section.

Help us fight cancer!

Join SETI Team GDNet!

2406 articles in the reference section.

Help us fight cancer!

Join SETI Team GDNet!

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 NotationIt is important to understand a little bit about how algorithms are rated for efficiency. Michael Abrash has said that " ) 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 complexity. Simply put, if you have O(n)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 , which is used to describe doubly nested O(n^2)for loop operations, or even or O(2^n)(n-factorial, which is O(n!) 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 and O(log n), (where O(c)c is a constant value). In , 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(c) is the most important complexity when dealing with binary trees. If you don’t know what a O(log n)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:logarithm In a 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 search function using binary trees later on. O(log n)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. |