Тёмный

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

selfedu
Подписаться 161 тыс.
Просмотров 9 тыс.
50% 1

Опубликовано:

 

30 окт 2024

Поделиться:

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист
Посмотреть позже
Комментарии : 20   
@ГвоздКрост
@ГвоздКрост Год назад
За доту и доку респект
@DimaBulavenko
@DimaBulavenko Год назад
Зашёл в комменты только ради этого)
@DaymerJun
@DaymerJun Год назад
Спасибо большое, смотрю видеоуроки на перёд по своему предмету в ВУЗе. Очень доходчиво объясняете материал. Жаль, что видео такое короткое, я бы ещё послушал.)
@siarheiulas6969
@siarheiulas6969 Год назад
Отличное видео! Спасибо Вам за эти занятия!
@mslq
@mslq Год назад
Я в шоке от количества дельных роликов на этом канале Сергея.
@7IdE
@7IdE Год назад
Где-то я уже видел этот видос. :D Но меня мучает вопрос: почему О(|key|)? Если я правильно понял, то |key| - это модуль ключа, т.е. длина(видимо, по аналогии с векторами). То есть, это тот же О(n), где n - длина ключа? Если это так, то у меня вопрос: а почему это тут такая сложность? Ведь нигде нет ограничений на то, каким должно быть дерево и сколько у каждого узла может быть детей. Это значит, что у нас может быть дерево, где будет корень с M детей(все 1-буквенные). И предположим, что у дерева будет строго 1 уровень в глубину. Но ведь в таком случае получится, что для для нахождения ключа нам придется перебрать М вариантов в худшем случае. И тогда сложно будет не О(|key|), а О(М). И, кажись, это будет справедливо для каждого уровня: на каждый символ в ключе нам придется перебирать все ключи на текущем уровне дерева. Разве нет?
@selfedu_rus
@selfedu_rus Год назад
Все верно расписали! Взял из теории по префиксному дереву. Вероятно, там полагают длину ключа переменной, а множества проверок - некоторой постоянной опреацией, в итоге она выносится на O большое и остается только длина ключа. Но этом мои догадки. Главное, конечно, понимать как происходит поиск в деталях.
@7IdE
@7IdE Год назад
​@@selfedu_rus, кстати, да, это хорошее замечание про константу. Там реально все будет сводиться О(n), т.к. мы предполагаем, что дерево уже сформировано и не будет меняться от ключа к ключу. Об этом я как-то не задумался. Но, в любом случае, такая структура данных, на первый взгляд, может оказаться крайне неэффективной - как раз-таки из-за этих констант.
@selfedu_rus
@selfedu_rus Год назад
@@7IdE часто она применяется для слов, и максимум число потомков - размер алфавита языка, т.е. не очень много, ну и выбрать всех потомков по префиксам - это тоже классная фишка этого дерева )
@7IdE
@7IdE Год назад
​@@selfedu_rus, хммммм. И в условном английский словаре в худшем случае будет О(26 * |key|). Коэф, конечно, коэф большой, но не настолько, чтобы это все медленно работало. В целом, спасибо за ответы.
@alexanderkrutko644
@alexanderkrutko644 Год назад
@@7IdE 26 в данном случае - это константа, следовательно её не учитываем, остается key
@DduuhbCdhhdjdysdY9lEn4cbseg
@DduuhbCdhhdjdysdY9lEn4cbseg 2 месяца назад
9:34 Не получилось понять этот момент. Как тогда быть, ключа do в этом дереве уже не может существовать, потому что имеющаяся "o" - false? Или нам нужно добавить еще одну "o" рядом и сделать ее is_key true?
@Coliante
@Coliante Год назад
Сергей, добрый день! А вы не планируете создать курс по Java на степик? очень нравится ваша подача, хочу изучить новый язык
@selfedu_rus
@selfedu_rus Год назад
Спасибо! Пока не знаю
@ПавелГолубев-п8о
То есть нам нужно ещё хранить структуру для хранение веток дерева Так как я понял здесь нет только левого и правого потомка К тому же могут быть ключи с похожи значениями 'ror', 'or' и их уже запишем в разных ветвях. В чём же преимущество?
@selfedu_rus
@selfedu_rus Год назад
Да, все верно, нужно в каждом узле хранить ссылки на всех потомков. Особенность дерева - быстрый выбор всех потомков по некоторому префиксу.
@Горныйаниматор
Здравствуйте я бы хотел попросить вас сделать курс по q обучению
@mrin0
@mrin0 Год назад
What's PL?
@Максим-т5ш8и
@Максим-т5ш8и Год назад
Вроде все понятно)
@mrin0
@mrin0 Год назад
!
Далее
B-дерево
24:36
Просмотров 67 тыс.
Avaz Oxun - E'lon, erga tegaman!!!
11:47
Просмотров 254 тыс.
6 важных структур данных
17:25
Просмотров 92 тыс.