Przechowywanie string'ów w drzewie binarnym

Witam

Przechowuję kilka tysięcy string'ów do których co chwilę są dodawane nowe, ale każdy musi być unikalny, dlatego przed każdym dodaniem zbiór musi zostać przeszukany pod kątem istnienia takiego samego napisu. Napisy mniej więcej mają długość kilka do około 30 znaków. Zależy mi na bardzo szybkim działaniu.

Nigdy nie miałem takiego problemu, ale domyślam się, że najlepszym rozwiązaniem będzie użycie drzewa binarnego. Jednak nie daje mi to spokoju, że zeżre to o wiele za dużo pamięci.

Skoro bajt może mieć wartość 0 - 255, to w każdym węzłu drzewa będzie trzeba przechować 256 wskaźników (pustych lub nie).

Jeżeli pierwsza część napisu nie będzie taka sama, to praktycznie przy każdym znaku trzeba będzie tworzyć nowy liść z węzłami zajmującymi 1 kb pamięci (256 * 4), więc zamiast tych kilkunastu bajtów każdy napis będzie zajmował 1 kb + kilkanaście b.

Może się myle.

Pozdrawiam.

Drzewo binarne zawsze ma dwoje potomków - stąd właśnie nazwa. Mówisz o drzewach k-narnych.
a) nie musisz zakładać, że każda wartość z przedziału 0-255 jest prawidłowa (no chyba, że musisz?).
b) Możesz użyć drzewa binarnego

Jakie operacje chcesz wykonywać na tym zbiorze?

IMHO drzewo binarne do tego celu jest złym wyborem. Do problemu słownikowego (bo na taki twój problem wygląda) najlepsza jest hash-table.

Spróbuj ze strukturą:

set<string> zbior;

Jeśli coś nie będzie działać, próbuj dalej (map, multimap, unordered_set, boost::bimap).