Имплементировать префиксное дерево (Trie)

Средняя
medium , tree , hash table
20 November 2023

Описание задачи #

Необходимо имплементировать интерфейс префиксного дерева:

О том, что такое префиксное дерево можно прочитать в статье на википедии.

Ограничения #

Пример #

tree := Constructor()

tree.Insert("apple")
tree.Search("apple")   // return True
tree.Search("app")     // return False
tree.StartsWith("app") // return True
tree.Insert("app")
tree.Search("app")     // return True

Решение #

Для решения данной задачи нужно знать что такое префиксное дерево и как работать с рекурсией (для реализации вставки значений и обхода по дереву).

Нода дерева в данном случае будет выглядеть следующим образом:

type Trie struct {
	children   map[rune]*Trie
	isFullWord bool
}

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

Свойство isFullWord - флаг, который показывает, является ли текущая нода конечной для слова.

children — хеш-мапа со связями между текущей и дочерними нодами дерева. В качестве ключа используется буква латинского алфавита (значение дочерней ноды).

Тогда, если мы разложим слова acid, ai, aid, aide, aim и air в нашу структуру, в итоге мы получим следующее.

Trie{
    children: map[rune]*Trie{
        'a': {
            children: map[rune]*Trie{
                'c': {
                    children: map[rune]*Trie{
                        'i': {
                            children: map[rune]*Trie{
                                'd': {
                                    isFullWord: true,
                                },
                            },
                        },
                    },
                },
                'i': {
                    children: map[rune]*Trie{
                        'd': {
                            children: map[rune]*Trie{
                                'e': {
                                    isFullWord: true,
                                },
                            },
                            isFullWord: true,
                        },
                        'm': {
                            isFullWord: true,
                        },
                        'r': {
                            isFullWord: true,
                        },
                    },
                    isFullWord: true,
                },
            },
        },
    },
}

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

func (t *Trie) insert(word []rune) {
	if len(word) == 0 {
		t.isFullWord = true
		return
	}

	child, exist := t.children[word[0]]
	if !exist {
		child = &Trie{
			children: make(map[rune]*Trie),
		}

		t.children[word[0]] = child
	}

	child.insert(word[1:])
}

Функции Search и StartsWith отличаются между собой только тем, что в Search у последней ноды префикса флаг isFullWord должен быть true. Поэтому, для реализации обеих функций мы можем воспользоваться простой вспомогательной рекурсивной функцией обхода дерева.

Итоговое решение.

  • package main

type Trie struct {
	children   map[rune]*Trie
	isFullWord bool
}

func Constructor() Trie {
	return Trie{
		children: make(map[rune]*Trie),
	}
}

func (t *Trie) Insert(word string) {
	t.insert([]rune(word))
}

func (t *Trie) Search(word string) bool {
	node, exist := t.traverse([]rune(word))
	if !exist {
		return false
	}

	return node.isFullWord
}

func (t *Trie) StartsWith(prefix string) bool {
	_, exist := t.traverse([]rune(prefix))

	return exist
}

func (t *Trie) insert(word []rune) {
	if len(word) == 0 {
		t.isFullWord = true
		return
	}

	child, exist := t.children[word[0]]
	if !exist {
		child = &Trie{
			children: make(map[rune]*Trie),
		}

		t.children[word[0]] = child
	}

	child.insert(word[1:])
}

func (t *Trie) traverse(prefix []rune) (*Trie, bool) {
	if len(prefix) == 0 {
		return t, true
	}

	child, exist := t.children[prefix[0]]
	if !exist {
		return nil, false
	}

	return child.traverse(prefix[1:])
}

  • export class Trie {
    children: Map<string, Trie>
    isFullWord: boolean

    constructor(children?: Map<string, Trie>, isFullWord?: boolean) {
        this.children = children ?? new Map()
        this.isFullWord = isFullWord ?? false
    }

    insert(word: string): void {
        debugger
        if (word.length === 0) {
            this.isFullWord = true
            return
        }

        let child = this.children.get(word[0])

        if (!child) {
            child = new Trie()
            this.children.set(word[0], child)
        }

        child.insert(word.slice(1))
    }

    search(word: string): boolean {
        const node = this.traverse(word)
        if (!node) {
            return false
        }

        return node.isFullWord
    }

    startsWith(prefix: string): boolean {
        const node = this.traverse(prefix)

        return node !== null
    }

    private traverse(prefix: string): Trie | null {
        if (prefix.length === 0) {
            return this
        }

        const child = this.children.get(prefix[0])

        if (!child) {
            return null
        }

        return child.traverse(prefix.slice(1))
    }
}

Оценка сложности #

Так как задача - имплементировать структуру данных, мы будем оценивать сложность методов Insert, Search и StartsWith.

По времени

Функции Insert, Search и StartsWith используют рекурсивные вспомогательные функции insert и traverse. У обеих функций глубина рекурсии равна длине префикса.

Таким образом все 3 функции имеют сложность O(n), где n - длина префикса.

По памяти

Для работы функций не используются промежуточные структуры, зависящие от длины префикса. Сложность по памяти O(1).

Оригинал задачи на Leetcode
< Предыдущая задача
Следующая задача >