Boost logo

Boost :

From: Peter Dimov (pdimov_at_[hidden])
Date: 2005-02-15 14:41:35


David Abrahams wrote:
> Howard Hinnant <hinnant_at_[hidden]> writes:
>
>> On Feb 15, 2005, at 9:49 AM, David Abrahams wrote:
>>
>>> 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.
>
> 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

You could have pretended that you had in mind an implementation where
pointers are always even and one of the least-significant bits is used as a
color bit. ;-)

Are there std::maps that store a next and previous pointer to optimize
traversal at the expense of per-node overhead?

(Of course my original point was that most people don't care about the
per-node overhead and those that do just use a different data structure.)


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