Прямолинейное остовное дерево: различия между версиями

Чтобы найти подмножество активных точек, для которых s находится в их областях <math>R_1 \;</math>, вначале необходимо найти наибольшее x, такое, что <math>x \le x_s \;</math>, а затем выполнять обработку в порядке убывания x, до тех пор, пока не будет достигнуто <math>x - y \ge x_s - y_s \;</math>. Поскольку упорядочение производится только по одному измерению, использование любого бинарного дерева поиска со стоимостью операций вставки, деления и запроса, равной O(log n), получаем алгоритм с временем исполнения O(n log n). Бинарные деревья запроса также требуют балансировки. Кроме того, можно использовать списки с пропусками [2], использующие рандомизацию во избежание проблемы явной балансировки, но демонстрирующие ожидаемое поведение на уровне O(log n).