[wpears]

BST is O(n) in the worst case (when a tree is completely unbalanced and is essentially a linked list)

[abcdabcd987]

Well, it's not a big problem. This case won't exist in most BSTs. Even if it appears in some BST, splay tree for example, it will be amortized.

[skj]

I'm not really sure what amortization you're talking about here.

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.

[cporios]

BSTs can have O(lg n) lookups. A Red-black tree is such an example. It is a self-balancing BST, so a red-black tree is a BST itself.

[hvidgaard]

And BSTs can have O(n) lookup. The only property of a BST is that you know something about the value of the children compared to the parent. This means that a sorted linked list is a BST.

[Veedrac]

Sure, but abcdabcd987 was evidently not suggesting using a completely general BST. That there exists a BST with the mentioned properties is sufficient to validate the claim made; that there exists a BST which does not is irrelevant.

[skj]

I believe your and abcdabcd987's use of the term BST is not exactly what is commonly used. A BST refers to both the data structure and the algorithm used to manage it. An RB tree is a different concept. An RB tree is a binary tree, certainly, since the term "binary tree" implies no algorithms, but it is not a "binary search tree" in its specific denotation.

[hvidgaard]

Terminology is important. A BST is what I defined. A balanced BST has an extra property, but you don't get to call a balanced BST just a BST, it only adds to confusion and unclear communication.