Solved

Help on BST

Posted on 2003-12-01
3
227 Views
Last Modified: 2010-04-01
I'm writing a program using BST.  The program stores city code, city name, its crime rate, and its state which the city is located.  I can serach the database by citycode(unique key), but I do not know how to handle to search by its city name as well.  It must be able to search both either by the city code or city name. Any idea???

Thanks,
Raymond
0
Comment
Question by:templeavenue
3 Comments
 
LVL 11

Accepted Solution

by:
bcladd earned 25 total points
ID: 9854635
Can you traverse the entire tree? That is, can you write a function that visits every node in the tree? Perhaps a pre-order traversal? Imagine looking for the non-key data using a  traversal function that returns a pointer to the matching node (if found) and NULL otherwise. Then, instead of ALWAYS visiting current and then calling traverse left and then traverse right you will check if current is the one you want. If so, return the pointer; else, traverse left and if it returns non-NULL, return that value; else traverse right and return that value.

Hope this helps, -bcl
0
 
LVL 1

Expert Comment

by:travd
ID: 9854930
If you need to have fast search for both the citycode and the cityname, consider a secondary BST that will have city name as the key, and the value is a pointer to the relevant node in the first tree.  You would also need to have a pointer in the primary tree so that if you delete a node, for example, you can delete the secondary node also.
0
 
LVL 9

Expert Comment

by:jhshukla
ID: 9860821
make two BST's _sharing_ the same nodes.
class Node{
  //data
  Node *codeLeft, *codeRight;
  Node *nameLeft, *NameRight;
};

one BST uses code pointers while the other uses name pointers. Note that a given node's children may be different in different BST's. For Example:
codeBST has:
         A
       /   \
     B      C

nameBST has:
         C
       /   \
     B      A

As in the example above, even the roots may differ. Be careful with pointers.

Good luck
Jaydutt
0

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

808 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question