Как реализовать класс для нод дерева вручную без рекордов в Java

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

Понимаете ли вы, чем запись (record) отличается от обычного класса и почему для изменяемой структуры данных она не подходит. Параллельно смотрят на инкапсуляцию, дженерики и рекурсию. Следом обычно просят вставку, обход и оценку сложности.

Как отвечать

Сначала объясните, зачем вообще «без рекордов». Поля записи final, наследоваться от другого класса она не может, а equals, hashCode и toString генерируются по всем компонентам. Для дерева, где при вставке и удалении переставляются ссылки на детей, нужны изменяемые поля. Запись уместна только в неизменяемом дереве, где вставка возвращает новые узлы по пути к корню.

Каркас класса:

• дженерики: Node<T extends Comparable<? super T>> вместо жёсткого int, тогда дерево работает с любыми сравнимыми значениями;
• поля: final T value и изменяемые Node<T> left, right. Для дерева с произвольным числом детей List<Node<T>> children, для навигации вверх ссылка parent;
• инкапсуляция: узел объявляется private static class Node<T> внутри BinarySearchTree<T>. static важен: нестатический вложенный класс держит скрытую ссылку на внешний объект. Наружу торчат методы дерева (add, contains, remove), а не поля узла;
• дубликаты: решите явно, игнорировать их, класть вправо или хранить счётчик в узле;
• обход: in-order, pre-order и post-order рекурсией, плюс итеративный вариант со стеком на ArrayDeque, а не на устаревшем Stack.

Назовите сложность: поиск и вставка O(log n) в сбалансированном дереве и O(n) в вырожденном. На отсортированном входе дерево вырождается в список, спасает балансировка (AVL, красно-чёрное).

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

Генерируют equals, hashCode и toString средой разработки по всем полям. Со ссылкой на parent получается цикл и StackOverflowError, а без неё сравнение двух узлов обходит всё поддерево.

Пишут только рекурсивную вставку. На вырожденном дереве в сотни тысяч узлов глубина рекурсии упирается в размер стека потока.

Сравнивают значения через ==. С Node<Integer> это случайно работает на числах от -128 до 127 из кеша Integer и ломается на остальных, сравнивать нужно через compareTo или equals.