5
$\begingroup$

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$.

$\endgroup$
11
  • 1
    $\begingroup$ Have you tried answering this question yourself? What implementations of BST are you aware of? Can you calculate their memory usage? $\endgroup$ Commented Aug 14, 2015 at 15:20
  • $\begingroup$ @YuvalFilmus The problem with libraries is that we can only measure the overall memory usage, and me I would like to understand clearly what objects are used and what are their number. $\endgroup$
    – user7060
    Commented Aug 14, 2015 at 17:15
  • 1
    $\begingroup$ This question has a bunch of different kinds of questions connected together. I count at least three questions: one about minimum pointer-space for a BST, one for a hash table, and one about selecting a general question about low-space-overhead data structures in general. Smushing all of them into one question might be less than ideal. For the BST, it depends on how you represent the data structure: the number of points needed might be as low as zero, if you were to use a heap data structure to store the tree. For a hash table, the answer depends on what kind of hash table you're using (cont) $\endgroup$
    – D.W.
    Commented Aug 17, 2015 at 21:38
  • 1
    $\begingroup$ (cont), as David Richerby commented. For the last question, the answer will depend upon what counts as "fast enough access time". I could try to give an answer to any one of those questions, but when there are three different questions, and each one is a bit vague and ill-defined, I think that's a bit too much to expect for this site format. It'd be better to divide this up into multiple questions, and to edit the question to address the points/feedback raised in the comments. $\endgroup$
    – D.W.
    Commented Aug 17, 2015 at 21:39
  • 1
    $\begingroup$ How often are you going to add/remove elements, and what is acceptable performance for these operations? You can pack a BST or hash table with very little space overhead, but if it comes at a large $\Omega(n)$ overhead whenever the content changes, that might not be acceptable for you. $\endgroup$ Commented Aug 18, 2015 at 6:55

3 Answers 3

9
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for this very interesting answer. It seems that you have not finished the sentence "compared with $2n$ or $3n$ for" $\endgroup$
    – user7060
    Commented Aug 17, 2015 at 7:03
2
$\begingroup$

First of all BST has not $\Omega(logn)$ access, it has $\Omega(n)$. What you really need is AVL or RBT tree, self balancing trees to maintain logarithmic access.

1) BST you have to use two pointers (to left and right child) and one variable for data. This is whole footprint. Additionally you have to assign root to some variable. For AVL you may add height of left and right subtree (so like BST plus two integers), or one small integer to encode balance. In fact you have to choose what is footprint of one node, this is in tradeoff to speed of balancing operation. What auxiliary data you encode (or choose between AVL and RBT) is determined on ratio of insertions to searches. If smaller footprint is needed rebalancing operation will execute more steps. If you have all data in advance, you can construct BST with $\Omega(logn)$ access, if there will be no changes to structure later.

Hash table with open addressing is described here: http://www.algolist.net/Data_structures/Hash_table/Open_addressing Instead of creating linked list in case of collision it searches for free bucket, so there is no linked list needed.

2) Assuming you have everything in advance, and it is simple as search only - perfect hashing will give constant time access and no need for pointers at all, it will be simple array of your type and hashing function as getter. For example: http://cmph.sourceforge.net

BST is 2n pointers + n values. AVL is 2n pointers + n or 2n integers + n values. RBT is 2n pointers + n values + n colors (boolean). As you decided to open hash table (open adressing strategy), you have m pointers (m is > n, and biger is better) and n values. As open adressing is not degrading into linked lists but moves data to next empty cell. I assume that you create dynamically data structures, so empty node is only null pointer, so are leaves in trees. But even if some node is leaf, it still encodes 0 height to both childs.

$\endgroup$
6
  • $\begingroup$ Thank you for your answer. I try to improve again my post. $\endgroup$
    – user7060
    Commented Aug 16, 2015 at 11:08
  • $\begingroup$ I updated answer, but still you should answer about usage, if you have data in advance or dynamic. Do you want to modify it later? $\endgroup$
    – Evil
    Commented Aug 16, 2015 at 16:07
  • $\begingroup$ Thanks very much for your updating. What is the meaning of 1 root variable ? I don't understand why you say that "open adressing is not degrading into linked lists". An open hash table does not refer to a hash table with linked list for each entry ? Note that I've updated my post. I'm intereted by having data in adavnace or dynamically. $\endgroup$
    – user7060
    Commented Aug 16, 2015 at 16:24
  • $\begingroup$ Do not worry, additional root variable is convienient to tree operations with empty root (without data), it is not needed, I deleted it. For general case (dynamic) you have answers. In case of data known in advance and not modified later you can build balanced BST (without rebalancing operations) and use it. If you are using array with data that will be read only - you can (in the most cases) exploit data and hash it to one getter. It is time consuming, not always possible, but in runtime you do not have memory overhead and can guarantee constant lookup. $\endgroup$
    – Evil
    Commented Aug 16, 2015 at 16:42
  • $\begingroup$ Thank you for your updating. Instead of using $2n$ pointers for trees, it is not possible to use only one pointer by node ? For instance by using one pointer towards an array of two nodes (the node childrens) ? $\endgroup$
    – user7060
    Commented Aug 17, 2015 at 6:58
0
$\begingroup$

As far as I have understood your question, you are asking just about the size requirement for both algorithms.

  1. If you are using BST (Binary Search Tree) the size of your array depends on the number of elements you have. If it is a balanced tree, then you may require maximum of n+2 elements. But if it is unbalanced or skewed tree then you may be in need of n*2 elements.
  2. If you are using hash table, there is a factor called load factor. If you know the maximum limit of your elements, that is n, then you can keep the size of your array as n and you'll get maximum efficiency with LF=1.0. If you don't know the size of your elements (it may increase in future), you can initialize it with a L.F.=0.75. Your final size may be x=n/0.75.

One benefit with hash table is that you can fill all the locations available which is not the case with BST. In BST, an element can have only one appropriate place. Whereas, in hash table, you can insert the element in any next free available space.

For hash table, you can refer to this Chosing a suitable table size for a Hash

$\endgroup$
3
  • $\begingroup$ What kind of hash table (open or closed)? When you say that a hash table has "maximum efficiency" when it's completely full, I suppose you mean space efficiency, since inserting elements into a nearly-full closed hash table can be very time-consuming. $\endgroup$ Commented Aug 15, 2015 at 8:49
  • $\begingroup$ In BST memory size does not depend on balance. $\endgroup$
    – Evil
    Commented Aug 15, 2015 at 13:10
  • $\begingroup$ Thanks for this answer. We can suppose an open hash table. $\endgroup$
    – user7060
    Commented Aug 16, 2015 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.