Prowadzę kurs na temat struktur danych i na początku przyszłego tygodnia zajmę się drzewami splay. Wiele razy czytałem artykuł na temat drzew splay i znam się na analizie i intuicji stojących za strukturą danych. Nie mogę jednak znaleźć solidnej intuicji dla potencjalnej funkcji, której Sleator i Tarjan używają w swojej analizie.

Analiza polega na przypisaniu każdemu elementowi drzewa dowolnej wagi $w_i$ , a następnie ustawieniu rozmiaru $s(x)$ węzła jako sumy wag węzłów w poddrzewie zrootowanych na $x$ . Następnie pobierają dziennik tej wartości, aby uzyskać rangę $r(x)$ węzła, więc $r(x) = \log s(x)$ . Wreszcie potencjalna funkcja drzewa jest zdefiniowana jako suma rang wszystkich węzłów.

Rozumiem, że ta potencjalna funkcja działa poprawnie i mogę śledzić analizę, ale nie rozumiem, dlaczego wybrali ten potencjał. Pomysł przypisania rozmiaru do każdego węzła ma dla mnie sens, ponieważ jeśli zsumujesz rozmiary, otrzymasz ważoną długość ścieżki drzewa. Nie mogę jednak zrozumieć, dlaczego zdecydowali się wziąć kłody ciężarów, a następnie podsumować je zamiast tego - nie widzę żadnej naturalnej właściwości drzewa, z którą to odpowiada.

Czy potencjalna funkcja drzewa splay odpowiada jakiejś naturalnej właściwości drzewa? Czy istnieje jakiś inny powód, niż „to działa”, że wybrali ten potencjał? (Jestem szczególnie ciekawy, ponieważ w tym zestawie notatek oczywiście wspomniano, że „analiza to czarna magia. [Nie wiem, jak odkryto”)

Dzięki!

Jak wymyślić potencjał sumowania dzienników

Rozważmy BST algorytm że dla każdego dostępu dla elementu x , to reorganizuje tylko elementy w ścieżce wyszukiwania P od x wezwany przed-ścieżki, do jakiegoś drzewa zwane po-drzewa. Dla dowolnego elementu a , niech s ( a ) i s ′ ( a ) będą wielkością poddrzewa zakorzenionego odpowiednio przed i po przegrupowaniu. Tak więc y ( ) i y ' ( ) może różnić się wtedy i tylko wtedy jest ∈ P .$A$$x$$P$$x$$a$$s(a)$$s'(a)$$a$$s(a)$$s'(a)$$a \in P$

Ponadto $A$ zmienia tylko ciągle wiele elementów ścieżki wyszukiwania w dowolnym momencie. Nazwijmy ten algorytm algorytmem „lokalnym”. Na przykład drzewo splay jest lokalne. Układa jednocześnie maksymalnie 3 elementy jednocześnie za pomocą zig, zigzig i zygzak.

Teraz każdy lokalny algorytm, który tworzy „wiele” liści w drzewie pospolitym, taki jak drzewo splay, ma następującą przyjemną właściwość.

Możemy utworzyć odwzorowanie takie, że$f: P \rightarrow P$

1. Istnieje liniowo wiele , gdzie s ′ ( f ( a ) ) ≤ s ( a ) / 2 .$a \in P$$s'(f(a)) \le s(a)/2$
2. Ciągle jest wiele , gdzie s ′ ( f ( a ) ) może być duże, ale trywialnie co najwyżej n .$a \in P$$s'(f(a))$$n$
3. Inne elementy , s ′ ( f ( a ) ) ≤ s ( a ) .$a \in P$$s'(f(a)) \le s(a)$

Możemy to zobaczyć, rozwijając zmianę ścieżki wyszukiwania. Mapowanie jest w rzeczywistości całkiem naturalne. Ten artykuł, A Global Geometric View of Splaying , dokładnie pokazuje szczegóły, jak zobaczyć powyższą obserwację.

Po zapoznaniu się z tym faktem bardzo naturalne jest wybranie potencjału sumy logów. Ponieważ możemy wykorzystać potencjalną zmianę elementów typu 1, aby zapłacić za całe przegrupowanie. Co więcej, w przypadku elementów innego rodzaju musimy zapłacić za potencjalną zmianę co najwyżej logarytmicznie. Dlatego możemy uzyskać logarytm zamortyzowanego kosztu.

Myślę, że powodem, dla którego ludzie myślą, że jest to „czarna magia”, jest to, że poprzednia analiza nie „ujawnia” ogólnej zmiany ścieżki wyszukiwania i widzi, co naprawdę dzieje się w jednym kroku. Zamiast tego pokazują zmianę potencjału dla każdej „lokalnej transformacji”, a następnie pokazują, że te potencjalne zmiany można magicznie teleskopować.

PS W pracy pokazano nawet pewne ograniczenie potencjału sumy logów. Oznacza to, że można udowodnić satysfakcję z dostępu do lematu poprzez potencjał sumy logów tylko do lokalnego algorytmu.

Interpretacja potencjału sumy logów

Istnieje inny sposób zdefiniowania potencjału BST w pracy Georgakopoulos i McClurkina, który jest zasadniczo taki sam jak potencjał sumy logów w pracy Sleator Tarjan. Ale to daje mi dobrą intuicję.

Teraz przechodzę do notacji papieru. Przypisujemy wagę do każdego węzła u . Niech W ( U ) jest sumą wagi u jest poddrzewem. (Jest to tylko rozmiar poddrzewa u , gdy waga każdego węzła wynosi jeden.)$w(u)$$u$$W(u)$$u$$u$

Teraz zamiast definiować rangę w węzłach, definiujemy rangę do krawędzi, które nazywali współczynnikiem postępu .

A potencjał drzewa jest$S$

Ten potencjał ma naturalną interpretację: jeśli podczas przeszukiwania przemierzamy krawędź , zmniejszamy przestrzeń poszukiwań od potomków u do potomków v , frantional redukcja W ( u ) / W ( v ) . Nasz współczynnik postępu jest logarytmiczną miarą tego „postępu”, stąd jego nazwa. [Z sekcji 2.4]$(u,v)$$u$$v$$W(u)/W(v)$

Zauważ, że jest to prawie równy potencjał Sleator Tarjan i jest addytywny na ścieżkach.

edytuj: Okazuje się, że ta alternatywna definicja i intuicja za nią została opisana dawno temu przez Kurta Mehlhorna. Zobacz jego książkę „Struktury danych i algorytmy” Tom I, Sekcja III. 6.1.2 Drzewa splay, strony 263–274.