From: David Abrahams (dave_at_[hidden])
Date: 2005-02-15 13:59:10
Howard Hinnant <hinnant_at_[hidden]> writes:
> 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
Oh, I didn't understand that he meant color info. I guess that is
only for rebalancing, isn't it?
/me crawls back under rock
> 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? :-)
/me burrows several inches down into dirt under rock
-- Dave Abrahams Boost Consulting www.boost-consulting.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk