Обучающий курс: stepik.org/a/134212 Инфо-сайт: proproprogs.ru/structure_data Узнаете о способе представления данных в виде префиксного дерева. Операции добавления пар ключ-значение в префиксное дерево, поиска по ключу и удаление ключей.
Спасибо большое, смотрю видеоуроки на перёд по своему предмету в ВУЗе. Очень доходчиво объясняете материал. Жаль, что видео такое короткое, я бы ещё послушал.)
Где-то я уже видел этот видос. :D Но меня мучает вопрос: почему О(|key|)? Если я правильно понял, то |key| - это модуль ключа, т.е. длина(видимо, по аналогии с векторами). То есть, это тот же О(n), где n - длина ключа? Если это так, то у меня вопрос: а почему это тут такая сложность? Ведь нигде нет ограничений на то, каким должно быть дерево и сколько у каждого узла может быть детей. Это значит, что у нас может быть дерево, где будет корень с M детей(все 1-буквенные). И предположим, что у дерева будет строго 1 уровень в глубину. Но ведь в таком случае получится, что для для нахождения ключа нам придется перебрать М вариантов в худшем случае. И тогда сложно будет не О(|key|), а О(М). И, кажись, это будет справедливо для каждого уровня: на каждый символ в ключе нам придется перебирать все ключи на текущем уровне дерева. Разве нет?
Все верно расписали! Взял из теории по префиксному дереву. Вероятно, там полагают длину ключа переменной, а множества проверок - некоторой постоянной опреацией, в итоге она выносится на O большое и остается только длина ключа. Но этом мои догадки. Главное, конечно, понимать как происходит поиск в деталях.
@@selfedu_rus, кстати, да, это хорошее замечание про константу. Там реально все будет сводиться О(n), т.к. мы предполагаем, что дерево уже сформировано и не будет меняться от ключа к ключу. Об этом я как-то не задумался. Но, в любом случае, такая структура данных, на первый взгляд, может оказаться крайне неэффективной - как раз-таки из-за этих констант.
@@7IdE часто она применяется для слов, и максимум число потомков - размер алфавита языка, т.е. не очень много, ну и выбрать всех потомков по префиксам - это тоже классная фишка этого дерева )
@@selfedu_rus, хммммм. И в условном английский словаре в худшем случае будет О(26 * |key|). Коэф, конечно, коэф большой, но не настолько, чтобы это все медленно работало. В целом, спасибо за ответы.
То есть нам нужно ещё хранить структуру для хранение веток дерева Так как я понял здесь нет только левого и правого потомка К тому же могут быть ключи с похожи значениями 'ror', 'or' и их уже запишем в разных ветвях. В чём же преимущество?
