Skompresowane drzewo trie
Skompresowane drzewo trie (również: drzewo Patricia, drzewo pozycyjne) – struktura danych przechowująca zbiór ciągów.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/ae/Patricia_trie.svg/320px-Patricia_trie.svg.png)
Koncepcja
Skompresowane drzewo trie jest wariantem 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ć łańcuchy znaków, ciągi bitów stanowiące zapis liczb naturalnych lub adresów IP lub też ciągi dowolnych elementów z porządkiem leksykograficznym.
Operacje
Poniższe operacje na skompresowanym drzewie trie przechowującym zbiór słów są wykonywane w czasie
- 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 sufiksowi słowa, albo – jeżeli istnieje krawędź, która ma wspólny z tym sufiksem 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ść. 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 tablic asocjacyjnych z ciągami jako kluczami. Szczególne znaczenie mają w dziedzinie trasowania IP. Szczególne drzewa Patricia, drzewa sufiksowe, są stosowane w algorytmach 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)[1].
Zobacz też
- drzewo sufiksowe
- drzewo trie
Przypisy
- ↑ Informacje o publikacji Donalda R. Morrisona w archiwum ACM [1].