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! :))))

dwa drzewa to coś istotnie prostszego niż drzewo + kopiec? :D

A jak z dwoma drzewami byś to zrobił?

dwa AVL, gdzie jeden posortowany po x, drugi po k. i kazdy węzeł ma powiązanie do odpowiadającego węzła w drugim drzewie

Czy w ten sposób nie tracimy Max(S) w czasie stałym?

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ę.

drzewo + kopiec = drzepiec! :)

LOL jakieś za przeproszeniem dziwne te zadania 0_o