Описание тега cartesian-tree
В информатике декартово дерево - это двоичное дерево, полученное из последовательности чисел; он может быть однозначно определен из свойств, что он упорядочен в куче и что симметричный (по порядку) обход дерева возвращает исходную последовательность.
Декартовы деревья также использовались в структурах данных рандомизированного двоичного дерева поиска для задач двоичного поиска. Декартово дерево для последовательности может быть построено за линейное время с использованием алгоритма на основе стека для поиска всех ближайших меньших значений в последовательности.