Глупый вопрос зачем в сбалансированном дереве указатель на родителя? Если высота ограничена логарифмом количества элементов то достаточно запоминать путь по которому добрались до узла и не хранить лишний указатель на каждый узел.
Глупый ответ: в данном случае, исключительно чтобы в функции вставки/удаления путь вторым аргументом не передавать.
А так-то да, путь запоминать экономнее.
Сбалансированные двоичные деревья поиска: реализация на Julia