Что такое декартово дерево и как его использовать

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

Алгоритмическая часть: понимаете ли вы, откуда у декартова дерева берётся баланс, и что оценка здесь вероятностная. Для мобильной разработки добавляется практический угол: упорядоченного контейнера в стандартной библиотеке Swift нет, поэтому такие структуры пишут руками.

Как отвечать

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

Операции удобнее описывать через split (разрезать по ключу на два дерева) и merge (склеить два дерева, все ключи одного меньше ключей другого). Вставка это split и два merge, удаление это split и merge без вырезанного узла.

func merge(_ l: Node?, _ r: Node?) -> Node? {
    guard let l else { return r }
    guard let r else { return l }
    if l.priority > r.priority {
        l.right = merge(l.right, r)
        return l
    }
    r.left = merge(l, r.left)
    return r
}

Отдельно стоит назвать неявное декартово дерево: ключом становится размер левого поддерева, то есть позиция. Получается массив со вставкой и удалением в середину за логарифм плюс операции над отрезком.

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

Обещают гарантированный логарифм. Гарантии нет, это математическое ожидание при случайных приоритетах, и отдельный запрос вполне может пройти по длинной ветке.

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

Забывают пересчитывать размер поддерева после каждой склейки и разрезания. Обычный вариант продолжит работать, а неявный молча начнёт резать не по той позиции, и ошибка проявится далеко от места, где её внесли.