Какая структура данных используется для реализации бинарного дерева с ссылками на родителя и двух дочерних узлов

Что проверяют

Умеете ли вы описать связную структуру узлов и понимаете ли, зачем узлу ссылка наверх и чем за неё платят. Следом почти всегда просят найти следующий по порядку элемент или удалить узел, где ссылка на родителя и пригождается.

Как отвечать

Такое дерево строится на связанных узлах: каждый узел это объект с данными и тремя ссылками.

class Node<T> {
    T value;
    Node<T> left, right, parent;
}

Хорошая опора на JDK: так устроен java.util.TreeMap. Его внутренний класс TreeMap.Entry хранит ключ, значение, ссылки left, right, parent и флаг цвета красно-чёрного дерева.

Что даёт parent:

• следующий по порядку узел: находится без стека. Если есть правое поддерево, спускаемся в его минимум, иначе поднимаемся по родителям, пока не придём слева. Так работает итератор TreeMap;
• удаление и повороты: при балансировке узел перевешивают к родителю, и без ссылки его пришлось бы искать от корня;
• путь до корня: глубина узла и общий предок считаются подъёмом за O(h).

Цена: лишнее поле в каждом узле (4 байта при сжатых указателях, 8 без них) и обязанность поддерживать ссылку в каждой операции, меняющей структуру. Альтернативы: хранить путь в стеке при обходе или взять массив, где у узла i дети 2i+1 и 2i+2, а родитель (i-1)/2. Массив годится только для полного дерева, как в куче PriorityQueue.

Сложность операций задают не ссылки, а высота: O(log n) у сбалансированного дерева и O(n) у выродившегося в список.

Где спотыкаются

Забывают обновить parent при вставке, удалении или повороте. Спуск сверху вниз продолжает работать, ломается только подъём, и такой баг долго не проявляется.

Генерируют equals, hashCode и toString через IDE или @Data из Lombok. Узел идёт в родителя, родитель в ребёнка, и всё заканчивается StackOverflowError. То же с Jackson при сериализации, там помогает @JsonBackReference.

Боятся, что цикл «ребёнок и родитель» вызовет утечку памяти. Сборщик мусора в Java трассирующий, недостижимые объекты с циклическими ссылками он собирает спокойно.