On Jul 13, 3:46 am, Tech Id <tech.login....@gmail.com> wrote: > Wont a bitwise trie be too memory intensive? > Storing an integer would need 32 nodes space and each node would need > 3-integers space (data, left and right). > So, if there are a million integers, we will need 32*3 = 96 million > integers!
Great point. But it may be okay if you're tricky about how you store things. First, you dont' have to store the values in the nodes, so you're down to 2 integers. (An integer is in the tree only if a full corresponding 32-node path exists.) Especially, if you don't have to change the trie after it's created, you can use cdr-coding. This means that you store all (say) left-child descendents of every subtree root as an array of right child pointers. In this manner, you need zero bytes for left child pointers. (You do need a way to mark the end of each array. One common technique is to set the lowest-order bit of the last right child pointer to 1; since most systems align ints on 4- byte boundaries, the low 2 bits of every pointer are normallly zero). So now you are down to 1 word of 32 bits per node. So your 1 million integers are representable in 4 million bytes, which is the same as a simple array of integers. You can play further tricks to get it even lower, but I'll let you think about that... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
