Префиксное дерево
Префиксное дерево (или бор, или луч, или нагруженное дерево) (trie) - структура данных, позволяющая хранить ассоциативный массив (или другое динамическое множество), ключами которого чаще всего являются строки. Представляет собой корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все ребра, соединяющие этот узел с его потомками, помечены разными символами. Некоторые узлы префиксного дерева выделены и считается, что префиксное дерево содержит данную строку-ключ тогда и только тогда, когда эту строку можно прочитать на пути из корня до некоторого (единственного для этой строки) выделенного узла.
Таким образом, в отличие от бинарных деревьев поиска (binary search tree), ключ, идентифицирующий конкретный узел дерева, не явно хранится в данном узле, а задается положением данного узла в дереве. Получить ключ можно выписыванием символов, помечающих ребра на пути от корня до узла. Ключ корневого узла - пустая строка. Часто в выделенных узлах хранят дополнительную информацию, связанную с ключом, и обычно выделенными являются только листья, а иногда и некоторые внутренние узлы.
Сложность
Временная сложность префиксного дерева составляет O(n) (при использовании хэш-таблицы).
Реализация
Для реализации префиксного дерева мы будем использовать хэш-таблицу (см. раздел 5).
Начнем с узла дерева:
// data-structures/trie/node.js
// Импортируем конструктор хэш-таблицы
import HashTable from '../hash-table'
// Последний (завершающий) символ
export const HEAD_CHARACTER = '*'
// Узел префиксного дерева
export default class Node {
constructor(char, isCompleteWord = false) {
// Символ
this.char = char
// Индикатор завершающего символа
this.isCompleteWord = isCompleteWord
// Хэш-таблица потомков
this.children = new HashTable()
}
}
Методы добавления и удаления узлов-потомков:
// Добавляет потомка в дерево
addChild(char, isCompleteWord = false) {
// Добавляем узел при отсутствии
if (!this.hasChild(char)) {
this.children.set(char, new Node(char, isCompleteWord))
}
// Извлекаем узел
const node = this.getChild(char)
// Обновляем флаг `isCompleteWord` при необходимости,
// например, при добавлении слова "car" после слова "carpet",
// букву "r" нужно пометить как завершающую
node.isCompleteWord = node.isCompleteWord || isCompleteWord
// Возвращаем узел
return node
}
// Удаляет потомка
removeChild(char) {
// Извлекаем узел
const node = this.getChild(char)
// Удаляем узел, только если:
// - у него нет потомков
// - node.isCompleteWord === false
if (node && !node.isCompleteWord && !node.hasChildren()) {
this.children.remove(char)
}
return this
}
Вспомогательные методы для работы с потомками:
// Возвращает потомка
getChild(char) {
return this.children.get(char)
}
// Определяет наличие потомка
hasChild(char) {
return this.children.has(char)
}
// Определяет наличие потомков
hasChildren() {
return this.children.getKeys().length > 0
}
// Автодополнение (предложение следующих символов)
suggestChildren() {
return [...this.children.getKeys()]
}
Метод преобразования потомков в строку:
// Преобразует потомков в строку
// с указанием признака завершающего символа
toString() {
let childrenAsString = this.suggestChildren().toString()
childrenAsString = childrenAsString ? `:${childrenAsString}` : ''
const isCompleteString = this.isCompleteWord ? HEAD_CHARACTER : ''
return `${this.char}${isCompleteString}${childrenAsString}`
}
Полный код узла префиксного дерева
Отлично! Приступаем к реализации самого дерева:
// data-structures/trie/index.js
import TrieNode, { HEAD_CHARACTER } from './node'
// Префиксное дерево
export default class Trie {
constructor() {
// Головной (корневой) узел
this.head = new TrieNode(HEAD_CHARACTER)
}
}
Методы добавления и удаления слова (ключа) в/из дерева:
// Добавляет слово (ключ) в дерево
addWord(word) {
// Преобразуем строку (слово) в массив символов
// (вопрос на засыпку: почему лучше не использовать `split('')`?
// Подсказка: попробуйте преобразовать "Hello, 👋!")
const chars = [...word]
// Текущий узел (начинаем с головного)
let node = this.head
// Перебираем символы и добавляем каждый в дерево
for (let i = 0; i < chars.length; i++) {
// Индикатор завершающего символа
const isComplete = i === chars.length - 1
// Добавляем потомка
node = node.addChild(chars[i], isComplete)
}
return this
}
// Удаляет слово (ключ) из дерева
removeWord(word) {
// Удаляет слово рекурсивно ("сначала в глубину")
const depthFirstRemove = (node, i = 0) => {
// Если удаляемый символ находится за пределами слова,
// ничего не делаем
if (i >= word.length) return
// Символ
const char = word[i]
// Следующий узел
const nextNode = node.getChild(char)
// Если следующий узел отсутствует,
// ничего не делаем
if (!nextNode) return
// Погружаемся глубже
depthFirstRemove(nextNode, i + 1)
// Поскольку мы удаляем слово,
// необходимо обновить флаг `isCompleteWord`
// его последнего символа
if (i === word.length - 1) {
nextNode.isCompleteWord = false
}
// Узел удаляется, только если:
// - у него нет потомков
// - nextNode.isCompleteWord === false
node.removeChild(char)
}
// Начинаем с головного узла
depthFirstRemove(this.head)
return this
}
Метод автодополнения:
// Автодополнение (предложение следующих символов)
suggestNextCharacters(word) {
// Получаем последний символ
const lastChar = this.getLastCharNode(word)
// Если последний символ отсутствует
if (!lastChar) {
return null
}
// Возвращаем массив следующих символов
return lastChar.suggestChildren()
}
Вспомогательный метод определения наличия слова в дереве:
// Определяет наличие слова в дереве
doesWordExist(word) {
// Получаем последний символ
const lastChar = this.getLastCharNode(word)
return Boolean(lastChar) && lastChar.isCompleteWord
}
Наконец, метод получения последнего символа:
// Возвращает последний символ
getLastCharNode(word) {
// Разбиваем слово на символы
const chars = [...word]
// Текущий узел (начинаем с головного)
let node = this.head
// Перебираем символы
for (let i = 0; i < chars.length; i++) {
// Если символ отсутствует
if (!node.hasChild(chars[i])) {
return null
}
// Извлекаем потомка
node = node.getChild(chars[i])
}
// Возвращаем последний узел
return node
}
Полный код префиксного дерева
Тестирование
Проверяем, что наше префиксное дерево работает, как ожидается.
Тесты для узла
Тесты для дерева
Запускаем тесты:
npm run test ./data-structures/trie
