Marzyłem o strukturze danych, czy ona istnieje?

Nie udało mi się znaleźć tej struktury danych, ale nie jestem ekspertem w tej dziedzinie.

Struktura implementuje zestaw i jest w zasadzie szeregiem porównywalnych elementów z niezmiennikiem. Niezmiennikiem jest to (zdefiniowane rekurencyjnie):

Tablica o długości 1 jest tablicą scalającą.

Tablica o długości 2 ^ n (dla n> 0) jest tablicą scalającą iff:

pierwsza połowa jest tablicą scalającą, a druga połowa jest pusta lub
pierwsza tablica jest pełna i posortowana, a druga połowa to tablica scalająca.

Zauważ, że jeśli tablica jest pełna, jest sortowana.

Aby wstawić element, mamy dwa przypadki:

Jeśli pierwsza połowa nie jest pełna, włóż rekurencyjnie do pierwszej połowy.
Jeśli pierwsza połowa jest pełna, włóż rekurencyjnie do drugiej połowy.
Po zakończeniu cyklu rekurencyjnego, jeśli cała tablica jest pełna, połącz połówki (które są posortowane) i zmień jej rozmiar do dwukrotności pierwotnej długości.

Aby znaleźć element, powtórz w obu połowach, używając wyszukiwania binarnego, gdy tablica jest pełna. (Powinno to być skuteczne, ponieważ istnieje najwyżej rosnących fragmentów). $O(\log(n))$

Strukturę można traktować jako statyczną wersję scalania.

Nie jest jasne, co należy zrobić, aby usunąć element.

Edycja: po poprawieniu mojego zrozumienia struktury.

ds.data-structures pbaren
źródło

Zdefiniowałeś to, dlatego istnieje. Myślę jednak, że musicie wygładzić niektóre punkty. Po pierwsze, niezmiennik nr 2 wprawia mnie w zakłopotanie, ponieważ wydaje się, że nie stosuje się do stanów pośrednich podczas ich opisywania. Po drugie, co robisz po usunięciu elementów?

Raphael,

Śniłeś się strukturę danych, nie marzył o niej ...

Andrej Bauer

@Raphael Dzięki za komentarze, poprawiłem definicję podążając za twoimi przemyśleniami. Nie myślałem o algorytmie do usuwania, chciałem tylko sprawdzić, czy ta struktura jest w literaturze, zanim poświęciłem jej więcej czasu (i nie mogłem znaleźć niczego w Google). W pierwszym zdaniu możesz zdefiniować Boga, ale czy on istnieje? :)

pbaren,

@Andrej Dzięki, angielski nie jest moim językiem ojczystym. (

Wydaje

@Andrej: PO pierwotnie miał „marzył o ”, który jest prawie na pewno nie to, co myśli. Zmieniłem to na „z” zamiast „w górę”. Oba są poprawne gramatycznie, ale oba również zmieniają znaczenie. „Of” było ciekawszą opcją…

András Salamon,

Odpowiedzi:

$A\cup B$ $A$ $B$ $O(\log n)$ $n$ ), ale zwiększa przestrzeń tylko o stały współczynnik. Tak, można to zdemontować dzięki Overmars i van Leeuwen, ale tak naprawdę nie chcesz tego robić, jeśli nie musisz.

Te uwagi dotyczą podstaw.

Tablice wyprzedzające pamięć podręczną to zmutowane potomstwo drzew Bentley-Saxe i van Emde Boas na sterydach.

Jeffε
źródło

Są to pięknie napisane i zilustrowane notatki, z których wielokrotnie korzystałem. Dziękujemy za udostępnienie ich!

jbapple,

Widzę, w jaki sposób drzewa wahadłowe (z pierwszej połowy artykułu przedstawiającego pamięć podręczną niewidzialne tablice wyprzedzające) są powiązane z drzewami vEB, ale jaki jest związek między COLA a drzewami vEB?

jbapple,

Dzięki, ten materiał wydaje się bardzo interesującym uogólnieniem pomysłu. Zawsze myślałem, że struktury danych to zamrożone algorytmy, które można uruchomić krok po kroku, ale nigdy nie znalazłem przydatnej formalizacji tej intuicji.

pbaren,

Czy pierwszy link działał dla kogoś innego?

Tak, właśnie tego spróbowałem. (Niestety, chodzi o

zaporę

Jest to podobne do drzew scalonych o strukturze dziennika lub pamięci podręcznej niewiadomych tablic wyprzedzających (lub COLA).

$2^k-1$ $2^i$ $0 \leq i < k$

$2^0$ $2^1$

$O(\lg n)$ $O(n)$ $O(\lg^2 n)$

jbapple
źródło