STL函数为什么使用节点的颜色来计算std :: map节点的前身

Question

我正在研究libstdc ++的std::map实现，并注意到迭代器的递增和递减函数并非完全对称。 local_Rb_tree_decrement函数（又名前身）具有一个附加子句，用于检查节点的颜色：

static _Rb_tree_node_base*
local_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ()
{
  if (__x->_M_color == _S_red
      && __x->_M_parent->_M_parent == __x)
    __x = __x->_M_right;
  else if (__x->_M_left != 0)
    {
      _Rb_tree_node_base* __y = __x->_M_left;
      while (__y->_M_right != 0)
        __y = __y->_M_right;
      __x = __y;
    }
  else
    {
      _Rb_tree_node_base* __y = __x->_M_parent;
      while (__x == __y->_M_left)
        {
          __x = __y;
          __y = __y->_M_parent;
        }
      __x = __y;
    }
  return __x;
}

第一种情况的目的是什么，为什么节点的颜色会以任何方式影响树的遍历？为什么与local_Rb_tree_increment不同？

if (__x->_M_color == _S_red
    && __x->_M_parent->_M_parent == __x)
  __x = __x->_M_right;

感谢您的评论和解释！

Answer 1

这肯定可以处理end()的情况-请注意无意义的祖父母的自相矛盾和错误的运动方向。而且，毕竟，您不能increment end()。颜色检查大概是一种优化，以（有时）避免获取比所需更多的内存。

Answer 2

经过一些调查，我相信我已经知道了。

标题

libstdc++的std::map的实现在树的顶部有一个附加节点。它称为Header，它的left子项指向整棵树的最左叶，它的right子项指向整棵树的最右叶，而它的parent] 实际上是Root node。因此，它有助于获得对树中最小和最大键的恒定时间访问时间（更快的begin()和rbegin()操作）。 Root node的parent也指向Header node，用这两个节点创建一个parent循环。

结束迭代器

如Davis Herring的回答，这也用于处理迭代器的end()情况。 end迭代器的最幼稚的实现将只包含null指针。如果到了下一个节点为null的地步，那就是end。它完美无瑕...直到您需要返回。 std::map的迭代器是bidirectional，并且您必须能够减少end迭代器并获取树的最右边的元素。

标题结尾

这里是Header节点再次提供帮助的地方。在有序遍历中搜索下一个节点时，我们最终到达Root node的父节点。我们不是从right（不是从left来的）进入Header node，而是将其作为后继项返回。这样，将Header作为end迭代器节点是很自然的。这就是为什么以前的计算条件会检查祖辈等于其自身的节点的原因。这是我们可以检查是否在Header节点中的方法。这也解释了我们为什么选择正确的子代：Header的正确子代是树的最右节点，这是inorder traversal中end的前身。

等等...但是颜色呢？>

是的，上一部分有一个重大错误。有two

个节点，其祖父母级等于此节点：Header和Root。从这个角度看，它们是无法区分的。我们需要为Header node提供一个单独的标志。

但是，红黑树中的每个节点已经有一个布尔标志：color

。而且我们还有一个red-black tree的很好的属性：Root总是black。

全部放在一起，我们可以完全省略其他标志，并为Header red

上色。这将是具有祖父母循环的两个节点的区别属性。