CODEWITHSUNDEEP
c++data-structurestree
Dirt
Dirt

Reputation: 331

Searching data stored in a tree

I have this data that is hierarchical and so I store it in a tree. I want to provide a search function to it. Do I have to create a binary tree for that? I don't want to have thousands of nodes twice. Isn't there a kind of tree that allows me to both store the data in the order given and also provide me the binary tree like efficient searching setup, with little overhead?

Any other data structure suggestion will also be appreciated.

Thanks.

EDIT:

Some details: The tree is a very simple "hand made" tree that can be considered very very basic. The thing is, there are thousands of names and other text that will be entered as data that I want to search but I don't want to traverse the nodes in a traditional way and need a fast search like binary search.

Also, importantly, the user must be able to see the structure he has entered and NOT the sorted one. So I cant keep it sorted to support the search. That is why I said I don't want to have thousands of nodes twice.

Upvotes: 0

Views: 208

Answers (1)

UmmaGumma
UmmaGumma

Reputation: 5693

If you don't want to change your trees hierarchy use a map to store pointers to vertexes: std::map<SearchKeyType,Vertex*> M.

Every time when you will add vertex to your tree you need to add it to your map too. It's very easy: M[key]=&vertex. To find an element use M.find(key);, or M[key]; if you are sure that key exists.

If your tree has duplicate keys, then you should use a multimap.

Edit: If your key's size is too big, than you can use pointer to key instead of key:

inline bool comparisonFunction(SearchKeyType * arg1,SearchKeyType * arg2);

std::map<SearchKeyType *, Vertex *, comparisonFunction> M;

inline bool comparisonFunction(SearchKeyType * arg1,SearchKeyType * arg2)
{
         return (*arg1)<(*arg2);
}

to search Element with value V you must write following:

Vertex * v = M[&V]; // assuming that element V exists in M

Upvotes: 1

Related Questions