Forum matematyczno-informatyczne
Pierwszy!
Co byście powiedzieli na taką strukturę? Skończony multizbiór S z operacjami?
Insert (S, x, k) - wstawia k egzemplarzy x
Delete(S, x, k) - usuwa k egzemplarzy x (albo wszystkie jak jest mniej niż k)
Max(S) - zwraca element o największej liczbie wystąpień
Czy da się wymyślić coś lepszego i prostszego od drzewo + kopiec?
//No i drugie zadanko. Wykaż, że żeby scalić k uporządkowanych list długości n,
//trzeba zrobić Omega(n k log(k)) porównań. Zaprojektuj algorytm.
//Wiem jak zrobić dowód, ale nie wiem jaki jest ten algorytm.
Już wiem! )))
Ostatnio edytowany przez Maciek (2007-12-15 22:41:07)
Offline
Tak, tracimy.
A teraz z innej beczki? Czy mi sie wydaje czy mogę trzymać w węzłach drzewa BST wskaźniki do jego poprzednika/następnika? I łatwo je uaktualniać przy wstawianiu/usuwaniu? Bo szukam przeszkód, ale doszukać się nie mogę.
Offline