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.
[C++] Implementacja drzewa przedziałowego na secie
-
- 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
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.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
[C++] Implementacja drzewa przedziałowego na secie
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".
- paladin
- 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
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.
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.