Tricks of the Windows Game Programming Gurus:Algorithms, Data Structures, Memory Management, and Multithreading

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

### Trees

The next class of advanced data structures, trees, are processed by recursive algorithms, so that’s why I took the preceding detour. Anyway, take a look at Figure 11.6 to see a number of different tree-like data structures.

Figure 11.6 Some tree topologies.

Trees were invented to help with the storage and searching of large amounts of data. The most popular kind of tree is the binary tree, AKA B-tree or BST (Binary Search Tree), a tree data structure emanating from a single root that is composed of a collection of nodes. Each node has one or two children nodes (siblings) descending from it; hence the term binary. Moreover, we can talk of the order or number of levels of a tree, meaning how many layers it has. The B-trees in Figure 11.7 are shown with their various orders.

Figure 11.7 Some binary trees and their orders.

The interesting thing about trees is how fast the information can be searched. Most B-trees use a single search key to order the data. Then a searching algorithm searches the tree for the data. For example, say you wanted to create a B-tree that contained records of game objects, each with a number of properties. You could use the time of creation as the key, or you could make each node represent a person in a database. Here’s the data structure that you would use to hold a single person node:

    typedef struct TNODE_TYP

       {

       int age;         // age of person

       char name[32];   // name of person

       NODE_TYP *right; // link to right node

       NODE_TYP *left;  // link to left node

       } TNODE, *TNODE_PTR;

> Note: Of course, the data in this example can be anything you want.

Notice the similarity between the tree node and the linked list node! The only difference is the way you use the data structure and build up the tree. Continuing with the example, let’s say that you have five objects (people) with the following ages: 5, 25, 3, 12, and 10. Figure 11.8 depicts two different B-trees that contain this data. However, there are more you could create that would maintain the properties of a B-tree depending on the order that the data is presented to the insertion algorithm.

Figure 11.8 B-tree encoding of data set age{5,25,3,12,10}.

Notice that I have used the convention that any right child is greater than or equal to its parent and any left child is less than its parent. You can use a different convention, as long as you stick to it.

Binary trees can hold enormous amounts of data, and that data can be searched very quickly with a binary search. This is a manifestation of the binary structure of the tree. For example, if you have a tree with one million nodes, at most it will take about 20 comparisons to find the data! Is that crazy or what? The reason for this is that during each iteration of your search, you cut half the nodes out of the search space. Basically, if there are `n` nodes, the average search will take `log2 n`; the run-time is `O(log2 n)`.

> Note: The statement about search time is only true for balanced trees—trees that have an equal number of right and left children per level. If a tree is unbalanced, it degrades into a linked list and search time degrades into a linear function.

The next cool thing about B-trees is that if you take a branch (sub-tree) and process it separately, it maintains the properties of a B-tree. Hence, if you know where to look, you can search a sub-tree just for whatever it is you’re looking for. Thus, you can create trees of trees or index tables that contain sub-trees so you don’t need to process the whole tree. This is important in 3D world modeling. You might have one large tree of the entire world, but there are hundreds of sub-trees that represent rooms in the world. Thus, you might have yet another tree that represents a spatially sorted list of pointers into the sub-trees, as shown in Figure 11.9. More on this later in the book…

Figure 11.9 Using a secondary index table on a B-tree.

Finally, let’s address when to use trees. I suggest using tree-like structures when the problem or data is tree-like to begin with. If you find yourself drawing out the problem and you see branches to the left and right, a tree is definitely for you.

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.