How does RBTree's color trick work? [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 8 years ago.

In wikipedia : Red-black_tree

Tracking the color of each node requires only 1 bit of information per node because there >are only two colors. The tree does not contain any other data specific to its being a red–>black tree so its memory footprint is almost identical to classic (uncolored) binary search >tree. In many cases the additional bit of information can be stored at no additional memory >cost.

And I found an implement of rbtree in C:

#ifdef UINTPTR_MAX

static inline enum rb_color get_color(const struct rbtree_node *node)
{
    return node->parent & 1;
}

static inline void set_color(enum rb_color color, struct rbtree_node *node)
{
    node->parent = (node->parent & ~1UL) | color;
}

static inline struct rbtree_node *get_parent(const struct rbtree_node *node)
{ 
    return (struct rbtree_node *)(node->parent & ~1UL);
}

static inline void set_parent(struct rbtree_node *parent, struct rbtree_node *node)
{
    node->parent = (uintptr_t)parent | (node->parent & 1);
}

#else
...
#endif

My question is how this color trick works?Thx.

Answer 1

It's using a(n incredibly sketchy) trick of altering the pointer to the parent to store a single bit, which indicates the color. The least significant bit in that pointer contains the color:

static inline enum rb_color get_color(const struct rbtree_node *node)
{
    return node->parent & 1;
}

If the low bit is 0 then the color is, say, red, and if the low bit is 1 then the color is black. (Realize that it's irrelevant whether red is 0 and black is 1, or vice versa).

---

@Daniel Fischer commented with a link that warrants being brought out of the comments:

http://en.wikipedia.org/wiki/Pointer_tagging

...which is precisely the technique used here.