Я проиллюстрирую, как это сделать, но не дам вам кода.
Вы начинаете со списка:
1 3 2 4 5 1 2 3 7
Вот он с добавленными позициями, поэтому мы можем поговорить об этом подробнее
1 3 2 4 5 1 2 3 7
0 1 2 3 4 5 6 7 8
Нам нужен новый массив «позиции следующего по величине элемента», который выглядит следующим образом:
1 3 2 4 5 1 2 3 7
0 1 2 3 4 5 6 7 8
1 3 3 4 8 6 7 8 x
Этот последний массив содержит всю необходимую информацию построить желаемое дерево. Проблема в том, как эффективно сгенерировать этот массив.
Мы сгенерируем его, пройдя от задней части массива назад. Отвечая на нужный вопрос в O(log(n)) на каждом шаге. Структура данных, которую я опишу, является вариантом списка пропуска . В упорядоченном поиске по значению он сообщит нам самый низкий индекс, по которому можно найти что-либо большее, чем это значение. Что мы делаем, так это ищем в нем наше значение во времени O(log(n)), а затем вставляем тот факт, что это значение может быть найдено во времени O(log(n)).
Как описано в этой статье, пропускаемый список представляет собой связанный список данных. И затем список данных с более высокой связью, обобщающий кое-что о более низких данных. с «скипами». Затем более высокий связанный список по этому поводу. Каждая точка данных идет на высоту. Половина точек на высоте 0 (только нижний список), половина на высоте 1, четверть на высоте 2 и так далее. Вся структура данных оказывается размером n + n/2 + n/4 + ..., что составляет примерно 2n. Все операции завершаются в среднем log(n) операциями.
Я нарисую его без необходимых указателей для обхода структуры данных, где каждый уровень будет строкой. Что вы можете сделать визуально, набрав right/left/down/up, в вашей программе нужны указатели. Наши фактические узлы всегда будут иметь вид (value, first index met or exceeded). (Вы увидите, что значения узлов могут быть устаревшими, но это будет нормально.)
Теперь в скиплисте высота узла обычно назначается случайным образом. В среднем это срабатывает. Но я буду использовать наибольшую степень двойки, которая делит значение как мой рост. В этом примере достигается хорошее распределение высот без запутанного случайного выбора.
Фокус в том, что когда мы читаем скиплист, мы начинаем сверху и перемещаемся вправо, затем вниз, пока не найдем значение больше чем или равный тому, который мы ищем. Затем мы перемещаемся влево и вниз (слева это значение все еще больше, чем то, которое мы хотим, иначе вниз) и берем минимальный индекс по второму пути, который мы находим. Когда мы вставляем, мы всегда пытаемся переместиться вверх, а затем влево, записывая вновь вставленный индекс по этому следу.
Теперь, чтобы очистить след операций, я добавлю в свою структуру данных пройденный путь во время этой операции. Это означает следующие операции:
l поиск более высокого значения, чтобы начать поиск следующего индекса. s поиск следующего индекса. (Я переключаюсь, как только нахожу это, поэтому l может и не быть, если первое, что я смотрю, это часть s поиска.) i n Вставка нового узла (поскольку это двумерная структура связанного списка, у вас также есть обновления для указателей соседей, которые я не показывал). Это происходит прямо перед последним s, а затем go прямо вверх. Но только если значение для нас новое. u pdating что-то об узле. Они начинаются слева от последнего s earch или i nsert, затем пытаются двигаться вверх, а затем влево. Если это новое наименьшее значение, обновлений не будет.
Теперь помните, что мы начали с:
1 3 2 4 5 1 2 3 7
0 1 2 3 4 5 6 7 8
Первое, что мы хотим в нашем skiplist, это то, что значение 7 можно найти в позиции 8. Этот факт находится на высоте 0, поэтому наш скиплист выглядит так:
next: [x]
skip: (7,8)i
Далее у нас есть тот факт, что 3 можно найти в позиции 7. Поиск следующего по величине значения тривиален. Вставляем еще один факт на уровне 0 и получаем следующее:
next: [8,x]
skip: (3,7)i (7,8)s
Далее значение 2 можно найти в позиции 6. Это вводит новый уровень.
next: [6,7,8,x]
skip: (2,6)i
(2,6)i (3,7)s (7,8)
Далее значение 1 можно найти в позиции 5.
next: [5,6,7,8,x]
skip: (2,6)s
(1,5)i (2,6)s (3,7) (7,8)
Теперь значение 5 встречается в позиции 4. Поскольку это первая сложная задача, буквы указывают, что мы l выбрали, где начать наш поиск, с (2,6) вверху, затем идут вниз, вправо, вправо. Тогда мы s заработали только (7,8). Затем мы i nsert и следующая u дата перемещались налево, налево, вверх. Обратите внимание, что устаревший (1,5) в нижнем левом углу никогда не даст нам неправильного вывода, потому что любой поиск, который его попадет, сначала обнаружит (2,4), поэтому мы знаем, что использовать индекс 4, а не устаревший 5 .
next: [8,5,6,7,8,x]
skip: (2,4)lu
(1,5) (2,4)lu (3,4)lu (5,4)i (7,8)s
Теперь 4 можно найти в позиции 3. На этот раз чтение пошло вниз, влево, влево, чтобы найти начальный (5,4). Наша вставка пошла назад, а затем поднялась прямо вверх, чтобы создать новый уровень. У нас есть много устаревших данных, которые мы не трогали.
next: [4,8,5,6,7,8,x]
skip: (4,3)i
(2,4)l (4,3)i
(1,5) (2,4)l (3,4)l (4,3)i (5,4)s (7,8)
Далее, 2 можно найти в позиции 2. Эти записи существовали, так что это u дата.
next: [3,4,8,5,6,7,8,x]
skip: (4,3)s
(2,2)u (4,3)s
(1,5) (2,2)u (3,4)s (4,3)s (5,4) (7,8)
Мы почти закончили! 3 теперь можно найти в позиции 1. Наши поиски пошли вниз. Затем мы нашли индекс root, обновили его, затем пошли влево, вверх.
next: [3,3,4,8,5,6,7,8,x]
skip: (4,3)s
(2,1)u (4,3)s
(1,5) (2,1)u (3,1)i (4,3)s (5,4) (7,8)
И теперь самую последнюю запись мы ищем вниз, влево, вниз, влево. Для полноты я обновлю структуру данных, чтобы включить ее, хотя мы больше никогда не собираемся смотреть. при 0, первое значение не менее 2 или 3 равно 1, первое значение не менее 4 равно 3, первое значение не менее 5 соответствует 4. И первое значение не менее 7 равно 8.