Tento úkol spočívá v implementaci jednoduché varianty prefixového stromu (Trie) ve stylu standardní knihovny. Varianta, kterou budete implementovat, reprezentuje každý znak jedním uzlem a má připravené odkazy pro každého možného potomka.

Tato varianta je zbytečně paměťově náročná, ale jednoduchá k implementaci.

V tomto úkolu začneme vytvořením struktury trie, která zastřešuje interní data skládající se z uzlů reprezentovaných trie_node. Jejich popis najdete níže.

// Assume only basic ASCII characters
static const size_t num_chars = 128;
 
struct trie_node {
    trie_node* children[num_chars] = {};
    trie_node* parent = nullptr;
    char payload = 0;
    bool is_terminal = false;
};
 
struct trie {
    trie_node* root = nullptr;
    size_t size = 0;
};

• trie::root je ukazatel na kořenový uzel stromu
• trie::size je počet unikátních slov, které trie obsahuje
• trie_node::children je pole ukazatelů na přímé následovníky daného uzlu
• trie_node::parent je ukazatel na přímého předka daného uzlu
• trie_node::payload je znak, který tento uzel reprezentuje
• trie_node::is_terminal označuje, jestli v tomto uzlu končí slovo

Potřebné hlavičkové soubory a testy ke stažení zde.

Jeden nebo více .cpp souborů, které implementují funkce deklarované v souboru trie.hpp tak, aby testy procházely a neztrácela se paměť. Při práci na úkolu soubor trie.hpp neměňte.

Testy jsou schválně dělané tak, aby bylo možné se ve stromu pohybovat pomocí rekurze. Tedy se vám ani při naivní implementaci nestane, že vám dojde místo na stacku, a doporučujeme tedy při implementaci různých operací přemýšlet rekurzivně.

Stejně tak doporučujeme implementovat plnění všech dat do uzlů. V tomto úkolu se bez toho obejdete, ale ty následující je budou využívat a je snadnější to udělat napoprvé.

Funkce pracující s trií dostávají jako argument std::string const&. Abyste si nemuseli vždy předávat referenci na std::string a index, kde zrovna v průchodu jste, můžete si ze std::string vzít ukazatel na C-style řetězec.

Následující kód projde a vypíše celý řetězec ze std::string bez použití délky. Podobným způsobem se můžete posouvat v řetězci uvnitř trie.

#include <string>
#include <iostream>
 
int main() {
    std::string s = "Hello world";
    const char* sptr = s.c_str();
    while (*sptr) {
        std::cout << *sptr << '\n';
        sptr++;
    }
}

Dávejte si pozor na přístup ke smazané paměti, protože jakmile jednou kus paměti uvolníte, všechna data v ní jsou pro vás ztracena. To znamená, že například při mazání trie je potřeba každému uzlu nejdříve smazat potomky, a až potom uzel samotný.

Pro tento úkol žádné hlavičky ze standardní knihovny nedoporučujeme.