Binary radix tries

[Kayaker]

Interesting article explaining the concept of Binary radix (Patricia) tries, a souped up version of a binary search tree. (interesting if you're into that kind of thing that is..)

Possible replacement for hash tables?


Aguri: Coolest Data Structure You’ve Never Heard Of
http://www.matasano.com/log/1009/aguri-coolest-data-structure-youve-never-heard-of/

[Maximus]

they are out from over a decade. I remember a DDJ article talking about sorting white pages with such algo -using an hacked alpha tree implemented using windows dir (cool idea btw, something like /m/a/x/i/m/u/s->here phone number).

they have quite their drawbacks, however. And no, hashes are faster, because they usually require few math and fewer memory fetch. hashes are slower on bad-sized tables when you get primary/secondary condensation (aka many collisions).

i have it somewhere in a very old DDJ, but... well i'm tired and dont wanna google

edit---
mmh.,. times passes so fast... nearly 2 decades i fear...

[ZaiRoN]

Quote:

well i'm tired and dont wanna google

Maximus: you should have studied all these interesting algos at uni (as far as I remember, we were at the same.. ), take a look at your papers

[Maximus]

hehe, i wanted to place a nice reference for those interested in practical applications and drawbacks of the algo, but looks like the article is not freely accessible... the only ref I found is to an old '95 article, which may match... I dont remember