[hvidgaard]

> I don't agree with your use of terminology

When you say BST the only thing you've said is that it's a binary tree structure with a property about the childrens value compared to the parent. While saying that there is certain BSTs with O(lg_2 n) searches is true, there also exists BSTs with O(n) searches.

The original claim was that:

> BTW, why not BST, for everything is O(log n)?

Which is not true. A sorted linked list is the canonical counter example. There is no confusion of terminology, it is clearly defined in algorithmic literature on search trees.

[Veedrac]

I generally take English sentences like that to be existential claims, rather than universal ones.

For example, if I was talking about an exciting new business plan to serve alcohol in a building and someone replied "Bars already serve drinks.", you probably wouldn't object saying that some bars don't serve drinks - that's not really the point.

I can probably concoct a counterexample, but given that most BSTs that one would actually use under that terminology are self-balancing ~O(log n) structures I am tempted to go with this. I imagine if "self-balancing BST" was used the objection might never have been raised, even though not strictly all self-balancing BSTs have all O(log n) operations.

Either way it's a semantic thing that has little to do with what BST means (we agree on that) and more to do with interpreting the ambiguities of English.

[hvidgaard]

My point of view origins from the academic world, and the distinction absolutely matters, and it should matter in any theoretical discussion on the topic, otherwise we'll spend too much time arguing semantics, instead of just being clear.

> not strictly all self-balancing BSTs have all O(log n) operations.

You're right. You could have a self balancing tree that would simply guarantee it's height is n/2, but that entails that it's height is O(n), which, by most definitions mean that it's not self balancing. You want it to be at least O(n^c) for 0<c<1, in height.

[Veedrac]

I'll put this under "agree to disagree". English is too vague to speak unambiguously in it all the time :P.