#24. Префиксное (нагруженное, Trie) дерево. Ассоциативные массивы | Структуры данных

Обучающий курс: stepik.org/a/134212
Инфо-сайт: proproprogs.ru/structure_data
Узнаете о способе представления данных в виде префиксного дерева. Операции добавления пар ключ-значение в префиксное дерево, поиска по ключу и удаление ключей.

[@user-gt8yq9qh5r]

За доту и доку респект

[@user-yg4no8qb3z]

Зашёл в комменты только ради этого)

[@DaymerJun]

Спасибо большое, смотрю видеоуроки на перёд по своему предмету в ВУЗе. Очень доходчиво объясняете материал. Жаль, что видео такое короткое, я бы ещё послушал.)

[@mslq]

Я в шоке от количества дельных роликов на этом канале Сергея.

[@siarheiulas6969]

Отличное видео! Спасибо Вам за эти занятия!

[@Coliante]

Сергей, добрый день! А вы не планируете создать курс по Java на степик? очень нравится ваша подача, хочу изучить новый язык

[@selfedu_rus]

Спасибо! Пока не знаю

[@user-tc9tt2be4j]

Здравствуйте я бы хотел попросить вас сделать курс по q обучению

[@7IdE]

Где-то я уже видел этот видос. :D Но меня мучает вопрос: почему О(|key|)? Если я правильно понял, то |key| - это модуль ключа, т.е. длина(видимо, по аналогии с векторами). То есть, это тот же О(n), где n - длина ключа? Если это так, то у меня вопрос: а почему это тут такая сложность? Ведь нигде нет ограничений на то, каким должно быть дерево и сколько у каждого узла может быть детей. Это значит, что у нас может быть дерево, где будет корень с M детей(все 1-буквенные). И предположим, что у дерева будет строго 1 уровень в глубину. Но ведь в таком случае получится, что для для нахождения ключа нам придется перебрать М вариантов в худшем случае. И тогда сложно будет не О(|key|), а О(М). И, кажись, это будет справедливо для каждого уровня: на каждый символ в ключе нам придется перебирать все ключи на текущем уровне дерева. Разве нет?

[@selfedu_rus]

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

[@7IdE]

​@@selfedu_rus, кстати, да, это хорошее замечание про константу. Там реально все будет сводиться О(n), т.к. мы предполагаем, что дерево уже сформировано и не будет меняться от ключа к ключу. Об этом я как-то не задумался. Но, в любом случае, такая структура данных, на первый взгляд, может оказаться крайне неэффективной - как раз-таки из-за этих констант.

[@selfedu_rus]

@@7IdE часто она применяется для слов, и максимум число потомков - размер алфавита языка, т.е. не очень много, ну и выбрать всех потомков по префиксам - это тоже классная фишка этого дерева )

[@7IdE]

​@@selfedu_rus, хммммм. И в условном английский словаре в худшем случае будет О(26 * |key|). Коэф, конечно, коэф большой, но не настолько, чтобы это все медленно работало. В целом, спасибо за ответы.

[@alexanderkrutko644]

@@7IdE 26 в данном случае - это константа, следовательно её не учитываем, остается key

[@user-yk2zc8vy6u]

То есть нам нужно ещё хранить структуру для хранение веток дерева Так как я понял здесь нет только левого и правого потомка К тому же могут быть ключи с похожи значениями 'ror', 'or' и их уже запишем в разных ветвях. В чём же преимущество?

[@selfedu_rus]

Да, все верно, нужно в каждом узле хранить ссылки на всех потомков. Особенность дерева - быстрый выбор всех потомков по некоторому префиксу.

[@mrin0]

What's PL?

[@user-qn6pq1dk5h]

Вроде все понятно)

[@mrin0]

!