Zmniejszenie złożoności pamięciowej algorytmu

g

o_O błąd widać już patrząc na maina:

int main(){
	unsigned short *n,*m;
	Tree *hasla = new Tree();
	n = new unsigned short;
	std::cin >> *n;
	std::string **tab = new std::string *[*n];
	for (unsigned short i=0; i<*n; i++){
		m = new unsigned short;
		std::cin >> *m;
		std::cin.get();
		tab[i] = new std::string [*m];
		for (unsigned short j=0; j<*m; j++){
			std::cin >> tab[i][j];
			hasla->add(tab[i][j],(i)+1);
		}
		delete [] tab[i];
		delete m;
	}
	delete n;
	delete [] tab;
	hasla->print();
	delete hasla;
	return 0;
}

Bo jakże sprytnie trzymasz w pamięci WSZYSTKIE podane na wejście stringi. I to podwójnie! :D Podczas gdy należało trzymać w pamięci tylko UNIKALNE stringi. Więc jak podam ci na wejście milion linii ze słowe "Konstantynopolitannczykowianeczka" to normalny algorytm trzymałby ten string raz a do tego listę miliona intów.
A ty przechowasz dwa miliony takich stringów plus milion intów.

1. Nie zapisuj tych stringów z wejścia do żadnej listy! Po co?! Czytasz jeden, wrzucasz do drzewa i czytasz następny. Po co ci ta tablica tab?
2. Zanim coś dodasz do drzewa zalecałbym sprawdzić czy może taki node w drzewie już jest bo jeśli jest to masz dodać do listy indeksów kolejny element, a nie dodawać cały nowy węzeł drzewa. Możliwe że tak robisz, ale trudno z tego kodu to wywnioskować. Zresztą tak czy siak robisz ZAWSZE Node *newOne = new Node(key,0,0); a delete żadnego nie widać, więc cieknie ci tam pamięć aż smutno...

a

Jeśli nie naprawiłeś tego swojego Tree:add to nic to nie zmieni bo nadal trzymasz strasznie dużo danych zupełnie bez potrzeby. Bo za każdym razem tworzysz nowy węzeł drzewa, niezależnie od tego czy faktycznie dodajesz nowy węzeł czy tylko dodajesz nowy element do listy w istniejącym węźle. Teraz zamiast 2 milionów konstantynopolitańczykowianeczek masz "tylko" milion, a ma być jedna...

Rozumiem o co chodzi. Jednakże jeśli będę każdorazowo sprawdzał, czy dany element znajduje się w drzewie to nie posypie się złożoność czasowa? Bo na razie nie widzę innego sposobu, żeby sprawdzić, czy węzel o danym kluczu już istnieje niż poszukanie go w drzewie.

PS. Na swoje usprawiedliwienie napisze, że właśnie taki sposób dodawania do drzewa został mi przedstawiony na zajęciach, więc liczyłem że algorytm da radę przejść przez sprawdzarkę.

No ale przecież ty i tak schodzisz w dół drzewa żeby znaleźć miejsce na ten nowy węzeł, więc gdzie tu jest dodatkowy narzut czasowy niby? Wystarczyłoby gdybyś zrobił zamiast tego funkcje, która dla podanego klucza znajduje ci:

• istniejący węzeł, jeśli już jest w drzewie -> wtedy tylko dodajesz nową pozycje do listy
• miejsce gdzie należy wpiąć nowy węzeł, jeśli klucza w drzewie jeszcze nie ma -> wtedy alokujesz nowy węzeł i dodajesz w to znalezione miejsce.