Рекурсивное дерево сплайнов

Question

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

Answer 1

Если я правильно помню, вы строите левое и правое дерево, возвращаясь к целевому узлу. Когда вы найдете цель, вы создаете последние левые и правые деревья, используя (исходные) дочерние элементы цели, присоединяете полученные деревья как новые дочерние элементы цели и возвращаете результат в хвостовой рекурсивной форме (т. Е. Все обратно в стек без дальнейших изменений).

Answer 2

Когда дерево становится полностью «несбалансированным» и действительно большим (скажем, как, например, 100000 ключей int), тогда рекурсивные алгоритмы могут вызвать исключение stackoverflow. Лучше использовать указатель родителя в каждом узле, чтобы получить родителя или прародителя. Это один из способов сделать это. работал нормально для меня.

Результаты времени выполнения здесь очевидны Профилирование времени выполнения Splay Tree