Tekst źródłowy strony Skompresowane drzewo trie

'''Skompresowane drzewo trie''' (również: '''drzewo Patricia''', '''drzewo pozycyjne''') – [[struktura danych]] przechowująca [[zbiór]] [[ciąg (matematyka)|ciągów]].

[[Plik:Patricia trie.svg|frame|Przykładowe skompresowane drzewo trie]]

== Koncepcja ==
Skompresowane drzewo trie jest wariantem [[drzewo trie|drzewa trie]], w którym krawędzie mogą być etykietowane ciągami znaków, a nie tylko pojedynczymi znakami. Kompresja drzewa trie polega na „ściągnięciu” nierozgałęzionych ścieżek i oznaczeniu nowych krawędzi słowami złożonymi z liter na pierwotnych krawędziach. W rezultacie każdy węzeł wewnętrzny ma co najmniej dwóch synów.

Skompresowane drzewo trie może przechowywać [[Tekstowy typ danych|łańcuchy znaków]], ciągi bitów stanowiące zapis [[Liczby naturalne|liczb naturalnych]] lub [[adres IP|adresów IP]] lub też ciągi dowolnych elementów z [[porządek leksykograficzny|porządkiem leksykograficznym]].

== Operacje ==
Poniższe operacje na skompresowanym drzewie trie przechowującym zbiór [[język formalny|słów]] <math>S</math> są wykonywane w [[złożoność obliczeniowa|czasie]] <math>\mathcal{O}\left(\max\limits_{s_i \in S} |s_i|\right){:}</math>

* wyszukiwanie – informuje czy dane słowo należy do zbioru. Realizowane jak w drzewie trie, ale przejście niektórych krawędzi może oznaczać dopasowanie wielu znaków.
* wstawienie słowa – przeszukujemy drzewo, dopóki nie możemy zejść niżej. W tym momencie albo tworzymy nową krawędź z etykietą równą pozostałemu [[podsłowo|sufiksowi]] słowa, albo – jeżeli istnieje krawędź, która ma wspólny z tym sufiksem [[podsłowo|prefiks]], rozbijamy tę krawędź na dwie krawędzie (z których pierwsza jest etykietowana tym wspólnym prefiksem, a druga pozostałą częścią pierwotnej etykiety), a następnie do nowego wierzchołka dołączamy krawędź z pozostałą częścią wstawianego słowa.
* usuwanie słowa – usuwamy odpowiedni [[liść (informatyka)|liść]]. Jeżeli jego ojciec ma tylko jednego syna, wycinamy go, łącząc etykiety sąsiadujących z nim krawędzi.
* znajdowanie poprzednika i następnika danego słowa w porządku leksykograficznym.

== Zastosowania ==
Skompresowane drzewa trie znajdują zastosowanie w konstrukcji [[tablica asocjacyjna|tablic asocjacyjnych]] z ciągami jako kluczami. Szczególne znaczenie mają w dziedzinie [[Trasowanie (telekomunikacja)|trasowania]] [[Protokół internetowy|IP]]. Szczególne drzewa Patricia, [[drzewo sufiksowe|drzewa sufiksowe]], są stosowane w [[algorytm]]ach tekstowych.

== Historia ==
Drzewa Patricia po raz pierwszy wprowadził Donald R. Morrison w [[1968]]. Nazwa drzewa pochodzi od skrótu ''PATRICIA: Practical Algorithm To Retrieve Information Coded in Alphanumeric'' (''Praktyczny algorytm wyszukiwania informacji zakodowanych w formie alfanumerycznej'')<ref>Informacje o publikacji Donalda R. Morrisona w archiwum ACM [http://portal.acm.org/citation.cfm?id=321481].</ref>.

== Zobacz też ==
* [[drzewo sufiksowe]]
* [[drzewo trie]]

== Przypisy ==
{{Przypisy}}

[[Kategoria:Drzewa (informatyka)]]