Wikipedia states that the color bit can be stored without taking
additional space: "In many cases the additional bit of
information can be stored at no additional memory cost."
Looking at the Phobos implementation, it stores it as a regular
byte:
https://github.com/D-Programming-Language/phobos/blob/master/std/container.d#L4945
The only way I can see it storing a bit without taking additional
space is by storing the color in the pointer to a node instead of
in the node by using the tagged pointer trick:
http://en.wikipedia.org/wiki/Pointer_tagging
But I would think this trick would break the GC, as well as
making code less portable.
So.. Is the RBTree article a bit off here, or are there other
techniques to reduce memory overhead?
- Red-Black tree storing color without additional memory req... simendsjo
-
