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

#### Building BSTs

This subject is rather complex due to the recursive nature of all the algorithms that apply to B-trees. Let’s take a quick look at some of the algorithms, write some code, and finish with a demo.

Similar to linked lists, there are a couple of ways to start off a BST: You can have a dummy root or a real root. I’ll pick the real root because I prefer it. Hence, an empty tree has nothing in it but a root pointer pointing to `NULL`:

    TNODE_PTR root = NULL;

Okay, to insert data into the BST, you have to decide what you’re going to use as the insertion key. In this case, you can use the person’s age or name. Use the person’s age because these examples have been using age. However, using the name is just as easy; you would just use a lexicographic comparison function such as `strcmp()` to determine the order of the names. In any event, here’s the code to insert into the BST:

    TNODE_PTR root = NULL; // here’s the initial tree

    TNODE_PTR BST_Insert_Node(TNODE_PTR root, int id, int age, char *name)

    {

    // test for empty tree

    if (root==NULL)

       {

       // insert node at root

       root           = new(TNODE);

       root->id    = id;

       root->age   = age;

       strcpy(root->name,name);

       // set links to null

       root->right  = NULL;

       root->left   = NULL;

       printf("\nCreating tree");

       } // end if

    // else there is a node here, lets go left or right

    else

    if (age >= root->age)

       {

       printf("\nTraversing right…");

       // insert on right branch

       // test if branch leads to another sub-tree or is terminal

       // if leads to another subtree then try to insert there, else

       // create a node and link

       if (root->right)

          BST_Insert_Node(root->right, id, age, name);

       else

         {

         // insert node on right link

         TNODE_PTR node   = new(TNODE);

         node->id     = id;

         node->age    = age;

         strcpy(node->name,name);

         // set links to null

         node->left   = NULL;

         node->right  = NULL;

         // now set right link of current "root" to this new node

         root->right = node;

         printf("\nInserting right.");

         } // end else

      } // end if

    else // age < root->age

      {

      printf("\nTraversing left…");

      // must insert on left branch

      // test if branch leads to another sub-tree or is terminal

      // if leads to another subtree then try to insert there, else

      // create a node and link

      if (root->left)

         BST_Insert_Node(root->left, id, age, name);

      else

         {

         // insert node on left link

         TNODE_PTR node   = new(TNODE);

         node->id     = id;

         node->age    = age;

         strcpy(node->name,name);

         // set links to null

         node->left   = NULL;

         node->right  = NULL;

         // now set right link of current "root" to this new node

         root->left = node;

         printf("\nInserting left.");

         } // end else

    } // end else

    // return the root

    return(root);

    } // end BST_Insert_Node

Basically, you first test for an empty tree and then create the root, if needed, with this first item. Hence, the first item or record inserted into the BST should represent something that is in the middle of the search space so that the tree is nicely balanced. Anyway, if the tree has more than one node, you traverse it, taking branches to the right or left depending on the record that you’re trying to insert. When you find a leaf or terminal branch, you insert the new node there:

    root = BST_Insert_Node(root, 4, 30, "jim");

Figure 11.10 shows an example of inserting “Jim” into a tree.

Figure 11.10 Inserting into a BST.

The run-time performance of an insertion into the BST is the same as searching it, so an insertion will take O(log2 n) on average and O(n) in the worst case (when the keys happen to fall in linear order).

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.