Структуры данных важны в компьютерном программировании для быстрой и эффективной организации, управления и хранения данных. Инженеру-программисту важно хорошо разбираться в различных структурах данных.
Эти знания полезны, чтобы помочь вам решать проблемы во время собеседований по кодированию и создавать быстрые и эффективные приложения.
Сегодня мы рассмотрим некоторые расширенные структуры данных, такие как сегментированные деревья, попытки, самобалансирующиеся деревья и деревья двоичных индексов.
Знание основных структур данных, таких как деревья, стеки и кучи, могло бы стать хорошей основой для этой статьи.
Что такое Tries?
Слово «trie» происходит от слова re trie val. Попытки представляют собой упорядоченную древовидную структуру данных, эффективную при решении проблем программирования, связанных со строками.
Его также называют префиксным деревом или цифровым деревом.
Попытки используются при поиске слов по словарю, проверке орфографии и в поисковых системах путем создания автопредложений. Некоторые свойства необходимы для поддержания общей эффективности дерева, они включают:
- Дерево — это всегда набор связанных узлов с пустым корневым узлом.
- Каждый узел представляет собой уникальный алфавит.
- Каждый узел может указывать на нулевые или другие дочерние узлы.
- Глубина дерева зависит от самого длинного слова, которое оно хранит.
- Пытается указать один и тот же путь для слов с общим префиксом.
- Размер дерева зависит от количества алфавитов (т. Е. Дочерних узлов), а количество дочерних узлов в дереве зависит от общего количества возможных значений.
Например, в английском языке 26 букв, поэтому количество уникальных узлов не может превышать 26. Точно так же в бенгальском языке с 50 буквами будет 50 уникальных узлов.
Плюсы и минусы Trie
Плюсы
- Время извлечения / вставки Trie в худшем случае лучше, чем в хэш-таблице и деревьях двоичного поиска.
- Все слова легко распечатать в алфавитном порядке.
Минусы
- Им требуется много памяти для строк.
- Более сложный, чем другие структуры данных
Реализация попыток в JavaScript
Каждый узел в дереве представляет собой алфавит. Типичный узел в дереве состоит из трех членов данных:
- char: Здесь хранится символ, который должен содержать узел.
- children[ ]: Массив, состоящий из указателей на дочерние узлы. Размер этого массива зависит от количества алфавитов. Все имеют значение null.
- isEndWord: Флаг, указывающий на конец слова. По умолчанию установлено значение false и обновляется только тогда, когда слова заканчиваются во время вставки.
Trie будет реализовано с использованием TrieNodeкласса, и каждый узел будет иметь не более 26 дочерних элементов, если мы храним английские слова. Корневой узел (обычно помещаемый сверху) содержит 26 указателей, каждый из которых представляет букву английского алфавита.
Эти указатели содержат одно nullили другое trieNode.
Дочерние указатели имеют нулевой индекс, и все слова хранятся сверху вниз. Не забывайте всегда устанавливать isEndWordфлаг true для последнего символа, чтобы указать конец слова.
Чтобы реализовать узел trie, создайте Trienode.jsфайл и вставьте следующий код:
«use strict»;module.exports = class TrieNode{constructor(char){this.children = [];for(var i=0; i<26; i++){ //Total # of English Alphabetsthis.children[i]=null;}this.isEndWord = false; //will be true if the node represents the end of wordthis.char = char; //To store the value of a particular key}//Function to mark the currentNode as LeafmarkAsLeaf(){this.isEndWord = true;}//Function to unMark the currentNode as LeafunMarkAsLeaf(){this.isEndWord = false;}}
Вставка в дерево
Чтобы вставить ключ (слово) в дерево, вы сначала проверяете, существует ли символ в ключе по нужному вам индексу. Если это так, вы устанавливаете isEndWordпоследний символ на true.
Если префикс присутствует, новый ключ будет добавлен как расширение последнего префиксного ключа. В последнем случае, если нет общего префикса, дочерние узлы будут добавлены к корневому узлу, который всегда имеет значение NULL.
Длина ключа определяет глубину дерева. Обратите внимание, что пустые ключи не допускаются в дереве, и все ключи хранятся в нижнем регистре.
Всегда не забывайте устанавливать isEndWordзначение последнего узла равным true.
Создайте index.jsфайл и добавьте в него следующий код:
use strict»;const TrieNode = require(‘./TrieNode.js’);class Trie{constructor(){this.root = new TrieNode(»); //Root node};getIndex(t){return t.charCodeAt(0) — «a».charCodeAt(0);}//Function to insert a key in the Trieinsert(key){if (key == null){return;};key = key.toLowerCase();let currentNode = this.root;let index = 0;//Store the character index//Iterate the trie with the given character index,//If the index points to null//simply create a TrieNode and go down a levelfor (let level=0; level<key.length; level++){index = this.getIndex(key[level]);if (currentNode.children[index] == null){currentNode.children[index] = new TrieNode(key[level]);console.log(String(key[level]) + » inserted»);}currentNode = currentNode.children[index];}//Mark the end character as leaf nodecurrentNode.markAsLeaf();console.log(«‘» + key + «‘ inserted»);};//Function to search a given key in Triesearch(key){return false;};delete(key){return;}}// Input keys (use only ‘a’ through ‘z’ and lower case)let keys = [«the», «a», «there», «answer», «any»,«by», «bye», «their»,»abc»];let t = new Trie();console.log(«Keys to insert: «);console.log(keys);//Construct Triefor (let i=0; i<keys.length; i++){t.insert(keys[i]);}
В приведенном выше коде создается класс Trie. Корневой узел) инициализируется в конструкторе. Затем мы перебираем символы в ключе и получаем индекс для каждого символа, используя getIndex( ).
Затем в insert()методе мы сначала пишем проверку, чтобы убедиться, что пустые ключи не разрешены и все ключи хранятся в нижнем регистре. Затем мы сохраняем индекс символа, перебирая дерево с заданным индексом символа.
Если индекс указывает на ноль, мы создаем TrieNode для перехода на уровень ниже. Наконец, мы помечаем последний узел как листовой, поскольку слово закончилось.
Для ключа из n символов наихудшая временная сложность оказывается равной На)О ( п ) так как нам нужно сделать пп итераций.
В поисках дерева
Чтобы выполнить поиск в дереве, вам нужно обратить внимание на три возможных случая:
- Если слово не существует, вы найдете ноль до того, как будет исчерпан последний символ.
- Если слово является подстрокой другого слова, оно не будет найдено, потому что его isEndWordзначение последнего символа в дереве установлено равным false.
- Если слово существует как путь от корневого узла к последнему узлу и / или узлу, отмеченному как конец, то это успешный случай поиска.
search(key){if (key == null){return false; //null key}key = key.toLowerCase();let currentNode = this.root;let index = 0;//Iterate the Trie with given character index,//If it is null at any point then we stop and return false//We will return true only if we reach leafNode and have traversed the//Trie based on the length of the keyfor (var level=0; level<key.length; level++){index = this.getIndex(key[level]);if (currentNode.children[index] == null){return false;}currentNode = currentNode.children[index];}if (currentNode != null && currentNode.isEndWord){return true;}return false;};
Удаление в Trie
Узлы без дочерних веток легко удаляются. Листовой узел существует первым, пока не будет удалено все слово. Для префиксов установлено isEndWordзначение false.
У слов с общими префиксами будет удален последний узел вместе со всеми родительскими узлами в ветви, которые не имеют других дочерних элементов и не являются конечными символами.
Чтобы удалить узел в дереве, мы сначала пишем вспомогательную функцию, чтобы проверить, есть ли у currentNodeнего дочерние элементы.
Затем мы пишем рекурсивную функцию, которая принимает ключ, длину ключа, узел дерева и уровень (индекс) ключа в качестве аргумента. Эта функция удаляет любой заданный ключ.
//Helper FunctionhasNoChildren(currentNode){for (let i=0; i<currentNode.children.length; i++){if (currentNode.children[i] != null)return false;}return true;}//Recursive functiondeleteHelper(key, currentNode, length, level){let deletedSelf = false;if (currentNode == null){console.log(«Key does not exist»);return deletedSelf;}//Base Case: If we have reached the node which points to the alphabet at the end of the key.if (level == length){//If there are no nodes ahead of this node in this path//Then we can delete this nodeif (this.hasNoChildren(currentNode)){currentNode = null;deletedSelf = true;}//If there are nodes ahead of currentNode in this path//Then we cannot delete currentNode. We simply unmark this as leafelse{currentNode.unMarkAsLeaf();deletedSelf = false;}}else{let childNode = currentNode.children[this.getIndex(key[level])];let childDeleted = this.deleteHelper(key, childNode, length, level + 1);if (childDeleted){//Making children pointer also None: since child is deletedcurrentNode.children[this.getIndex(key[level])] = null;//If currentNode is leaf node that means currentNode is part of another key//and hence we can not delete this node and it’s parent path nodesif (currentNode.isEndWord)deletedSelf = false;//If childNode is deleted but if currentNode has more children then currentNode must be part of another key//So, we cannot delete currentNodeelse if(this.hasNoChildren(currentNode) == false)deletedSelf = false;//Else we can delete currentNodeelse{currentNode = null;deletedSelf = true;}}elsedeletedSelf = false;}return deletedSelf}//Function to delete given key from Triedelete(key){if (this.root == null || key == null){console.log(«None key or empty trie error»);return;}this.deleteHelper(key, this.root, key.length, 0);}}
Самобалансирующиеся двоичные деревья поиска
Самобалансирующиеся двоичные деревья поиска — это дерево со сбалансированной высотой, которое автоматически пытается сохранить минимальную высоту при выполнении основных операций.
Сбалансированное дерево — это такое дерево, в котором для каждого узла высота его правого и левого поддеревьев отличается не более чем на 1.
Временная сложность всех трех основных операций — вставки, удаления и поиска занимает Ой)O ( ч ) время, где часчас — это высота дерева двоичного поиска.
Общие примеры самобалансирующегося BST включают красно-черные деревья, AVL, Splay Tree и treaps. Эти BST выполняют вращение влево или вправо после выполнения операций вставки и удаления, сохраняя при этом свое свойство BTS.
Применение самобалансирующейся BTS
- Самобалансирующиеся деревья используются для поддержки упорядоченных списков, таких как очередь приоритетов.
- Они используются для ассоциативных массивов, где пары ключ-значение вставляются в порядке, основанном на ключах.
- Их можно легко расширить для выполнения новых операций, которые можно использовать для оптимизации запросов к базе данных или других алгоритмов обработки списков.
Сегментные деревья
Дерево сегментов — это древовидная структура данных, используемая для хранения интервалов или сегментов. Он используется в случаях, когда есть несколько запросов диапазона в массиве и модификации элементов одного и того же массива.
Он следует принципу статической структуры, согласно которому структуру нельзя изменить после ее создания. Это означает, что мы можем обновлять значения узлов, но не можем изменять их структуру.
Перед построением дерева сегментов нам необходимо решить следующее:
- Значение хранится в каждом узле дерева и,
- Операция слияния, которая образует внутренний родительский узел.
Обычный случай — найти сумму всех элементов в массиве от индексов L до R.
Здесь, на каждом узле (кроме конечных узлов), сохраняется сумма его дочерних узлов.
Сегментное дерево может быть построено с использованием рекурсии (т. Е. Снизу вверх). Каждый лист представляет собой отдельный элемент, и на каждом шаге данные из двух листьев используются для формирования внутреннего родительского узла.
Этот родительский узел может быть объединен с другим листовым или родительским узлом в зависимости от того, на каком уровне он находится, пока не дойдет до корневого узла.
Используемая операция слияния зависит от решаемого вопроса. Итак, рекурсия завершится в корневом узле, который будет представлять весь массив.
На изображении ниже показан запрос суммы для массива:
let x = [2, 6, −3, 8, −5];
Заштрихованные прямоугольники представляют конечные узлы, а прозрачные прямоугольники представляют внутренние родительские узлы.
Деревья сегментов — это гибкая структура данных. Он может быть использован при решении таких проблем, как найти сумму элементов на некоторых сегментах в массиве или нахождения минимального запроса всех элементов массива с индексами, lчтобы rвO (logN)O ( l o g N ) время.
Деревья двоичных индексов
Бинарное индексированное дерево (также известное как дерево Фенвика) — это структура данных, которая может эффективно обновлять элементы и эффективно вычислять суммы префиксов в таблице чисел.
Он обеспечивает способ представления массива чисел в виде массива или дерева. Временная сложность для каждой операции над деревьями двоичных индексов равнаO (logN)O ( l o g N ). Дерево приметп-1п — 1 узлы.
Каждый узел двоичного дерева содержит индекс и значение. Значение — это сумма префикса.
По сравнению с сегментированными деревьями, деревья с двоичным индексом более компактны и относительно проще в реализации, особенно во время соревнований по программированию.
Применение бинарных индексных деревьев
- Двоичные индексированные деревья используются для реализации алгоритма арифметического кодирования.
- Их можно использовать для подсчета инверсий в массиве в O (NlogN)O ( N l o g N ) время.
