Czy istnieje struktura danych umożliwiająca szybkie manipulowanie listami i zapytania dotyczące zamówień?

Mamy zestaw, $L$, list elementów z zestawu $N = \{ 1, 2, 3, ..., n \}$. Każdy element z$N$ pojawia się na jednej liście w $L$. Szukam struktury danych, która może wykonać następujące aktualizacje:

1. $concat(x, y)$ : konkatenuje listę zawierającą $y$ na końcu listy zawierającej $x$

2. $split(x)$ : dzieli listę zawierającą $x$ bezpośrednio po $x$

Musi także wykonać następujące zapytania:

1. $follows(x, y)$ : zwroty $true$ gdyby $x$ i $y$ są na tej samej liście i $y$ Przyjść po $x$ (ale niekoniecznie przylega do $x$)

2. $first(x)$ : zwraca pierwszy element listy zawierający $x$

3. $next(x)$ : zwraca następny element po $x$ na liście zawierającej $x$

Już opracowałem strukturę danych, która wykonuje te aktualizacje w $O(lg^2 (n))$ i zapytania w $O(lg (n))$czas. Najbardziej interesuje mnie, czy istnieje już struktura danych, która może to zrobić (mam nadzieję, że szybciej?).

Motywacja: zrootowane ukierunkowane lasy mogą być reprezentowane za pomocą dwóch z tych zestawów list i umożliwiają szybkie obliczenie dostępności w takich lasach. Chcę zobaczyć, do czego jeszcze można je wykorzystać i czy to wszystko jest już znane.

Trzymaj liczby całkowite na listach pominięć. Normalne listy pominięć są uporządkowane według klucza, ale użyjemy ich jako reprezentacji sekwencji. Dodatkowo zachowaj tablicę wskaźników wielkości$n$. Każdy element tablicy powinien wskazywać węzeł na liście pominięć. Wierzę, że to popiera$next$ w $O(1)$ i wszystkie inne operacje w $O(\lg n)$.

Konkretnie:

• $concat$ing lub $split$trwa dwie listy pominięć $O(\lg n)$ czas i dlatego unieważnia co najwyżej $O(\lg n)$ wskaźniki
• $next$ po prostu podąża za wskaźnikiem do przodu na poziomie liścia, biorąc $O(1)$ czas.
• $first$ trwa $O(\lg n)$czas: podążaj za wskaźnikami, aż utkniesz, a następnie podążaj za lewym wskaźnikiem. Gdy nie możesz już podążać za lewymi wskaźnikami, jesteś na czele listy pomijanych. Śledź wskaźniki w kierunku liścia, a następnie jeden wskaźnik do przodu. To pierwszy element na liście.
• $follows$jest nieco trudniejszy. Postępuj jak w$first$ dla $y$, ale zapisz listę wartości, w których utknąłeś (tzn. w których nie możesz już śledzić wskaźników). Nazwiemy tę listę, aby zarejestrować „ślad”. Zrób to samo dla$x$, ale postępuj zgodnie ze wskazówkami, gdy utkniesz, a nie w lewo. Gdyby$x$ poprzedza $y$ich ślady się przecinają. Ślady są wielkości$O(\lg n)$. Jeśli każdy element w śladzie jest opatrzony adnotacją o zablokowanym poziomie, możemy sprawdzić, czy nie ma przecięcia w czasie$O(\lg n)$.

$next$ to najgorszy przypadek $O(1)$, wszystkie inne są $O(\lg n)$ z dużym prawdopodobieństwem . Można to zrobić w najgorszym przypadku, stosując deterministyczne listy pominięć.

Myślę $concat$ da się zrobić $O(\lg \lg n)$używając drzew połączonych na poziomie liści (2,5) i zaczepiając kolce. Aby dowiedzieć się więcej na temat ładowania początkowego, zobacz „ Czysto funkcjonalne reprezentacje możliwych do posortowania list posortowanych ” autorstwa Kaplana i Tarjana.

Najmniej wspólny przodek problem może być stosowany w celu rozwiązania problemu osiągalności w dynamicznych korzenie drzew, więc sobie wyobrazić, będzie również zainteresować następujące: Optymalne algorytmy Znalezienie Najbliższe wspólnych przodków w dynamicznych Drzewa , przez Alstrup i Thorup. W tym dokumencie określono termin$O(n + m \log \log n)$ dla $n$ linki i $m$ zapytania nca na maszynie wskaźnikowej.