Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Help on BST

Posted on 2003-12-01
Medium Priority
233 Views
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
Question by:templeavenue
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 11

Accepted Solution

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

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

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

Question has a verified solution.

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

This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
###### Suggested Courses
Course of the Month7 days, 10 hours left to enroll