无法理解 libstdc++ 的红黑树迭代器

Question

我正在尝试为三元搜索树实现迭代器，并且因为 TST 与 BST 非常相似，所以我想我应该看看libstdc++所述迭代器的实现。这个想法是迭代所有树节点，而不修改树或在迭代器中保存除当前树节点之外的任何内容。树节点有一个父指针来允许这种迭代。

以下是最新 GCC 的代码，取自GitHub 镜像：

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

它看起来相当简单，增量操作要么带你到你的右孩子，然后一直到左孩子，要么到你的第一个非右父母。我不明白的是第二if条：

if (__x->_M_right != __y)
  __x = __y;

这种情况怎么会评估为false？__x需要超越__y才能发生这种情况，从循环来看这似乎是不可能的while。false我认为如果树是线程树，则可能是这样，但nullptr第一个if子句的检查似乎表明情况并非如此。另外，删除该if子句并仅__x = __y;在我的代码中写入似乎不会破坏任何内容。

这里发生了什么？

编辑：

这是 Clang 的代码libc++。看来这次相同的代码不受保护if：

 template <class _EndNodePtr, class _NodePtr>
 inline _LIBCPP_INLINE_VISIBILITY
 _EndNodePtr
 __tree_next_iter(_NodePtr __x) _NOEXCEPT
 {
     if (__x->__right_ != nullptr)
         return static_cast<_EndNodePtr>(__tree_min(__x->__right_));
     while (!__tree_is_left_child(__x))
         __x = __x->__parent_unsafe();
     return static_cast<_EndNodePtr>(__x->__parent_);
 }

我怀疑 if 是多余的，因为它已经存在了至少二十年（自 SGI 时代以来）。

Answer 1

EASTL使用了类似的eastl::RBTreeIncrement基于HP STL的树函数：

/// RBTreeIncrement
/// Returns the next item in a sorted red-black tree.
///
EASTL_API rbtree_node_base* RBTreeIncrement(const rbtree_node_base* pNode)
{
    if(pNode->mpNodeRight) 
    {
        pNode = pNode->mpNodeRight;

        while(pNode->mpNodeLeft)
            pNode = pNode->mpNodeLeft;
    }
    else 
    {
        rbtree_node_base* pNodeTemp = pNode->mpNodeParent;

        while(pNode == pNodeTemp->mpNodeRight) 
        {
            pNode = pNodeTemp;
            pNodeTemp = pNodeTemp->mpNodeParent;
        }

        if(pNode->mpNodeRight != pNodeTemp)
            pNode = pNodeTemp;
    }

    return const_cast<rbtree_node_base*>(pNode);
}

在这里，我们的目标是

while(pNode == pNodeTemp->mpNodeRight) 
{
    pNode = pNodeTemp;
    pNodeTemp = pNodeTemp->mpNodeParent;
}
    
if(pNode->mpNodeRight != pNodeTemp)
    pNode = pNodeTemp;

是获取其左分支中包含当前节点 的最小子树的根节点pNode，如果该子树不存在，则获取前哨节点。

类似图/节点的容器（例如双向链表、红黑树等(c)end）使用哨兵节点以具有正确语义的方式实现成员方法end() - 1，并进一步利用它们来删除边缘情况（或移动边缘）从一种算法到另一种算法的情况）。

EASTL 定义其哨兵 ，mAnchor如下eastl::rbtree：

我们采用传统的技巧，将 begin()（最左边的 rbtree 节点）分配给 mpNodeLeft，将“end() - 1”（又名 rbegin()）分配给 mpNodeRight，并将树根节点分配给 mpNodeParent。

例如，如果红黑树中只有一个节点，则哨兵节点的左子节点、右子节点和父节点都将指向该单个节点。

这意味着，为了增加没有右子节点的根节点，我们将引入 else 分支eastl::RBTreeIncrement，并最终pNode等于 while 循环后的前哨节点，这就是增量的预期结果。以下语句的条件if是false因为pNodeTempwill 等于哨兵节点（即根节点本身）的父节点，而pNode->mpNodeRightwill 等于哨兵节点（即根节点）的右子节点。