Вероятностная альтернатива сбалансированным деревьям

Вступление

Двоичные деревья могут использоваться для представления абстрактных типов данных, таких как словари и упорядоченные списки. Однако, когда мы вставляем элементы по порядку, существует высокая тенденция к тому, что мы получаем вырожденную структуру данных, которая плохо работает (например, вставка 2,3,4,5,6,7,8 в двоичное дерево) . Вот почему мы часто используем сбалансированные древовидные структуры, которые перестраивают древовидную структуру по мере выполнения операций. Списки пропуска могут использоваться как альтернатива сбалансированным деревьям (они могут даже хорошо работать в зависимости от ограничений). Поскольку они не так популярны, как сбалансированные древовидные структуры, я подумал, что написание этой статьи как второй в моей серии о структурах данных может быть полезным.

Связанные списки

Связанный список - это хорошо знакомая структура данных, которую легко и легко реализовать. На следующей диаграмме показан отсортированный односвязный список, в котором каждый узел содержит указатель на своего правого соседа.

Операции с отсортированными связными списками и сложность времени

Обычно мы ищем операции поиска, вставки и удаления. Посмотрим на псевдокоды.

Search (list, searchKey)
// находим searchKey с помощью линейного поиска

Insert (node, newNode) // вставляем newNode как правого соседа узла
newnode.next ← node.next
node.next ← newNode

Delete (node) // удаляем правого соседа узла
obsoleteNode ← node.next
node.next ← node .next.next
бесплатно (obsoleteNode)

Соответственно, средняя сложность по времени будет:
- Поиск: Θ (n)
- Вставить: Θ (1)
- Удалить: Θ (1)

где n - длина связанного списка (или количество узлов в связанном списке)

Недостатки

  • Поиск неэффективен. Трудно выполнить поиск менее чем за O (n) раз
  • Обход выполняется медленно, потому что вам нужно проходить по одному узлу за раз, начиная с первого узла до интересующего узла. Невозможно сразу перейти к середине.

Списки пропуска позволяют устранить эти недостатки.

Идеальные списки пропуска

Давайте внесем некоторые изменения в наш связанный список. В нашем исходном связанном списке каждый узел имеет указатель только на своего правого соседа. Для каждого другого узла давайте добавим указатель на узел, который находится на два впереди. Следующая диаграмма даст лучшее представление.

Для связанного списка мы должны пройти через n узлов во время операции поиска (в худшем случае). Теперь, после нашей модификации, нам нужно пройти только через n / 2 + 1 узлов. Например, если нам нужно найти значение 80,

Начнем с заголовка, на самом высоком уровне. Он указывает на узел со значением 10. 80 больше 10, поэтому мы переходим к узлу со значением 10. Он указывает на узел 28, который снова меньше 80. Мы продолжаем таким образом, пока не достигнем 70. Он указывает на узел узел со значением 90. Поскольку 90 больше 80, мы опускаемся на один уровень ниже. Теперь стрелка указывает на 80. Миссия выполнена !!! Мы прошли только 4 узла вместо 7 (что было бы в случае типичного связного списка).

Давайте сделаем еще один шаг и добавим указатель на каждый четвертый узел, который указывает на узел, который находится на четыре впереди. Следующая диаграмма демонстрирует новую структуру.

Как насчет поиска сейчас? Нам нужно пройти только через n / 4 + 2 узлов. Если мы ищем 80,

Мы можем продолжать делать это таким образом, чтобы каждый (2ˣ) -й узел имел указатель на 2ˣ узлов впереди. Мы можем легко заметить некоторые важные особенности нашей новой структуры данных, которые мы еще не назвали.

  1. Будет максимальное количество уровней log₂ (n) (если быть точным, ceil (log₂ (n)))
    [в нашем примере log₂ (8) = 3 уровня]
  2. Каждый более высокий уровень будет содержать половину количества элементов, чем на более низком уровне. [в нашем примере на уровне 1 8 элементов / узлов, на уровне 2 - 4 элемента, а на уровне 3 - только 2 элемента]
  3. Узлы заголовка и NIL (назовем это так) находятся на каждом уровне
  4. Это очень похоже на сбалансированное двоичное дерево.

Теперь мы можем выполнять поиск за время O (log n) даже в наихудшем сценарии, что является значительным улучшением по сравнению со связанным списком. Это то, что мы называем Perfect Skip List (наконец, мы дали имя нашей новой структуре данных 😊) . Несмотря на хорошую производительность поиска, вставка и удаление сейчас затруднены, потому что очень сложно поддерживать этот шаблон, поскольку новые узлы могут быть вставлены в любом месте или любой существующий узел может быть удален. После каждой вставки / удаления мы не можем реструктурировать весь список. Как мы с этим справляемся? С помощью рандомизации.

Рандомизированные списки пропусков

Давайте немного ослабим наши ограничения. Ранее мы говорили, что каждый уровень должен содержать половину количества элементов по сравнению с уровнем ниже. Теперь давайте ожидаем, что на каждом уровне будет вдвое меньше элементов, чем на нижнем уровне.

Предположим, у меня есть монета. Когда я вставляю новый узел, я подбрасываю свою монету (любое количество раз), пока не получу хвост. Количество последовательных голов, которые я получил, решит, сколько уровней я должен добавить к этому конкретному узлу.

Вставить операцию

Следующая диаграмма ясно показывает, как вставить 35 в список.

Шаг 1: вставьте 35 и создайте указатель на правого соседа.
Шаг 2: Подбросьте монету.
Шаг 3: Так как это ГОЛОВКИ, добавьте один уровень и соедините его с ближайшим узлом справа как минимум двумя уровнями. Соедините ближайший узел на левой стороне как минимум с двумя уровнями
Шаг 4: Подбросьте монету еще раз.
Шаг 5: Так как это ХВОСТЫ, оканчиваются.

Предположим, что если бы мы получили еще один HEADS до получения TAILS, тогда наш текущий узел имел бы три уровня, в то время как заголовок и NIL имели бы только 2 уровня. В таком случае мы должны добавить дополнительные уровни к узлам заголовка и NIL. Узлы заголовка и NIL всегда должны иметь то же количество уровней, что и узел с максимальным количеством уровней.

Операция удаления

Удалим сейчас 70.

Я считаю, что сама диаграмма все объясняет.

Операция поиска выполняется точно так же, как и в идеальном списке пропуска.

Событие подбрасывания монеты - это то, что вводит рандомизацию. Поскольку вероятность получения HEADS составляет 0,5, мы пытаемся воссоздать рандомизированный список пропусков, который похож на наш идеальный список пропусков, где каждый уровень имеет только половину количества элементов по сравнению с уровнем ниже.

Интересная тема - что произойдет с потреблением времени и памяти, а также со структурой списка пропуска, если мы будем использовать другую вероятностную функцию.

[Дополнительную информацию по этой теме можно найти в ресурсе, предоставленном внизу]

Также важно отметить, что мы жертвуем памятью ради повышения производительности. Добавление дополнительных уровней означает добавление дополнительных указателей (каждый указатель занимает 8 байтов в 64-разрядной системе).

Заключение

  • Список пропуска может использоваться как альтернатива сбалансированным деревьям (например, деревьям AVL) и самонастраивающимся деревьям (например, деревьям развертки). Однако список пропуска - это относительно простая структура данных, которую очень легко реализовать.
  • Мы можем легко изменить списки пропуска, чтобы ввести параллелизм (есть даже параллельные списки пропуска без блокировки)
  • Списки пропуска, как правило, используют немного больше памяти ради сокращения затрат времени (компромисс между памятью и производительностью неизбежен в любой структуре данных)

Последний важный вопрос. Почему мы называем это пропускаемым списком? Потому что мы пропускаем узлы во время обхода (если вы еще не догадались 😂)

Источник: Пью У. (1990). Списки пропуска: вероятностная альтернатива сбалансированным деревьям. Сообщения ACM, 33 (6), 668–676.