Как реализовать в дереве позицию после конца и перед началом?

Question

[Кирилл Баталин]

Имеется бинарное самобалансирующееся дерево. Как лучше в нем реализовать элементы после конца и перед началом (чтобы потом бегать по дереву с помощью итераторов)?

Был такой вариант: i.imgur.com/iqrWYI3.png
То есть добавить родительский элемент для корня дерева. Тогда в конце обхода я всегда бы приходил туда. Но такой способ не устраивает из-за того, что не будет возможности вернуться на предыдущий элемент. Как только я попаду в эту вершину, то оттуда уже не получится выбраться. (На скриншоте изобразил указатели на родительский элемент. То есть, самый верхний элемент является родителем сам для себя и для root).

Еще думал добавить самому левому листу дочернюю вершину, которая будет элементом перед началом. Аналогично с правым нижним листом. Но из-за постоянных перестроений дерева отказался от этой идеи.

Answer 1

[bak]

Например, как это сделано в одной из реализаций STL:
1) end_node - специальная нода, которая является parent-ом root ноды.
2) root является left child-ом end_node-ы (parent и right child у end_node-ы нулевые).
3) Благодаря перечисленным выше свойствам при итерировании до конца мы будем приходить в end_node.
4) reverse_iterator - отдельный тип, конструируется из обычного итератора, но ведёт себя следующим образом:
- хранит в себе обычный итератор
- при обращении - возвращает предыдущий итератор (копирует обычный, зовёт -- у обычного, возвращает то что получилось)
- инвертирует операции ++, --, +=, -=
5) соответственно rend получается из begin()-а, а rbegin() из end()-а.

Comments

[bak]

Обращение к предыдущему элементу происходит следующим образом:
if (__x->__left_ != nullptr)
return __tree_max(__x->__left_);
while (__tree_is_left_child(__x))
__x = __x->__parent_;
return __x->__parent_;
Как видно в такой реализации у end_nodы предыдущим элементом будет являтся максимальная нода в дереве (left для end_nodы - это корень дерева).