Войти
Последовательность чисел и производное от них декартово дерево. В информатике, Декартово дерево - это двоичное дерево, полученное из последовательности чисел; он может быть однозначно определен из свойств, что он упорядочен в куче и что симметричный (упорядоченный) обход дерева возвращает исходную последовательность. Представленный Vuillemin (1980) в контексте геометрического поиска по диапазону структур данных, декартовы деревья также использовались в определении treap и рандомизированное двоичное дерево поиска структуры данных для задач двоичного поиска. Декартово дерево для последовательности может быть построено за линейное время с использованием алгоритма на основе стека для поиска всех ближайших меньших значений в последовательности.
Декартово дерево для последовательности различных чисел может быть однозначно определено следующими свойствами:
На основе свойства кучи корень дерева должен быть наименьшим номер в последовательности. Исходя из этого, само дерево также может быть определено рекурсивно: корень - это минимальное значение последовательности, а левое и правое поддеревья - декартовы деревья для подпоследовательностей слева и справа от значения корня. Следовательно, три указанных выше свойства однозначно определяют декартово дерево.
Если последовательность чисел содержит повторения, декартово дерево может быть определено путем определения непротиворечивого правила разрыва связей (например, определения того, что первый из двух равных элементов рассматривается как меньший из двух) перед применяя вышеуказанные правила.
Пример декартового дерева показан на рисунке выше.
Двумерный поиск по диапазону с использованием декартова дерева: нижняя точка (красная на рисунке) в трехсторонней области с двумя вертикальными сторонами и одной горизонтальной стороной ( если область непуста) может быть найден как ближайший общий предок крайних левых и крайних правых точек (синие точки на рисунке) внутри плиты, определенной вертикальными границами области. Остальные точки в трехсторонней области можно найти, разделив ее вертикальной линией через нижнюю точку и рекурсивно. Декартовы деревья могут использоваться как часть эффективной структуры данных для минимальный диапазон запросов, проблема поиска диапазона, связанная с запросами, которые запрашивают минимальное значение в непрерывной подпоследовательности исходной последовательности. В декартовом дереве это минимальное значение может быть найдено в наименьшем общем предке крайнего левого и крайнего правого значений в подпоследовательности. Например, в подпоследовательности (12,10,20,15) последовательности, показанной на первой иллюстрации, минимальное значение подпоследовательности (10) образует наименьшего общего предка крайнего левого и крайнего правого значений (12 и 15). Поскольку самые низкие общие предки могут быть найдены за постоянное время для каждого запроса, используя структуру данных, которая занимает линейное пространство для хранения и которая может быть построена за линейное время, те же границы сохраняются для задачи минимизации диапазона.
Бендер и Фарач-Колтон (2000) изменили эту взаимосвязь между двумя проблемами структуры данных, показав, что наименьшие общие предки во входном дереве могут быть эффективно решены с применением недревесной техники для минимизации диапазона. Их структура данных использует технику обхода Эйлера для преобразования входного дерева в последовательность, а затем находит минимумы диапазона в результирующей последовательности. Последовательность, полученная в результате этого преобразования, имеет особую форму (соседние числа, представляющие высоту соседних узлов в дереве, отличаются на ± 1), которой они пользуются в своей структуре данных; для решения задачи минимизации диапазона для последовательностей, не имеющих этой специальной формы, они используют декартовы деревья, чтобы преобразовать задачу минимизации диапазона в задачу наименьшего общего предка, а затем применяют технику обхода Эйлера, чтобы снова преобразовать проблему в проблему минимизации диапазона для последовательностей с этой специальной формой.
Та же самая проблема минимизации диапазона может также получить альтернативную интерпретацию в терминах двумерного поиска диапазона. Набор конечного числа точек в декартовой плоскости может быть использован для формирования декартового дерева путем сортировки точек по их x-координатам и использования y-координат в этом порядке в качестве последовательности значений, из которых это дерево сформировано. Если S - подмножество входных точек в некоторой вертикальной плите, определяемой неравенствами L ≤ x ≤ R, p - крайняя левая точка в S (точка с минимальной координатой x), а q - крайняя правая точка в S ( один с максимальной координатой x), то наименьший общий предок p и q в декартовом дереве является самой нижней точкой в слэбе. На запрос трехстороннего диапазона, в котором задача состоит в том, чтобы перечислить все точки в пределах области, ограниченной тремя неравенствами L ≤ x ≤ R и y ≤ T, можно ответить, найдя эту самую нижнюю точку b, сравнив ее координату y с T, и (если точка находится в пределах трехсторонней области) рекурсивно продолжается в двух плитах, ограниченных между p и b и между b и q. Таким образом, после того, как крайняя левая и самая правая точки на плите определены, все точки в трехсторонней области могут быть перечислены за постоянное время для каждой точки.
То же самое построение самых низких общих предков в декартовой системе координат. tree, позволяет построить структуру данных с линейным пространством, которая позволяет запрашивать расстояния между парами точек в любом ультраметрическом пространстве за постоянное время для каждого запроса. Расстояние внутри ультраметрики такое же, как и вес минимаксного пути в минимальном остовном дереве метрики. Из минимального остовного дерева можно построить декартово дерево, корневой узел которого представляет собой самое тяжелое ребро минимального остовного дерева. Удаление этого ребра разбивает минимальное остовное дерево на два поддерева, и декартовы деревья, рекурсивно построенные для этих двух поддеревьев, образуют потомков корневого узла декартова дерева. Листья декартового дерева представляют собой точки метрического пространства, а наименьший общий предок двух листьев в декартовом дереве - это самое тяжелое ребро между этими двумя точками в минимальном остовном дереве, вес которого равен расстоянию между двумя точками.. После того, как минимальное остовное дерево найдено и его веса ребер отсортированы, декартово дерево может быть построено за линейное время.
Поскольку декартово дерево является двоичным деревом, естественно используйте его как двоичное дерево поиска для упорядоченной последовательности значений. Однако определение декартова дерева на основе тех же значений, которые образуют ключи поиска бинарного дерева поиска, не работает должным образом: декартово дерево отсортированной последовательности - это просто путь с корнем в самой левой конечной точке, и двоичный поиск в этом дереве вырождается в последовательный поиск в пути. Однако можно сгенерировать более сбалансированные деревья поиска путем создания значений приоритета для каждого ключа поиска, которые отличаются от самого ключа, сортировки входных данных по их значениям ключей и использования соответствующей последовательности приоритетов для создания декартова дерева. Эту конструкцию можно эквивалентно рассматривать в геометрической структуре, описанной выше, в которой x-координаты набора точек являются ключами поиска, а y-координаты - приоритетами.
Эта идея была применена Seidel Aragon (1996), которые предложили использовать случайные числа в качестве приоритета. Структура данных, полученная в результате этого случайного выбора, называется treap из-за сочетания в ней двоичного дерева поиска и функций двоичной кучи. Вставка в treap может быть выполнена путем вставки нового ключа в качестве листа существующего дерева, выбора для него приоритета и последующего выполнения операций поворота дерева вдоль пути от узла к корню tree для исправления любых нарушений свойства кучи, вызванных этой вставкой; аналогичным образом удаление может выполняться путем постоянного изменения дерева, за которым следует последовательность поворотов по одному пути в дереве.
Если приоритеты каждого ключа выбираются случайным образом и независимо один раз, когда ключ вставляется в дерево, результирующее декартово дерево будет иметь те же свойства, что и случайное двоичное дерево поиска, a дерево, вычисляемое путем вставки ключей в случайно выбранную перестановку , начиная с пустого дерева, причем каждая вставка оставляет прежнюю древовидную структуру без изменений и вставляет новый узел как лист дерева. Случайные бинарные деревья поиска изучались гораздо дольше, и, как известно, они хорошо себя ведут как деревья поиска (с большой вероятностью они имеют логарифмическую глубину); такое же хорошее поведение переносится и на трепы. Также возможно, как было предложено Арагоном и Зайделем, изменить приоритеты часто используемых узлов, заставляя их двигаться к корню treap и ускоряя будущие обращения для тех же ключей.
Декартово дерево может быть построено за линейное время из его входной последовательности. Один из методов - просто обработать значения последовательности в порядке слева направо, поддерживая декартово дерево узлов, обработанных до сих пор, в структуре, которая позволяет обход дерева как вверх, так и вниз. Чтобы обработать каждое новое значение x, начните с узла, представляющего значение до x в последовательности, и следуйте по пути от этого узла к корню дерева, пока не найдете значение y меньше x. Этот узел y является родителем x, а предыдущий правый дочерний элемент y становится новым левым дочерним элементом x. Общее время для этой процедуры является линейным, поскольку время, потраченное на поиск родительского элемента y каждого нового узла x, может быть начислено за количество узлов, удаленных из крайнего правого пути в дереве.
Альтернативный алгоритм построения линейного времени основан на задаче всех ближайших меньших значений. Во входной последовательности можно определить левый сосед значения x как значение, которое встречается до x, меньше, чем x, и находится ближе по положению к x, чем любое другое меньшее значение. Правый сосед определяется симметрично. Последовательность левых соседей может быть найдена с помощью алгоритма, который поддерживает стек , содержащий подпоследовательность ввода. Для каждого нового значения последовательности x стек выталкивается до тех пор, пока он не станет пустым или его верхний элемент не станет меньше x, а затем x будет помещен в стек. Левый сосед x является верхним элементом в момент нажатия x. Правых соседей можно найти, применив тот же алгоритм стека к обратной последовательности. Родитель x в декартовом дереве является либо левым соседом x, либо правым соседом x, в зависимости от того, что существует и имеет большее значение. Левые и правые соседи также могут быть эффективно построены с помощью параллельных алгоритмов, поэтому эту формулировку можно использовать для разработки эффективных параллельных алгоритмов для построения декартова дерева.
Другой алгоритм линейного времени для декартова дерева строительство основано на принципе «разделяй и властвуй». В частности, алгоритм рекурсивно строит дерево на каждой половине входных данных, а затем объединяет два дерева, беря правую часть левого дерева и левую часть правого дерева и выполняя стандартную операцию слияния .. Алгоритм также является распараллеливаемым, поскольку на каждом уровне рекурсии каждая из двух подзадач может быть вычислена параллельно, а операция слияния может быть эффективно распараллелена.
Пары последовательных значений последовательности (показаны толстыми красными краями), которые ограничивают значение последовательности x (темная синяя точка). Стоимость включения x в отсортированный порядок, полученный с помощью алгоритма Левкопулоса – Петерсона, пропорциональна логарифму этого числа пар скобок. Levcopoulos Petersson (1989) описывают алгоритм сортировки на основе декартовых деревьев. Они описывают алгоритм как основанный на дереве с максимумом в корне, но его можно напрямую модифицировать для поддержки декартова дерева с условием, что минимальное значение находится в корне. Для согласованности ниже описана именно эта модифицированная версия алгоритма.
Алгоритм Левкопулоса – Петерссона можно рассматривать как версию сортировки по выбору или сортировки по куче, которая поддерживает очередь приоритетов минимумов кандидатов, и что на каждом шаге находит и удаляет минимальное значение в этой очереди, перемещая это значение в конец выходной последовательности. В их алгоритме очередь с приоритетами состоит только из элементов, родительский элемент которых в декартовом дереве уже найден и удален. Таким образом, алгоритм состоит из следующих шагов:
Как показывают Левкопулос и Петерсон, для входных последовательностей, которые уже почти отсортированы, размер очереди приоритетов останется небольшим, что позволяет этому методу использовать преимущества почти отсортированного ввода и работать быстрее. В частности, время работы этого алгоритма в наихудшем случае составляет O (n log k), где k - среднее по всем значениям x в последовательности числа последовательных пар значений последовательности, заключенных в скобки x. Они также доказывают нижнюю границу, утверждающую, что для любых n и k = ω (1) любой алгоритм сортировки на основе сравнения должен использовать сравнения Ω (n log k) для некоторых входных данных.
Декартовы деревья были введены и названы Vuillemin (1980). Название происходит от декартовой системы координат для плоскости: в версии этой структуры Вюйлемена, как и в описанном выше приложении двумерного поиска по диапазонам, декартово дерево для набора точек имеет отсортированный порядок точки по их x-координатам как его симметричный порядок обхода, и он имеет свойство кучи в соответствии с y-координатами точек. Габоу, Бентли и Тарджан (1984) и последующие авторы следовали приведенному здесь определению, в котором декартово дерево определяется из последовательности; это изменение обобщает геометрическую настройку Vuillemin, позволяя использовать последовательности, отличные от отсортированного порядка x-координат, и позволяет применять декартово дерево также к негеометрическим задачам.
