[Algorytmy] struktura danych + operacje na parach

[matematyka464]

Witam,
Zaprojektować s. danych, w której wszystkie operacje można wykonać w czasie \(\displaystyle{ O \left( \log \left( n \right) \right)}\).
\(\displaystyle{ \textbf{init} \left( S \right) ;}\)
\(\displaystyle{ \textbf{insert} \left( \left( x,y \right) , S \right) ;}\)
\(\displaystyle{ \textbf{min} _x \left( S \right)}\) - usunięcie z \(\displaystyle{ S}\) pary o najmniejszej składowej \(\displaystyle{ x}\)
\(\displaystyle{ \textbf{min} _y \left( S \right)}\) - usunięcie z \(\displaystyle{ S}\) pary o najmniejszej składowej \(\displaystyle{ y}\)
\(\displaystyle{ \textbf{search}_x \left( x, S \right)}\) - wyznaczenie takiej pary, \(\displaystyle{ \left( a,b \right)}\), ze \(\displaystyle{ x = a}\)
\(\displaystyle{ \textbf{search}_y \left( y, S \right)}\) - wyznaczenie takiej pary, \(\displaystyle{ \left( a,b \right)}\), ze \(\displaystyle{ y = b}\)

Jedyne co mi do głowy przychodzi to dwa drzewa AVL. Opiszę scenariusz.
1. Drzewo AVL.
sortuje pary \(\displaystyle{ \left( x,y \right)}\) lexykograficznie, pamięta dodatkowo w kazdym węźle minimum z całego poddrzewa (chodzi o minimum z wartości \(\displaystyle{ y}\)).
2. Drzewo AVL
sortuje pary \(\displaystyle{ \left( y,x \right)}\) lexykograficznei, pamiętam dodatkowo w każdym węźle minimum z całego poddrzewa (chodzi o minimum z wartości \(\displaystyle{ x}\)).

Wówczas wykonując operację insert wstawiam parę do obu drzew.
Jak wykonać \(\displaystyle{ \textbf{min}_x}\) ? W pierwszym drzewie usuwam najbardziej lewy liść, w drugim korzystam z minimum pamiętanego w każdym poddrzewie (wiem czy iść w lewo czy w prawo). Analogicznie z \(\displaystyle{ \textbf{min}_y}\). Widać, że drzewa mają taką samą zawartość.
A tak to, wygląda to dokłądnie tak samo jak usuwanie ze zwykłego drzewa AVL. Operację  \(\displaystyle{ \textbf{search}_x}\) i \(\displaystyle{ \textbf{search}_y}\) dam radę wykonać używając odpowiednio pierwszego, albo drugiego drzewa.


Czy to jest ok ? Wszak wartość minimalna z poddzewa może być przeciągana przez rotacje.
Ponadto, czy może da się jakoś lepiej to rozwiązać ? (bez drugiego drzewa)

[Afish]

1. Po co kombinować z jakimiś minimami poddrzew? Nie łatwiej trzymać wskaźnik na odpowiadający element w drugim drzewie?
2. Na oko da się to zrobić w jednej skipliście, trzymając w każdym węźle wskaźniki na następne elementy po współrzędnej \(\displaystyle{ x}\) oraz osobne wskaźniki po współrzędnej \(\displaystyle{ y}\).

[matematyka464]

1. Po co kombinować z jakimiś minimami poddrzew? Nie łatwiej trzymać wskaźnik na odpowiadający element w drugim drzewie?

Wskaźnik na odpowiadający element chyba jest ok faktycznie. Aczkolwiek można się w ogóle pozbyć tego narzutu. Powiedzmy, że skasowaliśmy z drzewa porządkowanego po iksie. ALe podczas, gdy go kasowaliśmy poznaliśmy wartość igreka. Tak więc z drugiego drzewa kasujemy parę, którą znamy w całości.

2. Na oko da się to zrobić w jednej skipliście, trzymając w każdym węźle wskaźniki na następne elementy po współrzędnej x oraz osobne wskaźniki po współrzędnej y.

Tak, ale będzie to i tak spory narzut pamięci na wskaźniki (ta struktura nie jest taka tania). Co więcej jest probablistyczna, tego wolałbym uniknąć.

[Afish]

Tak, ale będzie to i tak spory narzut pamięci na wskaźniki (ta struktura nie jest taka tania).

Wskaźniki będą i tak tańsze, niż dwa drzewa.

[matematyka464]

Ale probavlistyczności nie unikniesz

[Afish]

No to zrób dwa drzewa operujące na tych samych elementach i po sprawie. Będzie więcej kombinowania, niż ze skiplistą, ale technicznie nie będzie się to różniło od obsługi jednego drzewa.

[matematyka464]

Tak, to faktycznie także jest rozwiązanie! Wolę jednak pozostać przy dwóch drzewach z własnymi kluczami.

[Zordon]

Ja bym trzymał dwa drzewa par (w C++ mogą być sety pair<int,int>), oba posortowane leksykograficznie.
W jednym wrzucasz (x,y) a w drugim (y,x). Teraz każda operacja będzie wymagała zajrzenia do obu drzew. Wskaźniki nie są potrzebne.

[matematyka464]

Ja bym trzymał dwa drzewa par (w C++ mogą być sety pair<int,int>), oba posortowane leksykograficznie.
W jednym wrzucasz (x,y) a w drugim (y,x). Teraz każda operacja będzie wymagała zajrzenia do obu drzew. Wskaźniki nie są potrzebne.

Ja dokładnie to zaproponowałem!

Ale Ty nie powiedziałeś jak zapewnisz spójność danych między drzewami, po operacji minX, minY.

Ja podałem propozycje:
1. Utrzymujemy w drzewie \(\displaystyle{ minX}\) minimalną wartość \(\displaystyle{ y}\) z poddrzewa.

A Ty ?

[Zordon]

Nie rozumiem. Za każdym razem gdy chcę dodać do struktury (x,y):
1) dodaję do pierwszego drzewa (x,y)
2) dodaję do drugiego drzewa (y,x)
Za każdym razem gdy chcę usunąć ze struktury (x,y):
1) usuwam z pierwszego drzewa (x,y)
2) usuwam z drugiego drzewa (y,x)

Zauważ, ze u mnie struktura="dwa drzewa"

[matematyka464]

Tak, tylko że nikt nie powie jaką parę chce usunąć. Tylko ma dwie funkcje minx, miny. Która usuwa parę o minimalnym x, lub gdy wołał miny to o minimalnym y.


PS zapraszam także do tematu 378829.htm

[Zordon]

Jak to nie wiesz?
Szukasz odpowiednio w pierwszym albo drugim drzewie...