On Thu, 30 Apr 2009 19:06:43 +0200 Sulsa <s...@d...me> wrote:

> On Wed, 29 Apr 2009 21:38:24 +0200
> Wojciech Muła <w...@p...null.onet.pl.invalid> wrote:
>
> > Jak masz zaimplementowany ten słownik? Wg mnie tylko drzewo trie
> > jest sensowne w LZW.
>
> Slownik to std::map z c++.

Czyli najpewniej drzewo czerwono-czarne. Czas rzędu O(k lg n), gdzie
k długość prefiksu, n liczba elementów w mapie.

> Z tego co wiem jest on zaimplementowany na
> drzewie binarnym. co to za drzewo trie? Mozesz pokazac jakiegos linka?

Na wikipedii na ten przykład jest opis. Czas rzędu O(k); trywialna
implementacja takiego drzewo, szczególnie że potrzebujesz jedynie
dwóch operacji: INSERT, SEARCH.

w.

--
Kupię: http://wm.ite.pl/kupie.html