Как написать структуру или класс для бинарного дерева поиска

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

Здесь смотрят не на то, помните ли вы определение дерева, а на то, как вы выбираете между class и struct в Swift и доводите код до удаления узла. Следом почти всегда просят удалить узел с двумя детьми и оценить сложность на отсортированном входе.

Как отвечать

Сначала решите, какая семантика нужна:

• класс: final class Node<T: Comparable> с полями value, left: Node?, right: Node?. Ссылочный тип, вставка меняет дерево на месте, рекурсия по опционалам пишется естественно;
• struct напрямую не получится: struct Node { var left: Node? } не скомпилируется, у значимого типа не может быть хранимого свойства, рекурсивно содержащего его самого;
• enum: indirect enum Tree<T: Comparable> { case empty; case node(Tree, T, Tree) } даёт семантику значения, копии дерева независимы, а методы вроде inserting(_:) возвращают новое дерево;
• обобщённость: ограничение T: Comparable вместо жёсткого Int, иначе дерево для строк придётся писать заново.

Поиск и вставка спускаются влево при меньшем значении и вправо при большем. Что делать с дублями, проговорите сами: игнорировать или хранить счётчик. Удаление разбирается на три случая: лист, один потомок, два потомка. В последнем значение узла заменяют минимумом правого поддерева (in-order преемником) и удаляют преемника. Обход in-order отдаёт элементы по возрастанию, его удобно оформить через соответствие Sequence.

Сложность O(h), где h высота дерева. На случайных данных это около O(log n), при вставке отсортированной последовательности дерево вырождается в список и операции становятся O(n). Лечится балансировкой: AVL или красно-чёрное дерево.

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

Пишут только вставку и поиск, а на удалении узла с двумя детьми теряются. Этот случай и есть основная проверка.

Добавляют сильную ссылку на родителя (var parent: Node?) и получают цикл удержания: узлы никогда не освобождаются. Ссылка на родителя должна быть weak.

Называют сложность O(log n) без оговорок. Без балансировки это верно только в среднем, а худший случай встречается на самых обычных данных.