Cześć, miałem za zadanie zaimplementować drzewo binarne BST. Mam to juz zrobione. Dodawanie elementów działa wyśmienicie dla małych zbiorów jednak dla większych to już długie czekanie (dla 100 000 elementów to aż ~40 sekund!!)
Z listą wiązana jednokierunkowa był podobny problem, lecz tam dodałem ogon dzięki czemu przy dodawaniu elementu pozbyłem się iteracji, która zjadała czas.
W Internecie poszperałem, że domyślny set w CPP to drzewo binarne, dlaczego więc dodanie miliona to ułamek sekundy? Jak ta struktura jest zbudowana, jak to rozwiązali?
Moja funkcja add to po prostu pętla i wyszukuje najmniejszy lub największy klucz.
Mój pomysł: Aby przyspieszyć proces moge zapamiętać referencje do węzłow o kluczach najmniejszych i największych i zamiast pętli do nich się odwoływać - czy to jest dobry pomysł?
Jak w takim razie rozwiązuje to standardowy zbiór set w CPP? Może podobnie?
Drugie pytanie.
Poszperalem artykuły programistyczne, znalazłem kilka struktur. Dodawanie było oparte na rekurencji. Owszem, działało, ale dla małych zbiorów. Dla miliona elementów już wyrzucało błąd stosu i kończyło działanie programu. Czy Ci co pisali takie artykuły nie powinni się wstydzić?
Dodam, że dodawałem elementy uporządkowane. Wiec jest to drzewo zdegenerowane, no ale i tak..