TRIE - algorytm wypisywania zawartosci

Mam pewien problem z projetkem. Oto tresc polecenia:

Zadaniem programu jest zarządzanie zbiorem słów (słownikiem), poprzez realizację podawanych na wejściu poleceń aktualizacji oraz zapytań.
Wejście i wyjście

Wejście rozpoczyna się od liczby całkowitej t (t<106 ), określającej liczbę poleceń otrzymywanych przez program. Każda z kolejnych t linii zawiera jedno z następujących poleceń:

    * add word - polecenie dodania do słownika słowa word ,
    * add [n] suffix - jak wyżej, przy czym podana jest tylko końcówka suffix dodawanego słowa; pierwsze n liter słowa (poprzedzających końcówkę) należy przyjąć takich samych, jak w przypadku poprzednio wykonywanej operacji "add",
    * delete word - polecenie usunięcia ze słownika słowa word ,
    * count word1 word2 - żądanie wypisania jednej linii, zawierającej liczbę słów ze słownika, które w porządku leksykograficznym występują pomiędzy word1 a word2,
    * list word1 word2 - żądanie wypisania w oddzielnych liniach wszystkich słów ze słownika, które w porządku leksykograficznym występują pomiędzy word1 a word2; wyjście powinno być uporządkowane leksykograficznie (jeżeli word1 <= word2) bądź antyleksykograficznie (jeżeli word1 > word2),
    * show n - polecenie wypisania n-tego w porządku leksykograficznym słowa w słowniku. 

Uwagi:

    * Na początku działania programu słownik jest pusty.
    * Słowa należy rozumieć jako łańcuchy znaków o długości między 1 a 107, złożone wyłącznie z czterech możliwych znaków (zgodnie ze zwyczajem przyjmujemy alfabet: {'c', 'g', 't', 'a'}). Porządek leksykograficzny liter jest następujący: 'c' < 'g' < 't' < 'a'.
    * W wymienionych sytuacjach przetwarzane polecenie sterujące nie powinno powodować modyfikacji zawartości słownika: 1) próba dodania słowa już występującego w słowniku, 2) operacja "add [n] suffix" z błędną (zbyt dużą) wartością parametru n, 3) próba usunięcia słowa nie występującego w słowniku.
    * Granice zakresów dla poleceń "count" i "list" należy traktować ,,włącznie".
    * Rozmiary pliku wejściowego oraz poprawnego pliku wyjściowego nie przekraczają 32MB.

Przykład

Wejście:
14
add cta
add [1] tga
add [4] aa
list c a
add [2] aa
add [2] a
count cta ct
delete cta
count c cta
list g ctgaa
delete cta
add c
show 1
count c ctg

Wyjście:
ctga
ctgaaa
cta
3
2
ctaa
ctgaaa
c
1

Struktura mojego wezla zawiera:
klucz - litera
wskanik na rodzica
tablice wskaznikow na synow (max 4 bo sa 4 litery w alfabecie)
zmianna kontrolna koniec - okresla czy dany wezel jest koncem wyrazu

Polecenie add dziala juz poprawanie. Niestety nie mam pojecia jak zrobic polecenie "list"
Od razu zaznaczam ze nie chodzi mi o kod tylko o jakis przystepny algorytm :) O wskazowki zwiazane z implementacja ewentualnie zapytam pozniej :)

To co napisałeś(drzewo prefiksowe) jest całkiem dobre:
add word - O(dlugość słowa)
add [n] suffix - O(n+dlugość słowa)
delete word - O(dlugość słowa)
count word1 word2 - O(liczba słów pomiędzy word1 i word2 * długość najdłuższego słowa)
list word1 word2 - O(liczba słów pomiędzy word1 i word2 * długość najdłuższego słowa)
show n - O(n * długość najdłuższego słowa)

O ile "list word1 word2" nie można zrobić szybciej gdyż takiego rzędu jest wynik, to count i show można znacznie przyspieszyć.

W każdym węźle pamiętaj jeszcze ile wyrazów w drzewie ma taki prefiks(czyli ile wyrazów kończy się "poniżej"+ewentualnie 1 jeżeli dany węzeł też jest końcem wyrazu).

Po tej optymalizacji będziesz miał złożoność
count word1 word2 - O(lg (liczba słów pomiędzy word1 i word2) * długość najdłuższego słowa)
show n - O(lg (n) * długość najdłuższego słowa)

Natomiast "list word1 word2" powinieneś zrobić tak:
-węzły c,g,t,a trzymać zawsze w tej kolejności
-znaleźć pierwsze słowo >= word1
-przechodzić drzewo od tego miejsca wgłąb
-jeżeli już nie możemy iść dalej to cofamy się do ojca i patrzymy u ojca kolejnego syna(czyli naszego brata).
-kończymy, gdy znajdziemy słowo >= word2

Def.
Slowo1 >= Slowo2, wtw gdy:
-slowo2 jest prefiksem(być może niewłaściwym-słowa równe) slowo1
lub
-po usunięciu wspólnego prefiksu słów, pierwsza litera slowo1 >= pierwsza litera slowo2.