Re: what type of tree algorithm is this?

"Gene" <gene.ressler@xxxxxxxxx> wrote in message news:38b9873b-24bf-443b-92dc-e5106d2614a0@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Nov 11, 1:36 pm, Richard Heathfield <r...@xxxxxxxxxxxxxxx> wrote:
In <hdert2$nb...@xxxxxxxx>, James wrote:
[...]
> I was not happy with a binary tree, so instead of comparing keys, I
> simply check of bits are set or not. Each bit represents a level in
> the tree, so if `unsigned long int' is 32-bit's then the tree will
> only have 32 levels

Sure sounds like a trie to me. (Not a typo, by the way: trIe.) They
have quite a few uses, but they are perhaps most famous for their
starring role in compression programs.

Take a look at this:

http://www.itl.nist.gov/div897/sqg/dads/HTML/trie.html

and see if it rings a bell.

It ends up looking like a trie, but it's slightly different from the
usual. This algorithm inserts based on the prefix (starting at the
lsb) that's sufficient to reach a missing node in the current tree.
The rest of the key is ignored. So insertion order matters.

Right. This modified "trie" is not sorted when you traverse it like:


void traverse(struce tree* t)
{
if (t)
{
traverse(t->left);
printf("%lu\n", t->key);
traverse(t->right);
}
}


It just that I did not need to process anything in any particular order, so this "hacked" trie seems to be working pretty darn good for my application so far.




A
classical trie would, I suppose, create N levels where the MSB of the
key is at bit N-1, and insertion order would be immaterial. It's a
small change, but it's a pretty clever idea for the OP's application,
which seems to be a hash table for unsigned ints.

Yeah. I was experimenting with the hash to try and take "pressure" off of a single trie. With the hash in place I guess the complexity would be something like:




let N = total bits in key



no collision
--------------------------------------------------------
O(1) - best-case



collision
--------------------------------------------------------
O(log N) - worst-case



collision on a trie with N levels and item is at level N
--------------------------------------------------------
O(N) - horrible-case




Who knows, this hack might be fairly useful to somebody else besides me!

;^)

.

Relevant Pages

  • Re: what type of tree algorithm is this?
    ... of the following tree algorithm is? ... the tree, so if `unsigned long int' is 32-bit's then the tree will ... Sure sounds like a trie to me. ... and insertion order would be immaterial. ...
    (comp.programming)
  • Re: using a tree to delete duplicate lines in a text
    ... are sequences much longer than 1 word, like these strings, then you ... On the contrary, that is the sole purpose of the trie data structure and, ... In a hash table, you hash the key ... the tree depth is Owhereas the hash cost is O. ...
    (comp.programming)
  • Re: using a tree to delete duplicate lines in a text
    ... On the contrary, that is the sole purpose of the trie data structure and, ... the tree depth is Owhereas the hash cost is O. ... to detect a duplicate the whole string must be ...
    (comp.programming)
  • Re: Functional dictionary structure
    ... to get better performance than Data.Map, which uses a balanced binary tree. ... unboxed Ints, not it's use of a Trie structure. ... with like (I.E. compare with balanced tree of unboxed Ints) things ... Trie needs (for the balanced tree it just does a simple compare ...
    (comp.lang.functional)