When saying binary tree, I thought of a trie actually. I know it's still O(log n) so does not satisfy the
conditions, but a binary trie's code is not as complicated as that of a balanced binary tree.
As for initializing memory: the C library certainly won't initialize the whole array when calling
malloc. However, on multi-user OS, the system has to
initialize all the pages allocated by a process, for security
reasons. If it would not do that, you could get vulnerable
informations by allocating much memory and searching for
daat that other processes freed but hav not zeroed.
This does not take much time because 1. malloc
tries to reuse the memory freed by a process,
so it doesn't have to ask for a new chunk evry time,
2. the os can do it in idle time, so you don't have
to wait for it when you allocate the memory, 3.
zeroing a chunk of memory is fast.
The first reason may not count with very large arrays,
as malloc gets thoes with mmap, and when they're
freed they're munmapped.
The question you asked still holds however,
because using such a structure is good even in
such OS'es, as you may use it many time, and
you don't have to zero it evry time the same process
clears and reuses one. I
still don't know if it can be done in Perl.
