5 ms·
BST is O(n) in the worst case (when a tree is completely unbalanced and is essentially a linked list)
by wpears 11y ago
BST is O(n) in the worst case (when a tree is completely unbalanced and is essentially a linked list)
- abcdabcd987 11y agoWell, 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 11y agoI'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 11y agoBSTs 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 11y agoAnd 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 11y agoSure, 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 11y agoI 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.
- Veedrac 11y agohttps://en.wikipedia.org/wiki/Binary_search_tree#Types https://en.wikipedia.org/wiki/Binary_search_tree#Types > There are many types of binary search trees. AVL trees and red-black trees are both forms of self-balancing binary search trees.
- hvidgaard 11y agoTerminology 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.
- Veedrac 11y agoI don't agree with your use of terminology; to me "BST" is just as much a class of things as "mammal" is. I will agree though that it has added confusion.
- hvidgaard 11y ago> 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.