Splay tree z nieparzystą liczbą obrotów

Podczas wstawiania przedmiotu do drzewa rzutów obroty wykonuje się parami w oparciu o wzór zygzakowaty lub zygzakowaty. Gdy do wykonania jest nieparzysta liczba obrotów, można wykonać dodatkowy obrót, zaczynając od liścia, lub zapisać dodatkowy obrót i zrobić to u podstawy. Czy to ma znaczenie?

Na przykład na załączonym obrazie wstawiam 4 do BST i „splay” to do rdzenia. Na górze rysunku najpierw lokalizuję parę zygzakowatą w węźle liścia i wykonuję zygzakowatą rozpad od dołu, pozostawiając końcowy prawy obrót u podstawy. W dolnej części figury najpierw wykonuję dziwny obrót, zaczynając od liścia, a następnie wykonuję rzut zygzakowy do korzenia.

Który jest poprawny? A może oba doprowadzą do zwykłego działania drzewa splay?

To naprawdę nie ma znaczenia dla analizy. Kluczowym lematem do analizy wydajności drzewa splay jest lemat dostępu . Stwierdza, że ​​zamortyzowane koszty operacji splay (x) są mniejsze niż$1+3(r(t)-r(x))$, gdzie $t$ jest korzeniem drzewa i $r(u):=\lfloor \log (\text{weight of $u$'s subtree}) \rfloor$. Waga poddrzewa jest sumą wag jego węzłów. (Wagi (dodatnie) będą wybierane w zależności od zastosowania lematu). Zastosowana potencjalna funkcja to$\Phi(T)=\sum_{x \text{ node of } T} r(t)$.

Dowód lematu dostępu dotyczy kosztów pojedynczej operacji zig / zig-zag / zig-zig itp. Dostajesz

1. Koszty operacji zygzakiem lub zag wynoszą $1+3(r_+(u) - r(u))$, gdzie $r_+$ dzwonił po operacji i $u$ jest węzłem obróconym do góry.

2. Koszty operacji zig-zig / zig-zag i symetrycznych wynoszą $3(r_+(u) - r(u))$.

Jeśli dodasz te różnice do operacji wykonanych w pojedynczej grze (x) , otrzymasz sumę teleskopu, a to, co pozostanie, to$1+3(r(t)-r(x))$.

Jeśli zmienisz kolejność obrotów, otrzymasz tę samą sumę. Jedyną różnicą jest to, że teraz „+1” pochodzi z pierwszego obrotu, a nie z ostatniego obrotu. Możesz nawet wykonać obrót zygzaka na środku. Wszystkie dalsze (klasyczne) analizy opierają się na lemacie dostępu.

Powodem, dla którego wykonujesz pojedynczy obrót jako ostatni, jest to, że nie wiesz, czy głębokość węzła jest z góry parzysta czy nieparzysta.