Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk