Drzewa splay: Samoaktualizujące się drzewo binarne wyszukiwania

Co sprawia, że drzewo splay jest samooptymalizujące

Drzewo binarne wyszukiwania jest strukturą pasywną: przechowuje wartości w porządku, ale żadna operacja wyszukiwania nie zmienia jego kształtu. Drzewo splay jest inaczej, ponieważ każda operacja dostępu, czyli wyszukiwanie, wstawianie lub usuwanie, spowoduje przeformowanie struktury podczas wykonania kroku zwanej splingiem. Po lokalizacji węzła docelowego, drzewo wykona serię rotacji, które przewińą ten exact węzeł przez swoje przodekty aż do momentu, gdy stanie się nowym korzeniem. To oznacza, że kształt drzewa jest żywym zapisem najnowszych aktywności, a nie ustalonym rozkładem wybranym jednorazowo podczas budowy. Nie ma potrzeby przechowywania dodatkowych informacji o równowadze, takich jak wysokość lub kolory używane przez inne samooptymalizujące drzewa. Zamiast tego struktura sama wykonuje pracę poprzez rotacje zastosowane podczas powrotu do korzenia. Rotacje zachowują właściwość porządku drzewa binarnego na każdym kroku, więc drzewo pozostaje całkowicie prawidłowe i wyszukiwalne w trakcie całego procesu. Praktyczny efekt polega na tym, że drzewo stale zmienia swoje kształty tak, aby ulubieniec najbardziej ostatnio dostępnego elementu był przewyższony, co okazuje się wyjątkowo dobrym heurystycznym podejściem do rzeczywistych obciążen. Drzewa splay wprowadził Daniel Sleator i Robert Tarjan, a ich atrakcyja polega na tej prostej: kilku zasad rotacji, zastosowanych zgodnie, tworzy strukturę, która adaptuje się sama bez konieczności osobnego procesu odrozniania.

Przypadek Zig: Jedno Obrótowanie Blisko Korzenia

Najprostszym z trzech wzorcowych splayingów jest przypadek zig, a występuje on tylko raz na wszystkie splayingi. To zdarza się w bardzo końcu przebiegu operacji splayinga. Przypada, gdy węzeł splayed ma korzeń drzewa jako bezpośredniego rodzica, co oznacza, że nie ma uroczyska do rozważania. W tej sytuacji drzewo wykonuje jedno obrót: jeśli węzeł jest dzieckiem lewym, drzewo obraca się w prawo wokół rodzica; jeśli węzeł jest dzieckiem prawym, to obraca się w lewo wokół rodzica. Ta jedna operacja wymienia węzeł i jego rodzica, umieszczając węzeł na korzeniu, podczas gdy stary korzeń spada do stanu swojego dziecka, a poddrzewo, które wcześniej wisiało między nimi, jest ponownie przyłączane na odpowiednie miejsce, aby zachować kolejność. Ponieważ zig występuje tylko wtedy, gdy węzeł jest o krok od korzenia, to działa jako końcowy dotyk dłuższej sekwencji splayingów, która może już przewidzieć kilka kroku zig-zag lub zig-zig głębiej w drzewie. Niektóre operacje splayinga składają się tylko z jednego zigna, co występuje wtedy, gdy węzeł dostępnego przypadkiem był bezpośrednim dzieckiem korzenia. Nawet choć jest to najmniej dramatyczny z trzech przypadek, zign jest kluczowy dla poprawności, ponieważ bez niego węzeł na poziomie niższym od korzenia nie miałby sposobu na ukończenie swej podróży do góry.

Zig-Zig: Rotacje proste

Zig-zig obsługuje sytuację, gdy węzeł i jego rodzic lecą w tej samej kierunku, co oznacza, że oba są lewymi dziećmi swoich odpowiednich rodziców, lub oba są prawymi dziećmi. Zamiast obracać węzeł bezpośrednio wokół swojego rodzica, najpierw wykonuje się rotację rodzica wokół dziadka, a potem obraca węzeł wokół teraz przestawionego rodzica, z obu rotacjami wykonanymi w tym samym kierunku. Porządek wykonania tych rotacji ma duży znaczenie. Obracanie bardziej oddalonej pary przed bliższą pary daje drzewom splay dobrą długoterminową zachowanie, ponieważ tendencja jest do prawie podwójnego zmniejszenia głębokości węzłów na ścieżce dostępu zamiast proste przesunięcie problemu o jedno poziom, co nastąpiłoby, gdyby obracano w tej samej kierunku od góry do dołu. Wyobraź sobie długi łańcuch lewych dzieci rozciągniętych po lewej stronie drzewa: zig-zig splay przeprowadza się przez ten łańcuch dwoma poziomami naraz, z każdą parą rotacji zwiatająca część łańcucha i rozmieszczając pozostałe węzły w kształcie głębszym, ale gęstszym. Jest to główny przypadek dla węzłów głęboko wciętych, ponieważ większość rzeczywistych ścieżek dostępu nie jest stricte alternacją zig-zag, ale zawiera ciągi kroku w tym samym kierunku, a zig-zig jest to, co utrzymuje te ciągi od powstania najgorszych łańcuchów po wielokrotne operacje.

Przypadek Zaginiecie-Zaginiecie: Odwrotnie-Naprzeciwne Obracania

Przypadek zaginiecie-zaginiecie obejmuje pozostałą możliwość, w której węzeł i jego rodzic leżą w odwrotnej kierunkowości, np. gdy węzeł jest dzieckiem lewym, a jego rodzic prawym, lub na odwrót. W tej sytuacji drzewo nadal wykona dwa obracania, ale w przeciwne kierunki zamiast tych samych. Pierwsze obratanie przynosi węzeł dookoła swojego bezpośredniego rodzica, a drugie obratanie przynosi go następnie dookoła dziadka, co efektywnie podnosi węzeł o dwa poziomy, zaś rodzic i dziadek stają się jego dwoma dziećmi, jedno na lewo, a drugie na prawo. Wizualnie, to przypomina obracanie podwójne używane do naprawienia niezrównoważonego drzewa AVL, co powoduje podobny efekt zgarbiony: zamiast skręconej ścieżki schodkowej, zaginiecie-zaginiecie prosi localną strukturę tak, że poprzedni rodzic i dziadek węzła stają się jego bracia pod nim. Splayowanie węzła typowo obejmuje pracę przez kombinację par zaginiecie-zaginiecie i zaginiecie-zaginiecie, gdy ścieżka zagina sieje lub biegnie prosto na różnych etapach, z końcowym zaginieniem stosowanym tylko wtedy, gdy pozostanie jedna dodatkowa poziom po tym, jak węzeł dotrze do dziecka bezpośredniego korzenia. Spoleglone na razie te dwa przypadki obracania podwójnego pozwalają na spłaszczenie dowolnie długiej ścieżki dostępu do korzenia w jednym przebiegu poprzez operację splay.

Dlaczego to daje dobry amortyzowany wydajnościowy wynik

Operacja splay na nie szczęśliwym, źle zaszklowanym drzewie nadal może przejść długą ścieżkę przed tym, jak znajdzie swój cel, dlatego żaden pojedynczy dostęp nie jest gwarantowany jako szybki. To, co sprawia, że drzewa splay są wartościowe, to nie prędkość żadnej jednostkowej operacji, ale ich zachowanie w średnim po wielu operacjach. Ponieważ każdy dostęp przesuwa wierzchołek dotykanego do korzenia, węzeł, który jest odwiedzany powtórnie, staje się ekonomiczny do osiągnięcia prawie natychmiast po swoim pierwszym, ewentualnie drogim, odwiedzeniu. Serii operacji, które powtarzają się i dotykają takiej samej małej grupy ciepłych elementów, stają się znacznie szybsze w ciągu czasu, ponieważ te elementy clusterują się blisko korzenia drzewa, podczas gdy zimne elementy są spuszczane do dnia, gdzie rzadko przeszkadzają. Analiza matematyczna drzew splay pokazuje, że nawet jeśli izolowane operacje mogą być drogimi, całkowity koszt sumowany po dowolnej długiej serii operacji pozostaje proporcjonalny do tego, co by osiągnął równoważnie zaszklowany drzewo, więc przypadki drogocenne są efektywnie zapłacone przez wiele drobnych, które następują. To samoczynne dostosowywanie zachowania jest to, co sprawia, że drzewa splay naprawdę są użyteczne poza klasą. Niektóre implementacje buforów pamięciowego korzystają z struktur podobnych do drzew splay, ponieważ najnowsze i często odwiedzane wpisy naturalnie wznoszą się na miejsce, gdzie mogą być znalezieni jak najszybciej. Niektóre routerzy sieciowe używali ich do zarządzania informacjami o routingu, gdzie podzbior destynacji dominuje ruchem. Algorytmy kompresji danych, w tym niektóre schematy kodowania adaptacyjnych, również korzystają z tej samej idei, ponieważ korzystają one z ekonomicznej powtarzalnej dostępu do symboli występujących często we wpływie.

Często zadawane pytania

Wypróbuj na żywo

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