From: Howard Hinnant (hinnant_at_[hidden])
Date: 2005-02-15 11:11:48
On Feb 15, 2005, at 9:49 AM, David Abrahams wrote:
>> Absolutely, all designs have certain irreducible overhead - I didn't
>> mean to imply otherwise. In the case of std::map, one should expect
>> an instance to be on the large-ish side. Also, one should expect the
>> per node overhead to be two pointers and probably another word for
>> the tree balancing algorithm.
>
> You don't need any storage for rebalancing. Typical map nodes have 3
> pointers: parent, left child, and right child.
If it is a red-black tree, you need to store the color of each node.
This information requires 1 bit, which can easily be padded to a word.
If it is a AVL tree, each node needs to store its tilt. This
information requires 2 bits.
Or is there a new technique I'm about to learn about? :-)
-Howard