Dec. 23, 2009
10:08 p.m.
Levente Uzonyi wrote:
I'd think that a hashtable of elements that are linked into a tree structure would also be an attractive implementation of a sorted set. Insert and delete time would be O(log n) but lookup time would be O(1).
I don't see the point here. Without a tree structure (just a list) it's O(1) for both.
How do you get O(1) for sorted inserts into a list? That's usually considered an O(n) operation. Or am I misunderstanding what you mean by list? Regards, -Martin