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

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

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

Как отвечать

Базовая оптимизация это отсечение. Если node.value < low, левое поддерево целиком меньше low, идём только вправо. Если node.value > high, идём только влево. Иначе прибавляем значение и спускаемся в обе стороны. Сложность O(h + k), где h это высота, а k число узлов в диапазоне: для сбалансированного дерева O(log n + k), для вырожденного в список O(n).

Варианты под нагрузку:

• итеративный обход со стеком: рекурсия на вырожденном дереве глубиной в десятки тысяч узлов переполнит стек, а у фоновых потоков он меньше, чем у главного. Массив [TreeNode] в роли стека снимает проблему;
• аугментированное дерево: узел хранит сумму своего поддерева, её пересчитывают при вставке и поворотах. Сумма на отрезке считается за O(h) без обхода k узлов;
• статичные данные: выгрузите значения в отсортированный массив, посчитайте префиксные суммы и ищите границы бинарным поиском. Каждый запрос за O(log n);
• частые изменения вперемешку с запросами: дерево Фенвика или дерево отрезков по сжатым координатам.

Для Swift полезно упомянуть цену ARC: обход дерева из class-узлов делает много retain и release, в горячем коде узлы в массиве с индексами вместо ссылок обычно быстрее. И арифметика Int в Swift при переполнении не заворачивается, а останавливает программу, так что для больших сумм подумайте о типе результата.

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

Пишут, что благодаря отсечению сложность O(log n). Если в диапазон попала половина дерева, посетить придётся половину узлов, оценка без k неверна.

Отсекают не ту сторону: при node.value < low уходят влево и теряют все подходящие значения.

Не уточняют границы: включительный ли диапазон, что делать при low > high и с пустым деревом. Спросите об этом до того, как писать код.