172
правки
Изменения
→Рекурсивный алгоритм
== Построение декартова дерева ==
Пусть нам известно из каких пар <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> корнем дерева O(по свойству [[Двоичная куча|пирамиды]] в корне должен быть элемент с максимальным приоритетом). Проделав то же самое с <tex>y_1 , y_2 , \ldots , y_{k-1}</tex> и <tex>y_{k+1} , y_{k+2} , n\ldots , y_n</tex>, получим соответственно левого и правого сына <tex>(x_k, y_klog n)</tex>.===
=== Алгоритм за O(n) ===
