RBTree的颜色技巧如何运作？

Question

在维基百科:Red-black_tree

跟踪每个节点的颜色每个节点只需要1位信息,因为只有两种颜色.该树不包含任何其他特定于红色 - >黑色树的数据,因此其内存占用量几乎与经典(无色)二叉搜索>树相同.在许多情况下,可以在没有额外存储器>成本的情况下存储额外的信息.

我在C中找到了一个rbtree的工具:

#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

我的问题是这种颜色技巧是如何工作的？Thx.

Answer 1

它正在使用一种(非常粗略的)技巧来改变指向父节点的指针,以存储一个指示颜色的位.该指针中最不重要的位包含颜色:

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

如果低位0则颜色为红色,如果低位1则颜色为黑色.(意识到红色0和黑色是否相关1,反之亦然).

@Daniel Fischer评论了一个链接,保证被带出评论:

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

......这正是这里使用的技术.