Proszę Was o sprawdzenie tego rozwiązania, lub zaproponowanie czegoś lepszego.
Zaprojektuj strukturę danych umożliwiającą wykonywanie następujących operacji:
(a) \(\displaystyle{ initialization:: S_i = \emptyset, i = 1, 2, .., n}\)
(b) \(\displaystyle{ insert (x,S_i):: S_i = S_i \cup \{x\}}\) pod warunkiem, że \(\displaystyle{ x}\) nie występuje w żadnym zbiorze.
(c)\(\displaystyle{ deletemin (S_i) ::}\) usunięcie najmniejszego elementu ze zbioru \(\displaystyle{ S_i}\)
(d) \(\displaystyle{ find(x)::}\) wyznaczenie numeru zbioru, do którego należy element \(\displaystyle{ x}\)
Użyję dwóch drzew AVL.
\(\displaystyle{ AVL\ t1}\) kluczem jest para : \(\displaystyle{ (idOfSet, element)}\)
\(\displaystyle{ AVL\ t2}\) kluczem jest para : \(\displaystyle{ (element, idOfSet)}\)
Będę używał zwykłych funkcji na drzewach AVL, zobaczcie:
Niech AVLfind zwraca parę \(\displaystyle{ (idOfSet, element)}\). Gdy elementu nie ma, zwraca \(\displaystyle{ (0,0)}\)
Kod: Zaznacz cały
find(x){
return AVLfind (t1, x).first;
}
insert (x, S_i){
if (find (x) = 0) {
AVLinsert (t1, (S_i, x));
AVLinsert (t2, (x, S_i));
}
}
findmin (S_i, myMin, root)){
if (root = NULL) {
return myMin;
}
if (t1.element.first > S_i){
return findmin (S_i, myMin, root->right);
}
else if (t1.element.first < S_i){
return findmin (S_i, myMin, root->left);
}
else{
return findmin (S_i, min (myMin, t1.element.second), root->left);
}
}
deletemin (S_i){
myMin = findmin (S_i, INF, root)
AVLdelete (t1, (S_i, myMin));
AVLdelete (t2, (myMin, S_i));
}