top | item 10653150 (no title) wpears | 10 years ago BST is O(n) in the worst case (when a tree is completely unbalanced and is essentially a linked list) discuss order hn newest abcdabcd987|10 years ago 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|10 years ago 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. load replies (1)
abcdabcd987|10 years ago 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|10 years ago 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. load replies (1)
skj|10 years ago 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. load replies (1)
abcdabcd987|10 years ago
skj|10 years ago
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.