Как работает трюк RBTree?

Question

В википедии: Red-black_tree

Отслеживание цвет каждого узла требуется только 1 бит информации на узел, потому что там> имеют только два цвета. Дерево не содержит никаких других данных, специфичных для того, чтобы быть красным -> черным деревом, поэтому его объем памяти почти идентичен классическому (неокрашенному) двоичному поисковому дереву. Во многих случаях дополнительный бит информации может храниться без дополнительной памяти> стоимости.

И я нашел орудие rbtree в 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 

Мой вопрос заключается в том, как работает этот цвет трюк Thx?.

Answer 1

Он использует (n невероятно отрывочный) трюк, изменяя указатель на родителя, чтобы сохранить один бит, который указывает цвет. Наименее значимый бит в этом указатель содержит цвет:

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

Если младший бит равен 0 то цвет, скажем, красный, и если младший бит равен 1 тогда цвет черный. (Поймите, что неважно, красный ли он 0, а черный - 1, или наоборот).

---

@Daniel Fischer commented со ссылкой, что гарантирует вывозимый из комментариев:

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

... что именно этот метод используется здесь.