Is it wrong to say that a binary tree does not require a separate sort?

[Sam Hobbs]

In Printing the array elements in order without sorting???? the issue of whether a binary tree, such as what std::map usually uses, is considered a sort is discussed. It is a minor issue; I consider it to be insignificant. However I think that someone else is insisting that only one definition is valid. I think my definition is clear and I don't see why it is necessary to be so particular on this subject.

So when discussing a binary tree, such as what std::map usually uses, am I wrong for saying what I said? Note that I am willing to agree to have a different definition from others, but others are insisting that my definition is unacceptable.

[Bassman]

If you consider it so insignificant, why are you taking the trouble to post it to a new thread?

What in particular is the specific problem with saying that inserting a group of items into a binary tree performs a sort operation?

Regards,
Bassman

[jlou]

The first statement you made in regards to sorting was different than the question you ask now. You said:

Originally posted by Sam Hobbs
Many people expect order from a binary tree without a sort ever being needed. It is very possible to create an array that is in a specified order without ever sorting it.

This statement is technically wrong because the act of inserting elements is where the sort occurs. If you want to confine the definition of sort to only doing a separate operation after insertion, then you must state that or the unconfined definition will rightly be assumed. If you had not mentioned creation in that statement, then maybe it would be ok, but by referring to the creation of the array not only do you fail to confine the definition to your version, but you imply the more inclusive definition.

However, later in that thread and now in this thread you ask if the statement, "a binary tree does not require a separate sort", is valid. Yes it is, because you specify that you are referring to only a specific type of sort - one that is separate.

That's just how I see it.

[Bassman]

Also, Sam, I should point out that my main issue here is simply that:

Building a binary/AVL tree == Sorting an unsorted array == O(n log n)

So the act of arranging the items in a logical order has the same complexity no matter if you use a binary tree to store the data or an explicit sort method.

Which is why I thought it was remiss to imply you can create an arbitrarily sorted array without incurring the neccessary time costs required by a sort operation. Was that your implication? Probably not. But that's how I took it.

Regards,
Bassman

[JMS]

I must be really bored to reply here.. But I would have to agree with Sam from a coding stand point...

I don't think inserting Items into a binary tree as sorting them. I believe I'm on safe ground here because the order which the elements come out of that tree is not necesarily equivelent to how they are stored. Sorting is at least in part done by the retrieval process. The insert depends not only upon the min max order but upon the order in which the items are inserted.

Now having said this I think the english definition of sort would be anything that rearranges the numbers regardless of order. So
jlou's pedantic stance on a semetic definition of sort is probable valid. But then his original question about ordering without sorting becomes a mental jungle gym not even Ulga Korbit could traverse.

So I would say in parting... Jlou stop pestering my man Sam with simantics. Sam, stop getting into these silly arguments. We need your brain working technical problems and not working out these finer points of English. Sam I don't come here to read about your knowledge of English... 10,000 posts.. I've probable read 2k of them.

[Bassman]

I don't think inserting Items into a binary tree as sorting them.

You probably should.
(Binary tree sort)

Regards,
Bassman

[Sam Hobbs]

Originally posted by Bassman
If you consider it so insignificant, why are you taking the trouble to post it to a new thread?

I am sorry, but I meant to say that the question is not who is right and who is wrong but instead whether this issue is important enough that the question of right and wrong is relevant. I am saying that it is not worth all this and I want it to just go away. Yet you insist on saying I am wrong. It really is not worth all this foolishness. Yes, I could ignore it, if I knew that would be the end of it. If however you insist on being like this again, then let's deal with it now.

Originally posted by Bassman
What in particular is the specific problem with saying that inserting a group of items into a binary tree performs a sort operation?

The problem is that you are insisting that what I am saying is wrong. I said you can use the terminology you want to use with the definition you want but you insist that I can't use the terminology I want to use with the definition I want. I am saying that this matter is not important enough for this.

[Sam Hobbs]

Originally posted by JMS
So I would say in parting... Jlou stop pestering my man Sam with simantics. Sam, stop getting into these silly arguments. We need your brain working technical problems and not working out these finer points of English. Sam I don't come here to read about your knowledge of English... 10,000 posts.. I've probable read 2k of them.

Thank you.

I agree that it is a waste of time. I definitely have better things to do. One of many things is my web site. I really don't know if it would be better to just ignore the problem, but I know from many other experiences that not dealing with such things is a mistake. For some reason I have been getting a lot of this type of thing happening, and I really think it is unnecessary foolishness that I have done little (maybe a little but nothing unreasonable) to cause. The problem is that there are many other good people such as you that don't get involved, so I need to get more people involved somehow.

The definition of sort in this context is unclear enough that it is not worth all this. In my opinion, though, because of other things, I think it is impprtant to make the point that I did not make the issue such a big one.

Notice, though, that there are some people that just won't quit until they have made the last statement that the other personm is wrong. I often try to give them a way out. In this situation it has reached the point that I am willing to let the preson have the last word, whatever it may be.

[Bassman]

Sam,

It is very possible to create an array that is in a specified order without ever sorting it.

What definition of sort makes this correct (and the poster you replied to incorrect) and what is your justification for the definition? Specifically, why does your definition vary from the dictionary definition and what precedent is there for doing so?

I take my stance because you cannot impose order on data without sorting the data - which has consequences, and it's critical to recognize them.

Regards,
Bassman
And by the way, I'm right here, you can stop talking about 'a person' now.

[nsh123]

Originally posted by Bassman
so the act of arranging the items in a logical order has the same complexity no matter if you use a binary tree to store the data or an explicit sort method.

What do you mean by a logical order?

[nsh123]

Originally posted by Bassman
Building a binary/AVL tree == Sorting an unsorted array == O(n log n)

afaik
Binary tree is a tree where all nodes have <=2 children
therefore, what do you think is the complexity of creating a binary tree ?