Сортировка декартовым деревом
Суть алгоритма в том, что на основании массива строится так называемое декартово дерево. А из построенного декартового дерева очень легко получить все элементы в порядке возрастания или убывания.
Компания EDISON всегда рада приобщиться к прекрасному.
Один из наших классических проектов — диагностика хранилища документов Vivaldi, благодаря чему оптимизирован одновременный доступ к тысячам документам и произведениям в сетевой библиотеке.
Мы очень любим сеять разумное, доброе, вечное! 😉
В рамках этой статьи я решил воздержаться от подробной теории и не стану разъяснять, что такое декартово дерево, как его построить и какие с ним возможны операции. Это уже прекрасно сделано и до меня — на Хабре есть превосходный материал, где все эти моменты удачно и подробно освещены — в конце этой лекции есть раздел «Ссылки», где можно перейти к этим хабрастатьям. В дальнейшем я буду освещать некоторые моменты, характерные для этой структуры, но при этом подразумевается, что вы понимаете её специфику или, в случае заинтересованности, готовы её изучить по указанным ниже ссылкам.
Декартово дерево является гибридной структурой, объединяющей в себе свойства кучи и бинарного дерева поиска. Для этого дерева есть синонимы, которые будут использоваться в статье:
дерамида (дерево + пирамида),
трип (treap — tree + heap)
и даже дуча (дерево + куча).
Давайте возьмём для примера вот этот массив:
и последовательно взглянем, как для него выглядит двоичное дерево поиска, куча и дерамида.
Бинарное дерево поиска
Внешний вид дерева сильно зависит от того, как изначально расположены элементы массива. На рандомных данных, дерево с высокой долей вероятности получится несбалансирвоанным, с гораздо большим количеством уровней, по сравнению с оптимальным. В нашем примере образовалось 7 уровней. Если бы элементы массива располагались, например, в таком порядке:
25, 28, 29, 23, 30, 27, 24, 22, 21, 26
дерево поиска бы получилось сбалансированным, с минимально возможным количеством уровней (= 4). Сортировка с помощью сбалансированного дерева имела бы сложность по времени: . Но в случае несбалансированного дерева может деградировать и до .
В предыдущей хабрастатье рассмотрена сортировка бинарным деревом поиска, а также её интересная модификация, позволяющая гарантировано сортировать с временно́й сложностью .
Чем более несбалансированным будет дерево поиска, тем более затратным будет его обход.
С другой стороны, хранение данных в дереве поиска весьма удобно с организационной точки зрения, позволяет с этими данными делать очень многие операции, сортировать в том числе.
Родитель в двоичном дереве поиска необязательно больше чем потомок. Но при этом левый потомок всегда меньше родителя, правый потомок всегда больше родителя (или равен ему).
Максимальный элемент массива при построении дерева поиска попадает где-то в правое поддерево. Чтобы этот максимум извлечь, дерево поиска надо полностью обойти.
Бинарная куча
В обычной куче очень просто организованы взаимосвязи «родитель — потомок», они привязаны к самим индексам элементов.
На рисунке на самом деле пока ещё не куча, поскольку такое дерево, изначально построенное на рандомном массиве ещё не является сортирующим. Нужно обойти каждый элемент и сделать для него просейку. В результате элементы в массиве перестроятся так, что каждый родитель будет больше своего потомка:
Максимальный элемент находится в корне дерева. Его расположение известно, его искать не нужно. С другой стороны, при если извлечь максимум из кучи (и вместо него в корень дерева приходится ставить какой-то другой элемент массива), куча перестаёт быть сортирующим деревом, её нужно опять просеивать.
Декартово дерево
И, наконец, декартово дерево. Взаимосвязи установлены таким образом, что с одной стороны, оно является кучей, если смотреть на значения элементов. Все родители больше своих потомков:
С другой стороны, структура является бинарным деревом поиска, если смотреть на индексы элементов. На изображении в дереве для наглядности убрали в узлах значения элементов, оставили только индексы. Каждый левый потомок меньше родителя, каждый правый потомок — больше родителя:
С одной стороны, мы имеем быстрый доступ к максимальному элементу. Так как это куча, то максимум находится в корне.
С другой стороны, из структуры легко можно удалить максимум и работать с оставшимися данными дальше. Так как это бинарное дерево поиска, удаление корня не связано с большими затратами. Во взаимосвязях «родители-потомки» происходят относительно небольшие изменения, в корень декартова дерева попадает новый максимум и можно работать дальше.
Каждый элемент характеризуется двумя числами — значением элемента и индексом элемента в массиве. Индекс можно считать за координату X, значение — за Y, а сам элемент интепретировать как точку на координатной плоскости. Если родителей и потомков соединить стрелками, то получается примерно такая картина:
Фигура на графике полностью изоморфна декартову дереву чуть выше.
Сортировка декартовым деревом :: Cartesian tree sort
- I. На основании неотсортированного массива строим декартово дерево:
- I.1. Перебираем элементы массива слева-направо.
- I.1. Если это первый элемент массива, то он просто является самым первым узлом декартова дерева.
- I.2. Если это не первый элемент массива, считаем что это декартово дерево, состоящее из одного элемента. Производим операцию Merge этого дерева с тем деревом, которое построено из предыдущих элементов.
- II.1. Текущий максимальный элемент — корень дерева.
- II.2. Удаляем из дерева корень, сам максимальный элемент переносим в дополнительный массив.
- II.3. После удаления корня структура распалось на два декартова дерева.
- II.4. Для этих двух деревьев производим операцию Merge. Новым текущим максимумом становится один из корней объединяемых деревьев.
- II.5. Для нового максимума снова повторяем действия II.1-II.4.
Сложность
Декартово дерево с минимальными затратами обрабатывает отсортированные и почти отсортированные (причём неважно, по возрастанию или убыванию) участки массива. Вот, например, так выглядит процесс для реверсно упорядоченного массива:
Самая затратная часть алгоритма — это операция Merge, которую для каждого из n элементов приходится делать дважды — сначала при построении дерамиды и затем при её разборке. На рандомных данных однократная операция Merge обходится в , но для элементов, находящихся в упорядоченных областях массива стоимость операции O(1).
Таким образом, средняя и худшая временна́я сложность сортировки — , лучшая — O(n).
По дополнительной памяти дела обстоят похуже — O(n). Если бы декартово дерево было просто разновидностью кучи, то затраты были бы O(1). Но cartesian tree — это также и дерево бинарного поиска, из-за чего для всех n элементов приходится отдельно хранить взаимосвязи «родители-потомки».
Кроме того, реализация именно в таком виде означает, что это внешняя сортировка — отсортированные элементы собираются в отдельном массив. А это ещё O(n) по дополнительной памяти.
Ссылки
Cartesian
Декартово дерево: Часть 1, Часть 2, Часть 3
Статьи серии:
- Excel-приложение AlgoLab.xlsm
- Сортировки обменами
- Сортировки вставками
- Сортировки выбором
- Сортировки кучей: n-нарные пирамиды
- Сортировки кучей: числа Леонардо
- Сортировки кучей: слабая куча
- Сортировки кучей: декартово дерево
- Сортировки кучей: турнирное дерево
- Сортировки кучей: восходящая просейка
Источник
Построение сбалансированного бинарного дерева поиска из отсортированного массива
💡 Во-первых, надо понимать отличие простого двоичного поискового дерева от сбалансированного.
Двоичное дерево поиска называется сбалансированным по высоте, если для каждой его вершины высоты левого и правого поддеревьев различаются не больше, чем на $1$.
➡ В теории структур данных такие деревья называют AVL-tree.
Сейчас я покажу $2$ сбалансированных по высоте двоичных дерева поиска.
Рисунок — сбалансированное по высоте двоичное дерево поиска
Рисунок — идеально сбалансированное двоичное дерево поиска
💡 Во-вторых, при построении бинарного дерева из массива оно должно получаться автоматически сбалансированным, то есть при добавлении очередной вершины не нужно выполнять специальную операцию, называемую балансировкой.
💡 В-третьих, построение дерева не должно зависеть от количества элементов массива. Речь про четное или нечетное количество элементов массива. То есть алгоритм формирования дерева должен быть универсальным ( это одно из базовых свойств алгоритма — массовость ).
💡 В-четвертых, обязательно массив чисел, на основе которого получается дерево, должен быть отсортирован. Если это условие не выполняется, то полученное дерево не будет являться сбалансированным ( будут перекосы ).
Для анализа алгоритма построения бинарного дерева из массива возьму такие данные:
$5$ $8$ $12$ $20$ $33$ $38$ $49$ $50$ $77$ $91$ $99$ значение $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ индекс Всего в массиве $11$ целых чисел. Они упорядочены по возрастанию! Эти числа образуют последовательность на отрезке от $0$ до $10$ ( беру значения по индексам ).
➡ Формирование дерева будет происходить рекурсивно, так как это максимально удобно.
На каждом этапе я буду выбирать «центральный» элемент. Его индекс легко рассчитать по формуле: $\frac<[левая\ граница]\ +\ [правая\ граница]>$.
Находим индекс центрального элемента: $\frac = 5$. Значение этого элемента равно $38$. Очевидно, что вершина с этим значением будет корнем двоичного сбалансированного по высоте дерева.
$5$ $8$ $12$ $20$ $33$ $38$ $49$ $50$ $77$ $91$ $99$ значение $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ индекс 
Числа, которые меньше $38$ ( $5,\ 8,\ 12,\ 20,\ 33$ ), будут добавлены в левое поддерево относительно корня, большие ( $49,\ 50,\ 77,\ 91,\ 99$ ), будут добавлены в правое поддерево.
Находим индекс «центрального» элемента, расположенного в левой части, относительно значения $38$: $\frac = 2$. Значение этого элемента равно $12$.
$5$ $8$ $12$ $20$ $33$ $38$ $49$ $50$ $77$ $91$ $99$ значение $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ индекс 💡 Есть такой нюанс, связанный с поведением рекурсивной функции, которая формирует дерево. Дело в том, что сначала строятся узлы левого поддерева, а затем достраиваются вершины из правого поддерева. По этой причине на этапе #$3$ сначала будут добавляться вершины в левое поддерево относительно узла $12$.
Индекс центрального элемента: $\frac = 0$. Значение этого элемента равно $5$.
$5$ $8$ $12$ $20$ $33$ $38$ $49$ $50$ $77$ $91$ $99$ значение $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ индекс Индекс центрального элемента: $\frac = 1$. Значение этого элемента равно $8$.
$5$ $8$ $12$ $20$ $33$ $38$ $49$ $50$ $77$ $91$ $99$ значение $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ индекс Индекс центрального элемента: $\frac = 3$. Значение этого элемента равно $20$.
$5$ $8$ $12$ $20$ $33$ $38$ $49$ $50$ $77$ $91$ $99$ значение $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ индекс Индекс центрального элемента: $\frac = 4$. Значение этого элемента равно $33$.
$5$ $8$ $12$ $20$ $33$ $38$ $49$ $50$ $77$ $91$ $99$ значение $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ индекс ➡ В результате левое поддерево относительно корня ( вершина с ключом $38$ ) отстроено. Аналогичным образом формируется и правое поддерево.
На следующей картинке показано конечное сбалансированное по высоте двоичное дерево поиска, построенное на основе данных из приведенного массива целых чисел:
Рисунок — полностью построенное сбалансированное бинарное дерево поиска
А вот программная реализация функции с подробными комментариями, которая формирует сбалансированное по высоте двоичное дерево из массива:
Источник
