1

在维基百科中：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

我的问题是这个颜色技巧是如何工作的？谢谢。

4

1 回答 1

5

它使用了一个（非常粗略的）技巧来改变指向父级的指针以存储一个位，该位指示颜色。该指针中的最低有效位包含颜色：

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

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

于 2013-04-30T01:58:08.477 回答