Dec. 23, 2009
9:44 p.m.
Adrian Kuhn wrote:
Levente Uzonyi <leves@...> writes:
what is TreeSet? The common data structure to implement ordered sets. Which one do you use?
IMO ordered sets (where ordering means the same as in OrderedCollection) should be implemented with a hashtable of linked elements.
You're right.
I confused ordered and sorted.
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). Regards, -Martin