How to save the memory when storing color information in Red-Black Trees?

Question

I've bumped into this question at one of Coursera algorithms course and realized that I have no idea how to do that. But still, I have some thoughts about it. The first thing that comes into my mind was using optimized bit set (like Java's BitSet) to get mapping node's key -> color. So, all we need is to allocate a one bit set for whole tree and use it as color information source. If there is no duplicatate elements in the tree - it should work.

Would be happy to see other's ideas about this task.

Answer 1

Just modify the BST. For black node, do nothing. And for red node, exchange its left child and right child. In this case, a node can be justified red or black according to if its right child is larger than its left child.

Answer 2

Use the least significant bit of one of the pointers in the node to store the color information. The node pointers should contain even addresses on most platforms. See details here.

Answer 3

There's 2 rules we can use:

1. since the root node is always black, then a red node will always have a parent node.

2. RB BST is always with the order that left_child < parent < right_child

Then we will do this:

1. keep the black node unchanged.

2. for the red node, we call it as R, we suppose it as the left child node for it's parent node, called P.

change the red node value from R to R', while R' = P + P - R

now that R' > P, but as it's the left child tree, we will find the order mismatch.

If we find an order mismatch, then we will know it's a red node. and it's easy to go back to the original R = P + P - R'

Answer 4

One option is to use a tree that requires less bookkeeping, e.g. a splay tree. However, splay trees in particular aren't very good for iteration (they're much better at random lookup), so they may not be a good fit for the domain you're working in.

You can also use one BitSet for the entire red-black tree based on node position, e.g. the root is the 0th bit, the root's left branch is the 1st bit, the right branch is the 2nd bit, the left branch's left branch is the 3rd bit, etc; this way it shouldn't matter if there are duplicate elements. While traversing the tree make note of which bit position you're at.

It's much more efficient in terms of space to use one bitset for the tree instead of assigning a boolean to each node; each boolean will take up at least a byte and may take up a word depending on alignment, whereas the bitset will only take up one bit per node (plus 2x bits to account for a maximally unbalanced tree where the shortest branch is half the length of the longest branch).

Answer 5

Instead of using boolean property on a child we could define a red node as the one who has a child in the wrong place.

If we go this way all leaf nodes are guaranteed to to be black and we should swap parent with his sibling (making him red) when inserting a new node.