Я пишу реализацию бинарного дерева поиска, и я хочу иметь функцию, которая находит узел и возвращает двусвязный список всех узлов на пути, который потребовался, чтобы попасть туда. Я знаю, что двусвязный список можно преобразовать в двоичное дерево поиска, поэтому было бы очень здорово (и здорово) иметь возможность использовать один и тот же класс.
Однако, если я делаю мелкие копии всех узлы на этом пути и начинают менять свои указатели для построения бинарного дерева поиска, которое я хочу вернуть, я, очевидно, буду уничтожать исходное дерево. Я не могу просто сделать полную копию всех узлов, потому что мне понадобятся ссылки на исходные узлы, которые я буду использовать для изменения исходного дерева (может быть удаление, балансировка, ...).
Например, у меня может быть функция добавления, которая вызывает find, которая возвращает последний узел в пути, куда новый узел будет go, и я могу просто поместить его как одного из дочерних элементов там. Если я пишу самобалансирующийся класс бинарного дерева (Red / Black Tree, AVL Tree, Splay Tree), который я могу выделить из этого подкласса, было бы неплохо иметь доступ по крайней мере к родителю и прародителю узла. Я только что добавил (что я мог бы просто отслеживать с помощью дополнительных указателей, но тогда метод поиска не так универсален).
Конечно, одним из решений является просто написать другой класс. Другое решение состоит в том, чтобы согласиться на односвязный список и использовать другой указатель для ссылки на соответствующий исходный узел. Но на данный момент речь идет не только о том, чтобы решение работало. Я использую язык Java, но мне определенно было бы интересно узнать, есть ли для этого какой-либо другой язык. Это не кажется мне очень возможным, но я мог что-то упустить.
Кто-нибудь знает, есть ли способ сделать это, или есть какие-то предложения относительно того, что я мог бы сделать вместо этого?