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

#### Searching BSTs

Once the BST is generated, searching it is a snap. However, this is where you need to use a lot of recursion, so watch out, dog. There are three ways to search a BST:

  • Preorder—Visit the node, search the left sub-tree preorder, and then search the right sub-tree preorder.
  • Inorder—Search the left sub-tree in order, visit the node, and then search the right-sub tree in order.
  • Postorder—Search the left sub-tree postorder, search the right sub-tree postorder, and then visit the node.

> Note: Right and left are arbitrary; the point is the order of visiting and searching.

Take a look at Figure 11.11. It shows a basic tree and the three search orders.

Figure 11.11 The order of node visitation for preorder, inorder, and postorder searches.

With that in mind, you can write very simple recursive algorithms to perform the traversals. Of course, the point of traversing a BST is to find something and return it. However, the following function just performs the traversals. You could add stopping code to the functions to stop them when they found a desired key; nevertheless, the way you search for the key is what you’re interested in at this point:

    void BST_Inorder_Search(TNODE_PTR root)

    {

    // this searches a BST using the inorder search

    // test for NULL

    if (!root)

       return;

    // traverse left tree

    BST_Inorder_Search(root->left);

    // visit the node

    print("name: %s, age: %d", root->name, root->age);

    // traverse the right tree

    BST_Inorder_Search(root->right);

    } // end BST_Inorder_Search

And here’s the preorder search:

    void BST_Preorder_Search(TNODE_PTR root)

    {

    // this searches a BST using the preorder search

    // test for NULL

    if (!root)

       return;

    // visit the node

    print("name: %s, age: %d", root->name, root->age);

    // traverse left tree

    BST_Inorder_Search(root->left);

    // traverse the right tree

    BST_Inorder_Search(root->right);

    } // end BST_Preorder_Search

And finally, the postorder search:

    void BST_Postorder_Search(TNODE_PTR root)

    {

    // this searches a BST using the postorder search

    // test for NULL

    if (!root)

       return;

    // traverse left tree

    BST_Inorder_Search(root->left);

    // traverse the right tree

    BST_Inorder_Search(root->right);

    // visit the node

    print("name: %s, age: %d", root->name, root->age);

    } // end BST_Postorder_Search

That’s it—like magic, huh? So if you had a tree, you would do the following to traverse it in order:

    BST_Inorder_Search(my_tree);

> Tip: I can’t tell you how important tree-like structures are in 3D graphics, so make sure you understand this material. Otherwise, when you build binary space partitions to help solve rendering problems, you’re going to be in pointer-recursion hell. :)

You’ll note that I have conveniently left out how to delete a node. This was intentional. It’s a rather complex subject because you could kill a sub-tree’s parent and disconnect all the children. Alas, deletion of nodes is left as an exercise for you to discover on your own. I suggest a good data structures text, such as Algorithms in C++ by Sedgewick, published by Addison Wesley, for a more in-depth discussion of trees and the associated algorithms.

Finally, for an example of BSTs, check out `DEMO11_3.CPP[vbar]EXE`. It allows you to create a BST and traverse it using the three algorithms. Again, this is a console application, so compile it appropriately.

### Optimization Theory

No other programming has the kind of performance requirements that games do. Video games have always pushed the limits of hardware and software and will continue to do so. Enough is never enough. Game programmers always want to add more creatures, effects, and sounds, better AI, and so on. Hence, optimization is of utmost importance.

In this section, I’m going to cover some optimization techniques to get you started. If you have further interest, there are a number of good books on the subject, such as Inner Loops by Rick Booth, published by Addison Wesley; Zen of Code Optimization by Mike Abrash, published by Coriolis Group; and Pentium Processor Optimization by Mike Schmit, published by AP Press.

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.