Drzewo statystyk porządkowych

Jakie Problemy Rozwiązuje

Drzewo porządkowe pozwala na szybkie odnalezienie k-tego najmniejszego elementu w czasie stałym, poprzez bezpośredni indeksowanie. Odpowiedź na pytanie o stopień elementu x wykonywana jest w czasie logarytmicznym za pomocą wyszukiwania binarnego. Problem polega jednak na tym, że wstawianie lub usuwanie wartości z drzewa porządkowego kosztuje czas liniowy, ponieważ wszystko po pozycji odbiorczej musi przesunąć się. Proste drzewo równoważne binarnego wyszukiwania odwraca tę proporcję: wstawianie i usuwanie są logarytmiczne, ale znalezienie k-tego najmniejszego elementu wymaga przejścia po porządku wstępnym, które kosztuje czas liniowy, ponieważ drzewo nie przechowuje żadnej informacji o liczbie elementów znajdujących się w każdym poddrzewie. Niemniej ani jedno z tych struktur nie daje szybkich wersji wszystkich czterech operacji naraz: wyszukiwanie, wstawianie, usuwanie i selekcja oparta na stopniu. Drzewo statystyk porządkowych zamyka tę lukę poprzez ulepszenie drzewa równoważnego, najczęściej czerwono-czarnego, dodając do każdego węzła jedno liczbę całkowitą reprezentującą rozmiar poddrzewa. Ponieważ drzewo czerwono-czarne już gwarantuje wysokość drzewa O(log n) poprzez swoje zasady koloru i równowagi, a rozmiar poddrzewa można utrzymać podczas tych samych obrótów, które zachowują te zasady, ulepszenie jest prawie bezkosztowe. Dodaje stałą ilość miejsca na każdy węzeł oraz stałą dodatkową pracę dla każdego obrotu, otwierając selekcję i zapytania dotyczące stopnia, które inaczej wymusiłyby pełny przebieg. Ten wzór jest uogólniony: taka sama technika ulepszenia dotyczy drzew interwałowych, które przechowują końce maksymalne poddrzew, lub drzew przechowujących sumy poddrzew dla zapytań agregacyjnych zakresu. W każdym przypadku podstawowe drzewo równoważne dostarcza wysokość logarytmiczną, a odpowiednio dobrany pola ulepszające, aktualizowany w czasie stałym dla każdego obrotu, dostarcza dodatkowe szybkie zapytanie bez renegocjacji wydajności operacji wstawiania i usuwania oryginalnego drzewa. Drzewo statystyk porządkowych jest kanonicznym, najprostszym przykładem tej techniki ulepszenia, a dobrze zrozumienie jej działania czyni bardziej skomplikowane struktury ulepszonej znacznie łatwiejszymi do zrozumienia.

Zwiększenie: Przechowywanie Rozmiaru Poddrzewa

Każdy węzeł x w drzewie statystyk porządkowych nosi pole size[x], zdefiniowane jako liczba węzłów w poddrzewie korzeniowanym w x, wliczając sam węzeł x. Formalnie, size[x] = size[left[x]] + size[right[x]] + 1, gdzie puste dziecko przyczynia się zero. Ta rekurencyjna definicja jest to, co sprawia, że utrzymanie jest manegwerowalne: kiedy zmieniają się dzieci węzła, jego pole size można obliczyć na podstawie jedynie bezpośrednich dzieci, bez dalszego przeszukiwania drzewa. W standardowym wprowadzeniu do drzewa binarnego wyszukiwania, nowy węzeł dodawany jest jako liść na końcu ścieżki od korzenia do liścia; każdy przodek na tej ścieżce zyskuje dokładnie jednego potomka, więc pola size każdego z nich zwiększa się o jeden podczas powrotu wprowadzania lub równoważnie jest inkrementowane podczas przeszukiwania w dół przed załączeniem liścia. Usunięcie symetrycznie: usuwanie węzła zmniejsza pole size każdego z jego przodków o jeden. Trudniejszym przypadkiem jest obrót, operacja, której używa drzewo czerwono-czarne do przywrócenia równowagi po wprowadzeniu lub usunięciu. Obrót, czyli w lewo czy w prawo, zmienia, który z dwóch węzłów jest rodzicem a który dzieckiem, co oznacza, że zmienia, które poddrzewo należy do którego. Konkretnie, przy obrócie w lewo wokół węzła x z prawym dzieckiem y, węzeł y zastępuje węzeł x, a węzeł x staje się lewym dzieckiem y, a jego poprzednie lewe poddrzewo staje się nowym prawym poddrzewem x. Po tej operacji chirurgicznej tylko dwa pola size potrzebują obliczenia i muszą być obliczone w odpowiedniej kolejności: najpierw size[x], używając teraz zaktualizowanych dzieci węzła x, a następnie size[y], używając nowego lewego dziecka y, czyli węzła x, oraz niezmienionego prawego dziecka y. Ponieważ tylko stały liczba węzłów ma swoje członkostwo poddrzewa zmienione przez dowolny obrót pojedynczy, aktualizacja pól size dodaje tylko stałe obciążenie do każdego obrócenia, co pozostawia ogólne wprowadzenie lub usunięcie O(log n).

OS-SELECT: Znajdowanie k-tego najmniejszego elementu

Funkcja OS-SELECT(x, k) znajduje węzeł zawierający k-tym najmniejszy klucz w poddrzewie korzeniowanym w węźle x, wykorzystując pola wielkości do podejmowania zainformowanych decyzji na każdym kroku zamiast eksplorować drzewo bez celu. Procedura rozpoczęta jest obliczeniem r = size[left[x]] + 1, co to rangę węzła x w swoim własnym poddrzewie: wszystko w lewym poddrzewie x jest mniejsze od x, więc sam x jest (r)-tym najmniejszym elementem w tym poddrzewie. Trzy przypadki następują. Jeśli k równa się r, węzeł x dokładnie jest odpowiedzią, a wyszukiwanie kończy się natychmiast. Jeśli k jest mniejsze od r, szukany k-tym najmniejszy element musi leżeć gdzieś w lewym poddrzewie, ponieważ to poddrzewo samodzielnie zawiera przynajmniej k elementów mniejszych lub równych tym potrzebnym; algorytm rekursywnie przechodzi do left[x] z tym samym wartością k. Jeśli k jest większe od r, szukany element leży w prawym poddrzewie, ale jego rangę tam ma on niższą niż k, ponieważ r elementów, czyli x i całe lewego poddrzewa, są już znane jako przystępujące przed nim; algorytm rekursywnie przechodzi do right[x] z odpowiednio dostosowaną wartością k minus r. To nie jest pełny przebieg drzewa; to jedno opuszczenie od korzenia do węzła odpowiedziowego, wykonując dokładnie jedną decyzję opartą na porównaniach na każdym poziomie. Ponieważ wysokość drzewa wynosi O(log n) zgodnie z niezawodności balansowania, OS-SELECT działa w czasie O(log n). Kontrastuj to z podejściem do przebiegu w porządkuABCDEFGH, które musi odwiedzić i policzyć aż k węzłów, potencjalnie dotykając dużej części drzewa; OS-SELECT zamiast tego przycinanie całe poddrzewo na każdym kroku, w którym nie ma potrzeby eksploracji, dokładnie tak jak wyszukiwanie binarne przycina połowę przestrzeni poszukiwania przy każdym porównaniu.

OS-RANK: Znajdowanie Położenia Elementu

OS-RANK(T, x) odpowiada na odwrotną odpowiedź: dana jest wskazówka do węzła x już znalezionego w drzewie, jakie jest jego stopień, czyli położenie, gdy całe drzewo zostanie uporządkowane i listowano? Algorytm wykorzystuje te same pola wielkości, ale przesuwa się w górę od x w kierunku korzenia zamiast w dół od korzenia. Inicjalizuje on licznik r = size[left[x]] + 1, stopień x w swoim własnym poddrzewie, dokładnie tak jak w OS-SELECT. Następnie przewija drzewo po jednym rodzaju na raz. Na każdym kroku, jeśli obecny węzeł y jest prawym dzieckiem swojego rodzica, to oznacza to, że rodzic i całe poddrzewo lewostronne rodzica, wraz z samym rodzicem, mają klucze mniejsze niż wszystko przeliczone do tej pory, więc algorytm dodaje size[left[parent]] + 1 do r przed przejściem w górę do rodzica. Jeśli y jest zamiast tego lewym dzieckiem swojego rodzica, nic nie należy dodać, ponieważ rodzic i reszta poddrzewa są większe, a licznik r pozostaje niewykorzystany; algorytm po prostu przechodzi w górę do rodzica. To kontynuuje się aż do osiągnięcia korzenia, na którym punkt r zawiera właściwy stopień ogólny x w całości drzewie. Ponieważ ta przeszukanie śledzi pojedynczą ścieżkę od korzenia do węzła w odwrotnej kolejności, a długość tej ścieżki wynosi O(log n) w zbalansowanym drzewie, OS-RANK również działa w czasie O(log n). Zauważmy elegancką symetrię między OS-SELECT i OS-RANK: jedno opada używając pól wielkości do znalezienia węzła na podstawie docelowego stopnia, a drugie podnosi się używając pól wielkości do obliczenia stopnia na podstawie znalezionego węzła, i oba wykorzystują dokładnie tę samą uzupełnianie i dokładnie tę sama granica asymptotyczna.

Praktyczne zastosowanie: Strumieniowe mediane i procenty

Naturalnym zastosowaniem drzewa statystyk porządkowych jest utrzymanie statystyk, takich jak mediana lub dowolny procent, nad zestawem danych, który ciągle się zmienia, z wartościami wstawianymi i usuwanymi kontynuacyjnie, np. strumień żywy z odczytów czujników, kwot transakcyjnych lub pomiarów opóźnienia. Naive rekomputacja mediana wymaga posortowania całego zestawu danych przy każdym przybyciu lub odejściu wartości, co prowadzi do kosztu rosnącego bez granic, ponieważ każda z n aktualizacji kosztuje O(n log n) dla nowego sortowania. Z drzewem statystyk porządkowych każdy nowy element jest wstawiany w czasie O(log n), a drzewo automatycznie odzyskuje równowagę,aktualizując pola wielkości podczas opisanej wcześniej operacji. Kiedy potrzebna jest obecna mediana, pojedyncza wywołanie OS-SELECT z k = (n+1)/2 dla nieparzystego n lub średnia z (n/2)-tego i (n/2+1)-tego najmniejszego dla parzystego n, zwraca ją w czasie O(log n), korzystając z pola wielkości dziecka lewego potomka korzenia, aby natychmiast wiedzieć, czy mediana do tej pory znajduje się po lewej stronie, prawej stronie lub na samym korzeniu. Ten sam pomysł można prosto rozszerzyć na dowolne procenty: 90%-ty procent n elementów odpowiada k = ceil(0.9 * n), a OS-SELECT znajduje go z tym samym jednym spadkiem, niezależnie od tego, jak duży stanie się n. To sprawia, że drzewo statystyk porządkowych jest atrakcyjne dla paneli i systemów monitoringu, które muszą raportować metryki poziomu usługi oparte na procentach, takie jak 95%-ty-procentowy czas odpowiedzi, ciągle wraz z nowymi odczytami i starzaniem się starych. Drzewo statystyk porządkowych również przewyższa naive schemat dwu-heapów do śledzenia mediana, gdy są wymagane dowolne procenty, a nie tylko mediana, ponieważ dwie heapy są specjalizowane dla ustalonego punktu podziału, w przeciwieństwie do jednego drzewa statystyk porządkowych, które spełniają dowolny zapytanie rank na żądanie. Usunięcie dowolnych elementów, a nie tylko ekstremów, jest również obsługiwane prosto, co kontrastuje z wielu schematach opartych na heapis.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Order-Statistics Tree i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.