BST is O(n) in the worst case (when a tree is completely unbalanced and is essentially a linked list)
BSTs are O(n) lookup, and the pathological case is quite easy to achieve: add elements to it in sorted order.
There are other trees that have O(lg n) lookup. Red-black trees are the canonical example.
> There are many types of binary search trees. AVL trees and red-black trees are both forms of self-balancing binary search trees.
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.
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.
> 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.