Префиксное дерево

…также известное, как: нагруженное дерево, и trie

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

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

const tail = byte(0)

type Leaf struct {
    char    byte
    leaves []Leaf
}

func (l Leaf) IsTail() bool {
    return getLeaf(tail, l.leaves) != nil
}

func (l Leaf) Validate(data []byte) (isValid bool) {
    if len(data) == 0 {
        return l.IsTail()
    }

    leaf := getLeaf(data[0], l.leaves)

    if leaf == nil {
        return false
    }

    return leaf.Validate(data[1:])
}

func getLeaf(char byte, leaves []Leaf) *Leaf {
    for _, leaf := range leaves {
        if leaf.char == char {
            return &leaf
        }
    }
    return nil
}

Данным кодом мы реализовали рекурсивный проход по префиксному древу. Как мы можем видеть, в методе IsTail() мы возвращаем логическое значение, является ли текущий узел хвостовым посредством поиска “магической” константы в списке своих узлов. Метод Validate() же возвращает логическое значение, совпадает ли поданная строка посимвольно с деревом. В случае, если поданная строка закончилось, однако дерево подразумевает продолжение (т.е. последняя ветка не является хвостовой), то такая строка тоже отсекается как невалидная.

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

Важно упомянуть, что по скорости данное решение будет не то, чтобы медленнее, а даже местами быстрее хэшмапы и сбалансированного дерева на получение по ключу. По памяти - тоже выигрыш, однако при условии, что наше дерево будет “сжато” - то есть, промежуточные узлы, ведущие к единственному не-промежуточному узлу. Например, дерево с узлами a->b->c->d|e можно сжать до вида abc->d|e, другими словами, объеденив несколько промежуточных узлов в один