Каков самый чистый способ расширить этот дизайн для переписывания деревьев?

Question

У меня есть дерево объектов, где у каждого объекта есть std::vector указателей на его потомков. Класс объекта имеет метод rewrite(), который применяется рекурсивно для изменения объекта и его дочерних элементов, обычно со следующими преобразованиями, где [N] - это перезаписываемый объект, а (M) - это элемент, который возвращает rewrite(). :

                 (A)
 [A]             / \               [A]
 / \     -->    B   X               |    -->    (B)
B   C                \              B
                      C

Какой самый простой способ расширить эту настройку, чтобы разрешить подобные преобразования?

    A             X
    |            / \
   [B]   -->    C   A
    |               |
    C              (Y)

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

Answer 1

Похоже, для скорости вам понадобится "обратный указатель" от каждого дочернего узла к его родительскому узлу. Таким образом, вы можете проследить цепочку родительских указателей по указателю на любой узел вплоть до корня, если это то, что вам нужно (я не уверен, как еще вы планировали найти корень по указателю на внутренний узел). без обратных указателей?). Конечно, вам нужно будет корректировать обратный указатель, а также «потомки» std::vector, всякий раз, когда вы переставляете дерево - печальное следствие небольшого дублирования информации (не более, скажем, двусвязного список представлен ;-), но небольшая цена за простоту и скорость такой двунаправленной навигации.