Memory usage of a BST or hash table? I would like to use a data structure allowing fast access, either a balanced binary search tree (BST) for $O(\log n)$ access time or an open hash table for constant access time.

1) What is the exact memory usage of a BST or hash table, for storing $n$ values? For instance, if we consider a BST, are $n$ pointers sufficient for storing it? (We can neglect the size of the stored values. The only thing that interests me is the storage overhead involed by the use of a specific data structure)

2) If the choice has to be determined by the cost in space, subject to the constraint of a fast enough access time, what is the best data structure to use?

For the space cost criteria, I would like a precise description. I'm interested in two types of usage: static and dynamic. I ask this question in the context of a C implementation.

I'm mostly interested in values around $n=100000$.
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 two bits per node. That's a lot less than two pointers.

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 harder to see how to get $O(\log n)$ access time, and much harder to see how to allow updates to the tree. This is an active research area.)

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 of red-black trees, because they use cache more efficiently. They also use $n + o(n)$ extra pointers to store $n$ nodes, compared with $2n$ or $3n$ for most binary search trees.

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 it is sufficient to use

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

bits. It is possible to achieve close to this bound using hash tables.

To give you the basic idea, consider an idealised hash table where you have $2^n$ elements stored in $2^n$ slots (i.e. load factor of one where every "chain" has length one).

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.

Of course, traditional hash tables have Poisson behaviour, so you would need to use a technique like cuckoo hashing to get close to a load factor of one with no chaining. See Backyard Cuckoo Hashing for further details.

So if space usage is a far more important factor than time (subject to time being "good enough"), it may be worth looking into this area of compressed data structures, and succinct data structures in particular.