Префіксне дерево

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Префіксне дерево (англ. trie, або англ. prefix tree) — структура даних, дерево, в якому шлях від кореня до листа визначає рядок. Рядки з однаковими префіксами мають спільний шлях від кореня довжиною цього префікса[1].

Префіксне дерево дозволяє зберігати асоціативний масив, ключами якого є рядки. На відміну від бінарних дерев, в листі дерева не зберігається ключ. Значення ключа можна набути прогляданням всіх батьківських вузлів, кожний з яких зберігає один або кілька символів алфавіту. Корінь дерева пов'язаний з порожнім рядком. Таким чином, нащадки вузла мають загальний префікс, звідки і відбулася назва даного абстрактного типу даних. Значення, пов'язані з ключем, зазвичай не пов'язані з кожним вузлом, а тільки з листям і, можливо, деякими внутрішніми вузлами.

Примітки[ред.ред. код]

  1. Arnab Bhattacharya (2015). 3.7 Tries. Fundamentals of Database Indexing and Searching. CRC Press. с. 52. ISBN 978-1-4665-8255-2. 

Див. також[ред.ред. код]