Рубрики

Обзор структур данных | Набор 3 (График, Три, Сегментное дерево и Суффикс-дерево)

Мы обсудили ниже структуры данных в предыдущих двух наборах.

Набор 1: обзор массива, связанного списка, очереди и стека.
Набор 2: Обзор двоичного дерева, BST, кучи и хэша.

9. График
10. Три
11. Сегментное дерево
12. Суффикс Дерево

график

График представляет собой структуру данных, которая состоит из следующих двух компонентов:

  1. Конечное множество вершин также называется узлами.
  2. Конечное множество упорядоченной пары вида (u, v), называемой ребром. Пара упорядочена, потому что (u, v) не совпадает с (v, u) в случае ориентированного графа (диграфа). Пара формы (u, v) указывает, что существует ребро от вершины u до вершины v. Ребра могут содержать вес / значение / стоимость.

V -> Количество вершин.
E -> Количество ребер.

График можно классифицировать на основе многих вещей, ниже приведены две наиболее распространенные классификации:

  1. Направление:
    Ненаправленный график: график, в котором все ребра двунаправлены. Направленный график: график, в котором все ребра однонаправлены.
  2. Вес:
    Взвешенный график: график, в котором вес связан с ребрами. Взвешенный график: график, в котором вес не связан с ребрами.

График может быть представлен разными способами, ниже приведены два наиболее распространенных представления:

Давайте возьмем ниже пример графа два и увидим два представления графа.

  1. Матрица смежности Представление вышеприведенного графа

  2. Список смежности Представление вышеприведенного графика

Time Complexities in case of Adjacency Matrix :
Traversal :(By BFS or DFS) O(V^2)
Space : O(V^2)

Time Complexities in case of Adjacency List :
Traversal :(By BFS or DFS) O(ElogV)
Space : O(V+E)

Примеры: Наиболее распространенный пример графика — найти кратчайший путь в любой сети. Используется в Google Maps или Bing. Другим распространенным приложением графа являются сайты социальных сетей, где предложение друга зависит от количества промежуточных предложений и других вещей.

Trie

Trie — это эффективная структура данных для поиска слов в словарях, сложность поиска с Trie линейна с точки зрения длины слова (или ключа), которую нужно найти. Если мы храним ключи в бинарном дереве поиска, хорошо сбалансированному BST потребуется время, пропорциональное M * log N, где M — максимальная длина строки, а N — количество ключей в дереве. Используя trie, мы можем искать ключ за O (M) время. Так что это намного быстрее, чем BST.

Хеширование также обеспечивает поиск слова в среднем за O (n) время. Но преимущества Trie заключаются в отсутствии коллизий (например, хеширования), поэтому сложность времени наихудшего случая равна O (n). Кроме того, самая важная вещь — Поиск Префикса. С помощью Trie мы можем найти все слова, начинающиеся с префикса (это невозможно при хешировании). Единственная проблема с Tries — они требуют много дополнительного места. Попытки также известны как основополагающее дерево или префиксное дерево.

The Trie structure can be defined as follows :
struct trie_node
{
    int value; /* Used to mark leaf nodes */
    trie_node_t *children[ALPHABET_SIZE];
};


                       root
                    /   \    \
                    t   a     b
                    |   |     |
                    h   n     y
                    |   |  \  |
                    e   s  y  e
                 /  |   |
                 i  r   w
                 |  |   |
                 r  e   e
                        |
                        r

The leaf nodes are in blue.

Insert time : O(M) where M is the length of the string.
Search time : O(M) where M is the length of the string.
Space : O(ALPHABET_SIZE * M * N) where N is number of 
        keys in trie, ALPHABET_SIZE is 26 if we are 
        only considering upper case Latin characters.
Deletion time : O(M)

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

Сегментное дерево

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

Construction of segment tree : O(N)
Query : O(log N)
Update : O(log N)
Space : O(N) [Exact space = 2*N-1]

Пример: он используется, когда нам нужно найти максимум / минимум / сумму / произведение чисел в диапазоне.

Суффикс Дерево

Суффикс-дерево в основном используется для поиска шаблона в тексте. Идея состоит в том, чтобы предварительно обработать текст так, чтобы операция поиска могла быть выполнена во времени, линейном с точки зрения длины образца. Алгоритмы поиска по шаблону, такие как KMP, Z и т. Д., Занимают время, пропорциональное длине текста. Это действительно большое улучшение, потому что длина шаблона, как правило, намного меньше, чем текст.
Представьте, что мы сохранили полную работу Уильяма Шекспира и предварительно обработали ее. Вы можете искать любую строку во всей работе во времени, пропорциональном длине шаблона. Но использование Suffix Tree может быть плохой идеей, когда текст часто меняется, например, текстовый редактор и т. Д.

Дерево суффиксов — это сжатый набор всех суффиксов, поэтому ниже приведены очень абстрактные шаги для построения дерева суффиксов из заданного текста.
1) Генерация всех суффиксов данного текста.
2) Рассмотрите все суффиксы как отдельные слова и создайте сжатый текст.

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

Эта статья предоставлена Абхираджем Смитом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Обзор структур данных | Набор 3 (График, Три, Сегментное дерево и Суффикс-дерево)

0.00 (0%) 0 votes