XOR Linked List

Начнем рассматривать сложные структуры данных. Сегодня начнем одной из таких: XOR связный список.

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

В связанном списке XOR вместо хранения фактических адресов памяти каждый узел хранит XOR адресов предыдущего и следующего узлов.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Продолжение обсуждения про XOR Linked List

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

Я нашел идеальную статью по этой теме:

https://www.linuxjournal.com/article/6828?page=0,0

Не обращайте внимание на дату создания. Ибо этот топик актуален до сих пор. Ну и плюсом будет в принципе глянуть на Linux Journal: там публиковалось очень много интересных топиков в свое время.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Обход связного XOR списка

Продолжаем тему XOR Linked List и сегодня поговорим про обходы данного листа.

Перемещаться по списку XOR мы можем как в прямом, так и в обратном направлении. Просматривая список, нам нужно запоминать адреса узла, к которому ранее осуществлялся доступ, чтобы вычислить адрес следующего узла.

Например когда мы находимся в узле С, у нас должен быть адрес B. Из XOR мы выщемляем адрес для C, а при помощи C (и функции npx) мы можем узнать адрес следующей ноды.

Завтра посмотрим на SourceCode для полного понимания данного процесса.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Код вставки элемента в XOR Linked List

Data Science: Алгоритмы и Структуры данных | Чат 💬

Структура данных - Префиксное(нагруженное) дерево - Trie

Сегодня (и последующие несколько дней) разберем еще одну продвинутую структуру данных: Trie

Префиксное дерево (Trie) - эффективная структура данных для поиска информации. Используя Trie, сложность поиска у вас сведется к длине ключа, что является оптимальным пределом.

Используя Trie - вы можете икать и вставлять ключ за О(M): где M максимальная длина строки. Однако будет штраф за то как это хранится.

Еще плюсом Trie будет являеться то, что вы легко сможете вывести все слова в алфавитном порядке

А также поможет вам эффективно решать задачи по поиску префикса(суффикса). Задачу подобную я скоро опубликую: она как раз была недавно в leetcode challenge

Data Science: Алгоритмы и Структуры данных | Чат 💬

Описание операции вставки в Trie

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

Простая структура Node выглядит примерно так:

1. Инициализация детей
2. флаг о конце слова

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

Data Science: Алгоритмы и Структуры данных | Чат 💬

Реализация вставки в Trie (Python)

Data Science: Алгоритмы и Структуры данных | Чат 💬

Расширяющее (косое) дерево - Splay Tree

Основная идея Splay Tree состоит в том, чтобы перенести элемент, к которому недавно осуществлен поиск(или доступ) в корень дерева. Тем самым дать возможность достучаться к нему повторно за O(1).

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

Все операции с Splay Tree выполняются в среднем за O(log N) времени, где N - количество записей в дереве.

В ближайшие дни рассмотрим основные операции над данным деревом.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Операция поиска в Splay Tree

Операция поиска в Splay Tree выполняет стандартный поиск BST, помимо поиска, также происходит и перемещение узла в корень.

Если поиск успешный, то найденный узел перемещается и становится корневым. В противном случае последний узел, к которому было обращение (до достижения NULL) - перемещается в корень.

Доступ к узлу

1. Через корень
2. Узел является дочерним по отношению к корню, либо левым потомком (применим правое вращение), либо правм потомком
3. Другие 2, которые расмотрим в будущем

Data Science: Алгоритмы и Структуры данных | Чат 💬

Jump Search

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

Рассмотрим массив - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, длина - 16. Размер блока возьмем - 4. Jump Search найдет значение 55 с помощью следующих шагов:

1. Переход от индекса 0 к индексу 4
2. Переход с индекса 4 к индеку 8
3. Перейсти с индекса 8 к индексу 12
4. Поскольку элемент с индексом 12 больше 55, мы вернемся на шаг назад. Переходим на индекс 8
5. Выполняем линейный поиск с индекса 8, чтобы получить элемент 55

Data Science: Алгоритмы и Структуры данных | Чат 💬

Оптимально выбрать блок для пропуска в Jump Search

В худшем случае мы должны делать n/m перехов. Где n - длина массива, а m - длина размера перехода. Если проверенное значение больше, чем искомый элемент, мы выполним m-1 сравнений больше, так как будем использовать линейный поиск.

Общее количество сравнений в наихудшем случае будет ((n / m) + m - 1). Значение функции ((n / m) + m - 1) будет минимальным, когда m = √n. Следовательно, лучший размер шага будет являться m = √n

Data Science: Алгоритмы и Структуры данных | Чат 💬

Когда стоит использовать Jump Search

Бинарный поиск - лучше, чем Jump Search. Для чего же тогда использовать Jump Search. У него есть одно преимущество перед бинарным поиском: мы возвращаемся назад только один раз. Для бинарного поиска может потребоваться до O(logN) переходов в ситуации, когда мы захотим найти элемент, который является наименьшим или даже меньше чем наименьший.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Interpolation Sort

Имея отсортированный массив нам надо написать функцию поиска элемента. Линейный поиск сделает это за время O(n) , Jump Search - O(√ n), а бинарный за O(log n).

Поиск с интерполяцией (Interpolation Sort) является улучшением по сравнением с бинарным поиском для экземпляров, где значения в отсортированном массиве равномерно распределены.

Двоичный поиск всегда переходит к центру. Interpolation Sort может идти в разные места в соответствии с значением ключа, по которому выполняется поиск. Например, если значение ближе к последнему элементу, поиск выгоднее начать с конца.

Сложность выйдет O(log(log n)). О том как выбрать значения ключа, поговорим в следующем посте.

Data Science: Алгоритмы и Структуры данных | Чат 💬