|
Howdy guys, you all helped me a ton last time I had a problem, so I'm coming back for more! This one falls under more general algorithms then c++ in general. Anyway...
For this project i have a medium-sized database implemented as a Binary Search Tree using the author of the books implementation (it sucks). Anyway, I got everything working fine, except one thing. The BST has a "keyed item" that it uses to keep the tree sorted etc. The problem is, I have to display a report based on a non-keyed item. I can't just change the keyed item and resort the tree, and I can't move the items into a new data structure. Is there any remotely efficient way to do this? Am I just missing something?
tl;dr version: how to output from a binary search tree based on a NON keyed entry.
thanks a ton in advance guys.
edit:
I suppose I should elaborate a bit more. I know that I could just write a findMin method(function?) based on the non-keyed item, print it, delete it, and keep going through the tree. But this is horribly inefficient because of all the loop nesting. I'm asking if there's a better way to do it.
|
|
|
So you need to display the non-keyed items in sorted order?
|
On November 11 2009 11:29 imDerek wrote:
So you need to display the non-keyed items in sorted order?
yes..well..
the tree is made up of objects that contain like 25 fields each or so. One of the fields is the keyed item. I have to display the objects sorted by a different item lol.
|
Your idea isn't necessarily horribly inefficient (O(n*n)), but not fantastic I guess? Depends on what you're shooting for.
Why aren't you able to re-sort or use an additional data structure? Just a stipulation of the problem?
When you say "can't move the items into a new data structure": do you mean you aren't allowed any additional storage, or does this mean "can't create a new BST"?
If you can create just an additional array, then toss all of the items in there and do a quicksort for O(n lg n) performance, but it doesn't really look like you can squeeze anything better out. Will look at it a little more.
|
why exactly can't you just read the fields you're interested in into an array and sort that? without copying stuff (or at least references to stuff) into another data structure I don't think there's really an efficient way to do this.
poster above me: sorry, but n^2 does in fact count as 'horribly inefficient' 
|
I suppose I should elaborate a bit more. I know that I could just write a findMin method(function?) based on the non-keyed item, print it, delete it, and keep going through the tree. But this is horribly inefficient because of all the loop nesting. I'm asking if there's a better way to do it.
You can consider using heapsort if you're going to do it this way, O(n lg n) performance, just need to heapify the tree, then keep removing the min element
http://en.wikipedia.org/wiki/Heapsort
|
Wouldn't that count as re-sorting the tree? Works as an in-place alternative to the array solution though.
|
oh yeah but since you're altering the tree anyway u might as well re-sort it haha
|
lol thanks for all the input guys. I cant re-sort the tree, and I can't move the elements into another data structure (including arrays). just a stipulation of the problem.
btw the findMin solution is worse than O(n^2).
findMin would have two nested loops, and findMin itself would be inside 2 nested loops.
Ill just go ahead and do it anyway. this class is fucking stupid. this is a very small part of a much larger project, and is the only part thats giving me headaches lol.
|
heapsort. Since your items aren't indexed for the value you're looking for, you pretty much have to resort it. Heapsort is O(nlogn) as opposed to the min-first sorting you mentioned, which is O(n^2).
|
On November 11 2009 12:49 tossinYoSalad wrote:
lol thanks for all the input guys. I cant re-sort the tree, and I can't move the elements into another data structure (including arrays). just a stipulation of the problem.
btw the findMin solution is worse than O(n^2).
findMin would have two nested loops, and findMin itself would be inside 2 nested loops.
It should be better than n^2.
You look through n elements to find the smallest, then n-1 for the 2nd, etc...
You thus have O(n * (n-1)/2) = O(n^2). If your findMin method is > n^2 you're doing something wrong in your looping implementation.
I hypothesize your issue is that your tree traversal is shit. Pre-order, in-order, post-order are all O(n). You should be fine in all those cases.
|
On November 11 2009 12:53 wok wrote:Show nested quote +On November 11 2009 12:49 tossinYoSalad wrote:
lol thanks for all the input guys. I cant re-sort the tree, and I can't move the elements into another data structure (including arrays). just a stipulation of the problem.
btw the findMin solution is worse than O(n^2).
findMin would have two nested loops, and findMin itself would be inside 2 nested loops. It should be better than n^2. You look through n elements to find the smallest, then n-1 for the 2nd, etc... You thus have O(n * (n-1)/2) = O(n^2). If your findMin method is > n^2 you're doing something wrong in your looping implementation. I hypothesize your issue is that your tree traversal is shit. Pre-order, in-order, post-order are all O(n). You should be fine in all those cases.
yeah i was just going through it in my head and I counted loops wrong. it would be n^2. in any case its all done and off to be graded.
tree traversal was implemented by the author of the book so I had nothing to do with that lol.
|
sorry i cant help but laugh whenever i see your name lmao
|
On November 11 2009 15:06 JohnColtrane wrote:
sorry i cant help but laugh whenever i see your name lmao
haha thanks  . i like it. the full name is proTossinYoSalad.. has an extra ring to it.
|
|
|
|
|
|
EPT
