David Abrahams wrote:
Howard Hinnant <hinnant@twcny.rr.com> 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.)