|
| 1 | +# Префиксное дерево |
| 2 | + |
| 3 | +**Префиксное дерево** (также бор, луч, нагруженное или суффиксное дерево) в информатике - упорядоченная древовидная |
| 4 | +структура данных, которая используется для хранения динамических множеств или ассоциативных массивов, где |
| 5 | +ключём обычно выступают строки. Дерево называется префиксным, потому что поиск осуществляется по префиксам. |
| 6 | + |
| 7 | +В отличие от бинарного дерева, узлы не содержать ключи, соответствующие узлу. Представляет собой корневое дерево, каждое |
| 8 | +ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с его сыновьями, |
| 9 | +помечены разными символами. Некоторые узлы префиксного дерева выделены (на рисунке они подписаны цифрами) и считается, |
| 10 | +что префиксное дерево содержит данную строку-ключ тогда и только тогда, когда эту строку можно прочитать на пути из |
| 11 | +корня до некоторого выделенного узла. |
| 12 | + |
| 13 | +Таким образом, в отличие от бинарных деревьев поиска, ключ, идентифицирующий конкретный узел дерева, не явно хранится в |
| 14 | +данном узле, а неявно задаётся положением данного узла в дереве. Получить ключ можно выписыванием подряд символов, |
| 15 | +помечающих рёбра на пути от корня до узла. Ключ корня дерева — пустая строка. Часто в выделенных узлах хранят |
| 16 | +дополнительную информацию, связанную с ключом, и обычно выделенными являются только листья и, возможно, некоторые |
| 17 | +внутренние узлы. |
| 18 | + |
| 19 | + |
| 20 | + |
| 21 | +На рисунке представлено префиксное дерево, содержащее ключи «A», «to», «tea», «ted», «ten», «i», «in», «inn». |
| 22 | + |
| 23 | +## Ссылки |
| 24 | + |
| 25 | +- [Wikipedia](https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE) |
| 26 | +- [YouTube](https://www.youtube.com/watch?v=zIjfhVPRZCg&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&index=7&t=0s) |
0 commit comments