Memory usage is the amount of memory occupied by a computation or program during execution. Profiling it reveals whether a data structure's performance advantage carries an unacceptable space cost. section 3.5.4 section 3.5.3
Compare memory requirements by separating container size, stored data, and per-element overhead:
- Trees storing n keys still require n nodes whether they are balanced or skewed when they do not support compression. section 3.5.4
- Randomized treaps use slightly more than twice the memory of binary search trees for integer keys because each node stores an additional priority. section 3.5.4
- The ratio can shrink to about 1.25 for four- to ten-character strings, showing that key representation affects the practical cost. section 3.5.4
- For generic strings, estimate storage from key lengths: average length L gives space proportional to n*L, while maximum length m gives O(n*m). section 6.1.1
Choosing a structure for stored words
A trie can save roughly 30% of storage compared with a binary search tree when words share prefixes, but a degenerate trie can store information inefficiently. For a static set, a hash table may provide fast lookups; a Bloom filter can trade memory savings for reduced precision. section 6.2.1 section 6.1.1
Figure 3.23 Cumulative memory allocation for BST and RandomizedTreap, in the most generic case, with random insertions and removals
Compare cumulative memory allocation for binary search trees and randomized treaps across insertions and removals. section 3.5.4
Figure 6.4 Comparing BST and trie approaches on a different example. When the keys in the trie have a larger ratio of shared characters (that is, a longer common prefix), tries are more efficient in storing strings
Inspect how shared character prefixes change trie storage efficiency relative to binary search trees. section 6.2.1
