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.

Unequivocal

Answer 1

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.

Lilias

You're absolutely right that this is the most common approach. However, in Java, this isn't possible since Java doesn't expose the bits of its pointers. The OP might be using Java, though I'm not sure if that's the case. – Outdated

@Outdated The question didn't explicitly target Java, it merely mentioned a data structure similar to that of Java, so it may or may not be the case. – Lilias

Right, I didn't mean Java as target but I was expecting portable solution (w/o this bare metall details). Anyway, I can't even understand this answer. @AlexeyFrunze, could you please explain the idea more detailed (for example in C and 4-byte pointers)? – Unequivocal

Optimizing red-black tree color bits. – Lilias

Answer 2

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.

Solicitous

This does not work with nodes which don't have two child nodes. – Globulin

Sure it does: just check if the one node is in the wrong place. If there are zero nodes, there's nothing to check since we never give the null node a red link. – Horsewhip

If 'null node' means a node without any children, then it is possible that a 'null node' to be red. Just check the example in the red-black tree wikipedia entry upload.wikimedia.org/wikipedia/commons/thumb/6/66/…. Given that, it seems to me the proposed scheme won't be able to distiguish betwen a red 'null node' and a black 'null node' – Quincyquindecagon

This sounds significantly worse than the accepted answer - you'd have to check twice the amount of links! – Harpist

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'

Kingbolt

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).

Oat

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.

Inaugural