166
правок
Изменения
→Построение декартово дерева за O(n) для заданного набора ключей
# Результат процедуры <tex>Merge</tex> ставим на место удаляемого элемента.
== Построение декартово дерева за O(n) для из заданного набора ключей элементов ==
Пусть нам известно из каких пар <tex>(x_i, y_i)</tex> требуется построить декартово дерево, причем также известно, что <tex>x_1 < x_2 < \ldots < x_n</tex>.
=== Простой алгоритм построения через рекурсию ===
Рассмотрим набор <tex>y_1 , y_2 , \ldots , y_n</tex>, выберем максимум среди них, пусть это будет <tex>y_k</tex>, и сделаем <tex>(x_k, y_k)</tex> корнем дерева (по свойству пирамиды в корне должен быть элемент с максимальным приоритетом). Проделав тоже самое с <tex>y_1 , y_2 , \ldots , y_{k-1}</tex> и <tex>y_{k+1} , y_{k+2} , \ldots , y_n</tex>, получим соответственно левого и правого сына <tex>(x_k, y_k)</tex>. С полученными наборами поступаем аналогично.
Данный алгоритм построения декартово дерева основан на рекурсии: находим в наборе максимальный <tex>y_k</tex> и назначаем его корнем, найденный <tex>y_k</tex> разбивает набор на два, для каждого из полученного непустого набора запускаем алгоритм построения декартово дерева. === Алгоритм за O(n) ===Будем строить дерево слева направо, то есть начиная с <tex>(x_1, y_1)</tex> по <tex>(x_n, y_n)</tex>, при этом помнить последний добавленный элемент <tex>(x_k, y_k)</tex>. Он будет самым правым, так как у него будет максимальный ключ, а по ключам декартово дерево представляет собой [[Дерево поиска, наивная реализация|двоичное дерево поиска]]. При добавлении <tex>(x_{k+1}, y_{k+1})</tex>, пытаемся сделать его правым сыном <tex>(x_k, y_k)</tex>, это следует сделать если <tex>y_k < > y_{k+1}</tex>, иначе делаем шаг ''по склону вверх'', то есть к предку последнего элемента и смотрим его значение <tex>y</tex>. Делаем это Поднимаемся до тех пор, пока приоритет в рассматриваемом элементе не превысит меньше приоритета в добавляемом, после чего делаем <tex>(x_{k+1}, y_{k+1})</tex> его правым сыном, а предыдущего правого сына делаем левым сыном <tex>(x_{k+1}, y_{k+1})</tex>.
Заметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь по склону вверх (ведь после этого вершина будет лежать в чьем-то левом поддереве, а мы поднимаемся только по правому). Из этого следует, что построение происходит за <tex>O(n)</tex>.
