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

1. Трие

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

Если бы мы хотели вставить слово «Корова», мы бы сначала создали узел C, поскольку он еще не существует, затем мы должны создать узел для O, который соединяется с C, а затем создать узел W, который соединяется с O.

Для слова «Cat» мы уже создали узел для C. С этим мы сразу перейдем к узлу для A, который подключается к C, узлу для T, который подключается к A, и создадим узел для S, который подключается Т.

Для слова «Кобра» мы перейдем непосредственно к B, поскольку у нас уже есть соединенные первые два узла. После создания узла для B, который подключается к O, мы могли бы создать узел для R, который подключается к B, а затем узел для A, который подключается к R.

Как видите, эта структура данных эффективна для хранения в ней самых разных слов. Настоящая сила в том, что мы можем искать внутри него префиксы. Допустим, мы хотели поискать «Кот», чтобы узнать, существует ли он. Мы бы проверили, присутствует ли C. Если да, мы проверяем, присутствует ли A, а затем T. Если все проверяется, возвращаемое значение будет «true». Обратите внимание, что и вставка слов, и поиск слов являются операцией O (M), где M - длина слова.

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

2. Непересекающееся множество

Непересекающееся множество также известно как объединение-поиск. Он отслеживает набор элементов на несколько непересекающихся неперекрывающихся подмножеств. Я знаю, что это может показаться сложным, но на самом деле это не так. Все, что у вас есть, это две основные функции: объединение и поиск. «Union» объединит два подмножества в один, а затем «Найти» выполнит поиск, чтобы определить, находятся ли два объекта в одном подмножестве. Допустим, у меня всего три подмножества, каждое из которых содержит группу чисел.

У каждого подмножества есть родительский элемент, где все числа внутри подмножества указывают на этот конкретный родительский элемент.

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

Я также могу решить проверить, входят ли два числа в одно и то же подмножество. Это делается с помощью операции поиска. Все, что нужно для этого, - это проверить, одинаковые ли их родители. Если их родители останутся такими же, они принадлежат к одному подмножеству.

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

3. TreeMap

Treemap наследуется от Hashmap. Разница в том, что записи сортируются по порядку ключей или по настраиваемому сравнительному классу, который вы предоставляете конструктору. Если бы мы пытались сохранить запись целочисленного сопоставления со строкой, все записи внутри вашей древовидной карты были бы отсортированы в порядке возрастания на основе этого целочисленного значения. Под капотом эта структура данных использует красно-черное дерево для эффективного поддержания порядка. Производительность для вставок и поиска на самом деле составляет O [log (N)].

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

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

4. Скилист

Список пропуска - это более быстрый способ поиска узлов внутри связанных списков. В обычном связном списке вам придется искать по каждому отдельному узлу, если вы хотите, чтобы он выполнял поиск определенного узла, что заняло бы время O (N), где N - количество узлов. В списке пропусков у вас есть экспресс-полоса над обычным связанным списком. Итак, у вас есть обычная полоса, которая имеет все соединения с каждым узлом в вашем связанном списке, а затем ваша экспресс-полоса пропускает кучу разных узлов.

Допустим, я хотел найти узел 45 на следующем изображении.

Сначала я перейду на свою экспресс-полосу, которая начинается на узле 10. Это меньше, чем 45, поэтому мне нужно перейти к узлу 30. В результате я должен был пропустить кучу узлов в моей обычной полосе. . 30 также меньше 45, поэтому я перейду к узлу 58, который больше 45. Теперь я знаю, где мне нужно начать поиск на моей обычной полосе. Итак, с узла 30 я перейду к 43, а затем к 45. Для списков пропуска все операции поиска, вставки и удаления будут O [log (N)].

Когда бы вы это использовали? Что ж, если нам нужна упорядоченная потокобезопасная структура данных в распределенной среде. Если у нас есть сбалансированное дерево, и нам нужно перебалансировать его в распределенной среде, где у нас есть много разных потоков, пытающихся получить доступ к частям памяти внутри этого дерева, это потребует от нас потенциально новой текстовой блокировки для огромной части дерева. Это очень неэффективно, потому что во время ребалансировки этого дерева могут быть большие части дерева, которые даже не изменяются. Однако для скиплиста мы можем иметь ту же функциональность, что и сбалансированные деревья, и мы можем поместить мьютекс на каждый отдельный узел, таким образом, нам нужно только заблокировать узлы, которые напрямую затронуты.

5. B-дерево

B-Tree - это самобалансирующееся двоичное дерево. В обычных бинарных деревьях у нас есть возможность получить деградированное дерево, если оно плохо сбалансировано. У нас может быть группа узлов внутри этого дерева, которые по сути представляют собой просто связанный список. Если наше дерево ухудшается до этого, поиск, вставка и удаление становятся O (N). Когда дерево сбалансировано, они становятся O [log (N)]. B-дерево гарантирует, что наше дерево всегда сбалансировано каждый раз, когда происходит вставка или удаление. Каждый узел внутри B-дерева содержит ключи, которые представляют собой просто данные, представленные внутри узлов. Порядок пчелиного дерева - это максимальное количество детей, которое может иметь каждый узел. Итак, для каждого ключа внутри узла у нас могут быть дополнительные узлы в качестве наших дочерних узлов, если они больше ключа слева и меньше ключа справа.

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

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