Re: Get reference to object in Set

On Fri, 6 Mar 2009, blue indigo wrote:

On Fri, 06 Mar 2009 16:20:40 +0000, Tom Anderson wrote:

More usefully, i actually did write an unordered map using a patricia tree
- i used the keys' hashcodes as the key strings. I think that'd be about
O(log n).

I don't see how this would be more useful than a HashMap, unless an array-based implementation was out of the question, maybe due to the sheer size of the collection. (Billions or more of entries?)

It's not really useful - it was more of an interesting exercise. The one potential advantage is that a tree never has to do a resize operation as it grows, unlike a hashtable, or any balancing operations, like a comparison-based tree, so although the amortized cost of each insertion may be higher, you know that they're all going to be about the same, as opposed to being really cheap most of the time and incredibly expensive occasionally. That could be useful in realtime systems.

Patricia trees have always been a favourite of mine because their structure is dependent only on their contents, and not their history, unlike most binary trees. That makes them easier to reason about and verify, and means that you don't have to worry about keeping them balanced. That's not to say that a Patricia tree is naturally balanced - try making one containing all the powers of two as keys - but it's one less bit of complexity to worry about.

And why call this a "patricia tree" -- I'm not familiar with that usage, though I've had plenty of exposure to all kinds of trees over the course of my career, B-trees, binary, red-black, several oddball ternary tree species, and yes, whole disjoint set forests of heap-like trees.

You evidently haven't had quite enough exposure:

Wikipedia calls it a radix tree, but Sedgewick, where i learned my data structures, calls it a patricia tree.

Does the name have anything to do with Patricia Shanahan, or is that a coincidence?

As far as i know, there's no connection.


if you can't beat them, build them