AiSD (index)

AiSD (14) - ADT MAP (trie)

OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie

https://en.wikipedia.org/wiki/Trie

WPROWADZENIE

Drzewo trie (ang. prefix tree) jest to drzewo poszukiwań przechowujące w węzłach fragmenty kluczy (drzewa BST przechowją w węzłach całe klucze). Węzeł przechowujący ostatni fragment klucza przechowuje również wartość związaną z danym kluczem (lub tylko znacznik końca klucza). Wyszukiwanie klucza w drzewie trie zajmuje czas O(m), a w zrównoważonych drzewach BST czas O(m log n), gdzie n to liczba kluczy, a m to największa długość klucza.

Modyfikacją drzew trie są drzewa Patricia (ang. compact prefix tree), w których węzły mające tylko jednego syna są usuwane, a drzewo odpowiednio modyfikowane.

| Wstawione pary (key,value) do drzewa trie:
| ("kot",1),("koc",2),("los",3),("loty",4)
|           *
|        /    \
|       k      l
|      /        \
|     o          o
|    / \        / \
| t(1) c(2)  s(3)  t
|                 /
|               y(4)

| Wstawione pary (key,value) do drzewa Patricia:
| ("kot",1),("koc",2),("los",3),("loty",4),("dach",5)
|           *
|       /      \    \
|     ko        lo   dach(5)
|    / \        / \
| t(1) c(2)  s(3)  ty(4)

WSTAWIANIE

Każdy znak klucza jest wstawiany jako osobny węzeł. Jeżeli wstawiany węzeł k1 jest prefiksem innego klucza k2, to nie tworzy się nowych węzłów, tylko ustawiamy znacznik końca klucza. Jeżeli wstawiany klucz k1 ma wspólny prefiks z kluczem k2, to tworzymy tylko węzły dla znaków następujących po wspólnym prefiksie.

WYSZUKIWANIE

Wyszukujemy kolejne znaki klucza w węzłach przechodząc w dół drzewa. Jeżeli wszystkie węzły istnieją i w węźle z ostatnim znakiem klucza jest ustawiony znacznik końca klucza, to klucz istnieje. W przeciwnym razie klucza nie ma w drzewie.

USUWANIE

Usuwanie klucza można wykonać rekurencyjnie. Możliwe są następujące przypadki.

1. Klucza nie ma w drzewie, a wtedy drzewo nie jest modyfikowane.
2. Klucz nie jest prefiksem innego klucza oraz żadna część klucza nie jest prefiksem innego klucza. Usuwamy wszystkie węzły klucza.
3. Klucz k1 jest prefiksem innego dłuższego klucza k2. Usuwamy znacznik końca klucza k1.
4. Klucz k1 jest obecny w drzewie, ale inny klucz k2 jest prefiksem k1 lub klucze k1 i k2 mają wspólny prefix. Usuwamy węzły z końca klucza k1 aż do momentu, gdy znajdziemy znacznik końca k2 lub dojdziemy do węzła kończącego wspólny prefix k1 i k2 (ten węzeł będzie miał co najmniej jedno dziecko).

PREFIKSY

Ważną cechą drzew trie jest łatwe wyszukiwanie wszystkich kluczy o wspólnym prefiksie. Takie klucze będę zlokalizowane w poddrzewie zaczepionym w węźle kończącym prefiks. Jako szczególny przypadek dostajemy możliwość wypisania wszystkich kluczy zawartych w drzewie (pusty wspólny prefiks).

IMPLEMENTACJA 1

Jeżeli liczba znaków, z których zbudowane są klucze, jest znana i mała, to każdy wezeł może mieć tablicę łączy do kolejnych węzłów dla odpowiednich znaków. Nie trzeba przechowywać samych znaków.

struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE]; // tablica wskaznikow
    bool isEndOfWord;
};

IMPLEMENTACJA 2

Jeżeli liczba znaków, z których zbudowane są klucze, jest duża lub nieznana, to każdy węzeł może mieć tablicę lub listę zmiennej długości z łączami do węzłów, ale musimy przechowywać znak w węźle.

Inny pomysł to zastosowanie reprezentacji na lewo syn, na prawo brat (ang. left-child right-sibling representation).

template <typename T>
struct TrieNode {
    T partial_key;
    struct TrieNode *left_child;
    struct TrieNode *right_sibling;
    bool isEndOfWord;
};

| Wstawione pary (key,value) do drzewa trie:
| ("kot",1),("koc",2),("kil",3),("lot",4),("lis",5)
|         *
|        /
|       k---------------l
|      /               /
|     o---------i     o-----i
|    /         /     /     /
| t(1)--c(2)  l(3)  t(4)  s(5)

ZADANIE 14.1

Przygotować implementację realizującą ADT MAP na bazie drzewa trie. Założyć, że kluczami będą stringi. Można rozwinąć przykładowy program.

ZADANIE 14.2

Przygotować implementację realizującą ADT MAP na bazie drzewa Patricia. Założyć, że kluczami będą stringi.

AiSD (index)