[C++] Implementacja drzewa przedziałowego na secie

satre
Użytkownik
Użytkownik
Posty: 17
Rejestracja: 26 mar 2010, o 15:36
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 1 raz

[C++] Implementacja drzewa przedziałowego na secie

Post autor: satre » 12 wrz 2011, o 23:37

Słyszałem, że drzewo przedziałowe można zaimplementować z wykorzystaniem stl-a a dokładniej set-a. (zawsze to kilka linijek mniej kodu niż jak bym miał sam je implementować). Drzewo takie ma mieć dopuszczone dwie operacje: dodaj(klucz,wartość) oraz max_z_przedziału(a,b).
Proszę więc Was o pomoc lub jakiś link z implementacją takiego drzewa.

Z góry dziękuje za pomoc.
Ostatnio zmieniony 13 wrz 2011, o 09:45 przez Afish, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.

Awatar użytkownika
Zordon
Gość Specjalny
Gość Specjalny
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 909 razy

[C++] Implementacja drzewa przedziałowego na secie

Post autor: Zordon » 12 wrz 2011, o 23:59

Kto Ci takich rzeczy naopowiadał . Niech się wstydzi. Takie drzewo implementuje się samemu na tablicy, co jest nawet kilka-(nascie) razy wydajniejsze niz typowe operacje na secie. Pomijam już tutaj fakt, że na secie się tego nie da zrobić, a nawet jeśli to nakład pracy nie będzie mniejszy niż pisanie własnego drzewa. W poszukiwaniu implementacji polecam przeszukać google, w szczególności po angielsku warto szukać "segment tree".

Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[C++] Implementacja drzewa przedziałowego na secie

Post autor: paladin » 16 wrz 2011, o 19:17

Na takim "gotowym" secie z STL faktycznie byłoby trudno.

Można by użyć drzewa czerwono-czarnego, czyli de facto napisać własnego seta, bardzo podobnego do tego z STL, który pozwalałby na dodatkową operację maksimum na przedziale. Ale jest to oczywiście znacznie bardziej pracochłonne.

ODPOWIEDZ