Searching question

Hi:

I have been working on a project which requires searching through the rows of a matrix (of integers) for a particular row (this is in C++). Currently, I have each row in a binary search tree (using a lexicographic ordering on the rows) - I am wondering if there is a faster way of searching the rows. The < operator runs in O(n), so I was wondering if there are any other orderings/containers which would improve on this. (As far as I am aware, the tree is balanced.)

Thanks,
gfdsa

What exactly is the problem? And how are you certain your tree is balanced?

Only 5 posts and already being condescending, you are my favorite new member What I meant by "what is the problem?" is things seem to sound very smooth as it is. Are you having general performance issues? If you are, you can always create index to reference logical places in your tree (thus allowing you to skip ahead... though I don't recommend this if things are going smooth now since you need to do a fair amount of logic to implement the look up tables).

"already being condescending"
Sorry, that wasn't my intention - I misunderstood what you meant.

The problem is that I have a tree with around k^(k-2) elements (each is an array of length k), which is hard to handle for even small values of k, so I am looking for better algorithms.

gfdsa

Ok, so here is a series of question that could perhaps prevent you from posting code. Usually your tree will perform at around O(n) if the tree is needing to scan as many branches as there are entries, right? So that would lead one to believe that balance is not existing.

How are you searching for your data? Is it possible your actual algorithm that traverses the tree is searching areas where it need not go? I remember writing a compression algorithm once that would use a very large BSP to do a statistical analysis of the frequency of data, and it ran very quickly.

If all else fails, just post your code. Things have become messy over the years, I've noticed. The best way to post code is in the form of an attachment. Pseudo code is so hard to help people with. And I hate reading code off the forums.