On Tue, Jun 19, 2012 at 10:33 AM, Alan
Reiner
<etotheipi@gmail.com>
wrote:
If we were to use a raw trie structure, then we'd have all the
above
issues solved: a trie has the same configuration no matter
how elements
are inserted or deleted, and accesses to elements in the tree
are
constant time -- O(1). There is no such thing as an
unbalanced trie.
But overall space-efficiency is an issue.
A PATRICIA tree/trie would be ideal, in my mind, as it also
has a
completely deterministic structure, and is an
order-of-magnitude more
space-efficient. Insert, delete and query times are still
O(1).
However, it is not a trivial implementation. I have
occasionally looked
for implementations, but not found any that were satisfactory.
No, a trie of any sort is dependent upon distribution of
input data for balancing. As Peter
Todd points out, a malicious actor could construct
transaction or address hashes in such a way as to grow some
segment of the trie in an unbalanced fashion. It's not much
of an attack, but in principle exploitable under particular
timing-sensitive circumstances.
Self-balancing
search trees (KVL, RB, 2-3-4, whatever) don't suffer from
this problem.
Mark