Witam używam struktury danych C++ z bliblioteki <set> , jak wyczytałem jest to drzewo binarne.
Dodaję sobie do niego element metodą .insert(val), która po każdym wywołaniu przywraca własność drzewa, tak że elementy są znowu posortowane. Pytanie brzmi jaka jest złożoność tej opracji, bo z tego co wyczytałem to dla drzewa binarnego czas posortowania to po prostu log(n), czy tutaj jest tak, ktoś się orientuje może ?
0
0
std::set uzywa tego http://en.wikipedia.org/wiki/Red%E2%80%93black_tree i nie wykonuje zadnego sortowania przy wstawianiu elementow.
0
std::set::insert musi mieć przynajmniej złożoność logarytmiczną. Takie wymaganie narzuca standard. Metoda implementacji nie powinna Cie interesować w zasadzie.