Структуры данных 101: Расширенные структуры данных в JavaScript

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

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

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

Знание основных структур данных, таких как деревья, стеки и кучи, было бы хорошим фундамент для этой статьи.

Сегодня мы будем изучать:

  • Что такое Попытки?
  • Реализация попыток в JavaScript
  • Что такое самобалансирующийся BST?
  • Что такое деревья сегментов
  • Что такое деревья двоичных индексов?
  • Что нужно узнать дальше

Познакомьтесь со структурами данных

Этот курс содержит подробный обзор всех распространенных ata структурирует и предоставляет подробные сведения об уровне реализации в JavaScript. Также доступно на других языках.

Структуры данных для собеседований по кодированию в JavaScript

Что попытки?

Слово «trie» происходит от слова re trie val . Попытки представляют собой упорядоченную древовидную структуру данных, эффективную при решении проблем программирования, связанных со строками.

Его также называют деревом префиксов или цифровым деревом.

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

  • Дерево всегда представляет собой набор связанных узлов с пустым корневым узлом ▪.
  • Каждый узел представляет собой уникальный алфавит.
  • Каждый узел может указывать на нуль или другие дочерние узлы.
  • Глубина дерева зависит от самого длинного слова , которое оно хранит.
  • Пытается указать один и тот же путь для слов с общим общий префикс .
  • Размер дерева зависит от количества алфавитов (т. е. дочерних узлов) и количество дочерних узлов в дереве зависит от общего количества возможных значений.

Например, в английском языке 26 букв, поэтому количество уникальных количество узлов не может превышать 26. Точно так же в бенгальском языке с 50 буквами будет 50 уникальных узлов..

Плюсы и минусы попыток

Плюсы

  • Получение Trie/ время вставки в худшем случае лучше, чем хэш-таблица и бинарные деревья поиска.
  • Легко вывести все слова в алфавитном порядке
  • Они требуют много памяти для хранения строк.
  • Более сложная, чем другие структуры данных

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

Реализация попыток в JavaScript

Каждый узел в дереве представляет собой алфавит. Типичный узел в дереве состоит из трех элементов данных:

  • char : в нем хранится символ, который должен содержать узел.
  • children [] : массив, состоящий из указателей на дочерние узлы. Размер этого массива зависит от количества алфавитов. Все имеют значение null.
  • isEndWord : флаг, указывающий на конец слова. По умолчанию для него установлено значение false, и он обновляется только тогда, когда слова заканчиваются во время вставки.

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

Эти указатели содержат либо null . или другой trieNode.

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

Чтобы реализовать узел trie, создайте Trienode.js и вставьте следующий код:

 "использовать строго"; module.exports = class TrieNode {constructor (char) {this.children = [];  for (var i = 0; i  

Вставка в дерево

Чтобы вставить ключ (word) в дерево, вы сначала проверяете, существует ли символ в ключе по нужному вам индексу. Если это так, вы устанавливаете для isEndWord последнего символа значение true .

Если префикс присутствует, новый key будет добавлен как расширение последнего префиксного ключа . В последнем случае, если нет общего префикса, дочерние узлы будут добавлены к корневому узлу, который всегда равен нулю.

Длина ключа определяет глубину дерева. Обратите внимание, что пустые ключи не допускаются в дереве, и все ключи хранятся в нижнем регистре.

Всегда не забывайте устанавливать значение isEndWord для последний узел в true.

Создайте файл index.js и добавьте в него следующий код:

 используйте  strict "; const TrieNode = require ('./TrieNode.js'); class Trie {constructor () {this.root = new TrieNode ('');//Корневой узел}; getIndex (t) {return t.charCodeAt  (0) - "a" .charCodeAt (0);}//Функция для вставки ключа в Trie insert (key) {if (key == null) {return;}; key = key.toLowerCase (); let  currentNode = this.root; let index = 0;//Сохранение индекса символа//Итерация дерева с заданным индексом символа,//Если индекс указывает на null//просто создайте TrieNode и спуститесь на уровень для (let  level = 0; level  

В приведенном выше коде создается класс Trie. Корневой узел) инициализируется в конструкторе. Затем мы перебираем символы в ключе и получаем индекс для каждого символа с помощью getIndex () .

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

Если индекс указывает на null, мы создаем TrieNode для перехода на уровень ниже. Наконец, мы помечаем последний узел как листовой, поскольку слово закончилось.

Для ключа с n символами наихудшая временная сложность оказывается O ( n ) O (n) O (n), поскольку нам нужно сделать n n n итераций.

Поиск в Trie

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

  • Если слово не существует , вы обнаружите null до того, как последний символ может быть исчерпан.
  • Если слово является подстрокой другого слова , оно не будет найдено, потому что для его значения isEndWord последнего символа в дереве задано значение false.
  • Если слово существует как путь от от корневого узла до последнего узла и/или узла, отмеченного как конец, то это успешный случай поиска.
 search (key) {if (key == null) {return false; //нулевой ключ} key = key.toLowerCase ();  пусть currentNode = this.root;  пусть index = 0; //Итерация Trie с заданным индексом символа,//Если в какой-то момент он равен нулю, мы останавливаемся и возвращаем false//Мы вернем true, только если мы достигнем листового узла и пройдем//Trie на основе длины ключа  для (var level = 0; level  

Удаление в Trie

Узлы без дочерних ветвей легко удаляются. Листовой узел существует первым, пока не будет удалено все слово. Для префиксов значение isEndWord установлено в false.

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

Чтобы удалить узел в дереве, мы сначала пишем вспомогательную функцию , чтобы проверить, есть ли currentNode имеет дочерние элементы.

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

//Вспомогательная функция hasNoChildren (currentNode) {for (let i = 0; i 

Самобалансирующийся-двоичный-поиск- Деревья

Самобалансирующиеся двоичные деревья поиска — это дерево со сбалансированной высотой , которое автоматически пытается сохранить минимальную высоту при выполнении основных операций.

Сбалансированное дерево — это такое дерево, в котором для каждого узла высота его правого и левого поддеревьев отличается не более чем на 1.

Временная сложность всех трех основных операций — вставка, удаление и поиск занимают O (h) O (h) O (h) время, где h h h — высота двоичного дерева поиска.

Распространенные примеры самобалансирующегося BST включают красно-черные деревья, AVL, Splay Tree, и treaps. Эти BST выполняют вращение влево или вправо после выполнения операций вставки и удаления, сохраняя при этом свойство BTS.

Применение самобалансирующегося BTS

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

Продолжайте обучение.

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

Структуры данных для собеседований по программированию на JavaScript

Деревья сегментов

Дерево сегментов — это древовидная структура данных, используемая для хранения интервалов или сегментов . Он используется в случаях, когда есть несколько запросов диапазона к массиву и модификации элементов одного и того же массива.

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

Перед построением дерева сегментов нам необходимо решить следующее:

  • Значение сохраняется в каждом узле дерева и,
  • операция слияния, которая формирует внутренний родительский узел.

Обычный случай — найти сумму всех элементов в массиве от индексов L до R.

Здесь, в каждом узле (кроме конечных узлов), сумма его дочерних узлов узлов сохраняется.

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

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

Используемая операция слияния зависит от решаемого вопроса. Таким образом, рекурсия завершится в корневом узле, который будет представлять весь массив.

На изображении ниже показан запрос суммы для массива:

  let x = [2, 6, -3, 8, -5];  

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

Деревья сегментов — это гибкая структура данных. Его можно использовать для решения таких задач, как поиск суммы элементов в некоторых сегментах в массиве или поиск минимального запроса всех элементов в массиве с индексами от l до r в O ( l o g N ) O ( logN) O (logN) время.

Деревья двоичных индексов

Бинарное индексированное дерево (также известное как дерево Фенвика) — это структура данных, которая может эффективно обновлять элементы и вычислять суммы префиксов в таблица чисел эффективно.

Она обеспечивает способ представления массива чисел в виде массива или дерева. Сложность по времени для каждой операции над деревьями двоичных индексов составляет O ( l o g N ) O(logN) O (logN). Дерево примет n — 1 n-1 n − 1 узлов.

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

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

Применение деревьев двоичных индексов

  • Деревья двоичных индексов используются для реализации алгоритма арифметического кодирования.
  • Они могут использоваться для подсчета инверсий в массиве в O ( N l o g N ) O(NlogN) O (NlogN) время.

Что изучать дальше

Я надеюсь, что это помогло вам получить хорошее понимание некоторых из более сложных структур данных. Еще многое предстоит узнать об этих и других структурах данных, например:

  • Несвязанная структура данных
  • K-размерные деревья
  • n-арное дерево

Вы можете продолжить обучение, пройдя курс Educative по структурам данных для собеседований по программированию на JavaScript . Курс направлен на то, чтобы дать вам подробное объяснение всех распространенных структур данных JavaScript..

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

Удачного обучения!

Продолжить чтение о структурах данных и алгоритмах

  • 7 структур данных JavaScript, которые вы должны знать
  • Top Data Структуры и алгоритмы, которые должен знать каждый разработчик.
  • Алгоритм 101: как использовать сортировку слиянием и быструю сортировку в JavaScript
Оцените статью
nanomode.ru
Добавить комментарий