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)Informacje o publikacji Donalda R. Morrisona w archiwum ACM ..
Zobacz też drzewo sufiksowe drzewo trie
Przypisy
Kategoria:Drzewa (informatyka)