Проблемы с пониманием итераторов libstdc ++ в красно-чёрном дереве - PullRequest
Новая
       8

Проблемы с пониманием итераторов libstdc ++ в красно-чёрном дереве

0 голосов
/ 01 октября 2018

Я пытаюсь реализовать итераторы для троичного дерева поиска , и, поскольку TST очень похожи на BST, я подумал, что посмотрю на реализацию libstdc++ для указанных итераторов.Идея состоит в том, чтобы перебрать все узлы дерева без изменения дерева или сохранения чего-либо кроме текущего узла дерева в итераторах.Узлы дерева имеют родительский указатель для такой итерации.

Вот код из последнего GCC, взятый из GitHub mirror : 

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;
}

Itвыглядит довольно просто, операция приращения либо приведет вас к вашему правому ребенку, а затем - к левому, либо к первому не правому родителю.Что я не понимаю, так это второе if предложение: 

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

Как это условие может когда-либо оцениваться в false?__x должен превзойти __y, чтобы это произошло, и это не представляется возможным, если смотреть на цикл while.Я думаю, что это могло бы быть false, если бы дерево было резьбовым деревом , но проверки nullptr в первом предложении if, похоже, указывают на обратное.Кроме того, удаление условия if и просто запись __x = __y; в моем коде, похоже, ничего не нарушает.

Что здесь происходит?

Редактировать :

Это код для 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).

...