Skip to main content
3 of 7
added 512 characters in body
Pseudonym
  • 23.8k
  • 3
  • 46
  • 94

When you're asking about "exact" memory usage, do consider that all of those pointers may not be necessary. To see why, consider that the number of binary trees with $n$ nodes is $C_{2n}$, where:

$$C_i = \frac{1}{i+1} { 2i \choose i }$$

are the Catalan numbers. Using Stirling's approximation, we find:

$$\log C_{2n} = 2n - O(\log n)$$

So to represent a binary tree with $n$ nodes, it is sufficient to use $2n$ bits.

It's not too difficult to work how how to compress a static (i.e. non-updatable) binary search tree down to that size; do a depth-first or breadth-first search, and store a "1" for every branch node and a "0" for every leaf. (It is much harder to see how to get $O(\log n)$ access time or to allow updates to the tree.)

Incidentally, while different balanced binary tree variants are interesting from a theoretical perspective, the consistent message from decades of experimental algorithmics is that in practice, any balancing scheme is as good as any other. The purpose of balancing a binary search tree is to avoid degenerate behaviour, no more and no less. Stepanov also noted that if he'd designed the STL today, he might consider in-memory B-trees instead, because they use cache more efficiently.

As for hash tables, there is a similar analysis that you can do. If you are (say) storing $2^n$ integers in a hash table from the range $[0,2^m)$, and $2^n \ll 2^m$, then you can achieve this using close to:

$$\log {2^m \choose 2^n} \approx (m-n)2^n$$

bits. I can go into a bit more detail if you like, but to give you the basic idea, consider that if you hash $m$ bits of key into $m$ bits of hash, then store this in a $n$-bit hash table, then $n$ bits of the hash are implied by the position in the hash table, and you therefore only need to store the remaining $m-n$ bits. By using an invertible hash function (e.g. a Feistel network), you can recover the key exactly.

(This assumes an idealised hash table, not one with Poisson behaviour. So you would need to use a technique like cuckoo hashing to get the load factor close to 1.)

Pseudonym
  • 23.8k
  • 3
  • 46
  • 94