Merkle-Patricia Trees. Часть 3

Что такое Trie?

Говоря простым языком, Trie - это особый тип дерева, используемый для хранения строк. То, что делает Trie интересным, так это то, как они организуют и хранят строки, позволяя быстро искать, вставлять и удалять их.

Как работает Trie?

Представьте, что у нас есть пустой Trie. Корень Trie не содержит никаких букв, но служит отправной точкой для хранения наших строк.

Начнем с первой строки «an».

1. Из корневого узла мы проверим, есть ли ветвь для первой буквы «a». В данном случае ее нет, поэтому мы создаем новый узел для «a».

2. Затем мы проверяем, есть ли ветвь для второй буквы «n», исходящая из узла «a». Поскольку ее нет, мы создаем еще один узел для «n».

Теперь наш Trie представляет слово «an».

Для того, чтобы добавить второе слово «ant», мы снова начинаем с корня:

1. Проверяем, есть ли ветвь для «a». На этот раз она уже существует, поэтому мы идем по ней.

2. Затем мы ищем ветвь для «n» от «a». Она также существует, поэтому мы идем по ней.

3. Наконец, мы ищем ответвление для «t» от «n». Ее не существует, поэтому мы добавляем новый узел для «t».

Теперь наша тройка содержит «an» и «ant».

1. Начиная с «dad», мы не находим ветви для «d» в корне, поэтому добавляем ее.

2. Мы не находим ветви для «a» от «d», поэтому добавляем ее.

3. Мы не находим ветви для «d» из «a», поэтому добавляем ее.

4. Для «do» у нас уже есть «d» в корне, поэтому мы следуем ему.

5. У нас нет ветви «o» от «d», поэтому мы добавляем ее.

Теперь наша тройка содержит «an», «ant», «dad» и «do».

Вот так мы создаем Trie! Если мы хотим проверить, входит ли слово в тройку, мы начинаем с корня и идем по ветвям, соответствующим буквам слова. Если мы можем сделать это, не заходя в тупик, значит, наше слово находится в Trie.

Таким образом, мы можем сделать вывод, что Trie хранит слова, разделяя между ними общие буквы. Эта общая структура позволяет эффективно хранить слова и быстро находить их.

Это базовое объяснение Trie. Продвинутые темы включают добавление маркера в конец каждого слова в Trie, чтобы различать, например, «an» и «ant» как отдельные слова.

#merkle #patricia