3 ms·
(I upvoted you because you're pedantically correct, but being even more pedantic: if it's not a balanced binary search tree, is "lookup" even a valid operation
by nostrademons 13y ago
(I upvoted you because you're pedantically correct, but being even more pedantic: if it's not a balanced binary search tree, is "lookup" even a valid operation on it?)
- marcosdumay 13y agoWell, lookup is a valid operation on any dataset.
- nostrademons 13y agoNot really: "lookup" is not part of the API (as taught in a typical data-structures class) for stacks, queues, and priority queues, and technically arrays/vectors let you lookup by integer but the O(N) lookup by object is only an extension that most languages provide as a convenience. If we really want to be pedantic, we'd have to define what the binary tree is used for, because there's no convention for what "lookup" means in this case. A heap, for example, can be implemented as a balanced binary tree, but the only methods it provides are push, pop, and top.