Czy istnieje ekwiwalent drzew van Emde Boasa dla lin?

Ktoś, kogo znam, planuje wdrożyć edytor tekstu w najbliższej przyszłości, co skłoniło mnie do zastanowienia się, jakie struktury danych są szybkie dla edytora tekstu. Najczęściej stosowanymi konstrukcjami są najwyraźniej liny lub bufory szczelinowe .

Drzewa Van Emde Boas są prawie najszybszymi kolejkami priorytetowymi, jeśli nie przeszkadza ci górna granica liczby przedmiotów, które możesz w nie umieścić, i duży koszt inicjalizacji. Moje pytanie dotyczy tego, czy istnieje struktura danych, która jest tak szybka jak drzewo van Emde Boasa, ale obsługuje operacje edytora tekstu.

W naszej strukturze danych musimy obsługiwać maksymalnie znaków (więc jeśli$m$$\log m = 32$ , to obsługujemy znaki ASCII o wartości do 4 GB). Możemy czas na zainicjowanie nowej struktury danych. Chcielibyśmy wspierać następujące operacje:$\sqrt{m}$

• Wstaw znak w pozycji do O ( log log m ) (a tym samym zwiększając pozycję każdego kolejnego znaku o 1).$i$$O(\log \log m)$
• Usuń znak z pozycji w O ( log log m ) .$i$$O(\log \log m)$
• Zwraca znak w pozycji w O ( log log m ) .$i$$O(\log \log m)$

Zatem wstawienie (0, „a”), a następnie wstawienie (0, „b”) powoduje „ba”.

Jeszcze lepiej byłoby to:

• Zwraca „wskaźnik” do jakiegoś indeksu w O ( log log m ) .$i$$O(\log \log m)$
• Biorąc pod uwagę „wskaźnik”, zwróć znak w tej pozycji w .$O(1)$
• Biorąc pod uwagę „wskaźnik”, usuń znak z tej pozycji w .$O(1)$
• Biorąc pod uwagę „wskaźnik”, dodaj znak w tej pozycji w i umieść wskaźnik w następującej pozycji.$O(1)$
• (opcjonalnie) Biorąc pod uwagę „wskaźnik”, zwróć „wskaźnik” do następnego / poprzedniego znaku w .$O(1)$

Fredman i Saks pokazują w „Złożoności sond komórkowych dynamicznych struktur danych”, że nie można zrobić lepiej niż zamortyzowany czas na operacje, których szukasz. Nazywają ten problem „reprezentacją listy”.$\Theta\left(\frac{\lg m}{\lg \lg m}\right)$

Dietz przedstawił strukturę danych w „Optimal Algorytm for Indexing List and Subset Rank”, która osiągnęła ten limit.