1

ウィキペディア: Red-black_tree

色は 2 つしかないため、各ノードの色を追跡するには、ノードごとに 1 ビットの情報しか必要としません。ツリーには、赤→黒ツリーであることに固有の他のデータが含まれていないため、そのメモリ フットプリントは、従来の (色付けされていない) 二分探索 >tree とほぼ同じです。多くの場合、追加の情報ビットは、追加のメモリ > コストなしで保存できます。

そして、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.

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 に答える