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][1]. Using [Stirling's approximation][2], 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 (n-m)2^n$$

bits.

  [1]: http://mathworld.wolfram.com/CatalanNumber.html
  [2]: http://mathworld.wolfram.com/StirlingsApproximation.html