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

Основываясь на этом свойстве, можно упорядочить активное множество в соответствии с возрастанием x. Из этого следует неубывающий порядок x - y. Пусть дана точка s; точки, для которых s находится в их областях <math>R_1 \;</math>, должны удовлетворять следующим неравенствам: <math>x \le x_s; x - y > x_s - y_s \;</math>.

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