\documentclass[a4paper,polish]{scrartcl}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{babel}
\usepackage[a4paper]{geometry}
\usepackage{polski}
%\usepackage[cm]{fullpage}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{algorithmicx}
\usepackage{algpseudocode}


\author{Rafał Sławik}
\title{Finger search tree}
\subtitle{Notatka do wykładu}
\date{11 grudnia 2012}

\newtheorem{lemma}{Lemat}

\begin{document}

\maketitle

\tableofcontents

\section{Wstęp}
Bardzo często spotykanym w informatyce problemem jest zarządzanie uporządkowanym zbiorem elementów,
w taki sposób, aby umożliwić \textit{szybkie} sprawdzanie czy dany element $e$ należy do tego zbioru.
Problem możemy rozważać w dwóch wersjach:
\begin{itemize}
 \item statycznej, gdzie zbiór elementów jest ustalony,
 \item dynamicznej, gdzie pozwalamy na operacja dodawania i usuwania elementów ze zbioru.
\end{itemize}

W przypadku statycznym możemy umieścić elementy w kolejności w tablicy i zastosować wyszukiwanie binarne
do sprawdzania czy element $e$ należy do zbioru. Z kolei dla wersji dynamicznej możemy skorzystać
z drzew BST. W obu tych przypadkach zużyjemy liniowo dużo pamięci na przechowanie zbioru, a czas
wyszukiwania będzie logarytmiczny względem liczby elementów.

Czasem taka złożoność wyszukiwania jest niewystarczająca i potrzebujemy wydajniejszej struktury danych. Taką 
strukturą są na przykład \textbf{finger search trees}, które rozważamy tutaj.

\subsection{Finger - wskaźnik, czas $O(\log d)$}
Dodajemy do struktury wskaźniki (ang. fingers), które umożliwią nam \textit{szybkie} uaktualnienia i
wyszukiwanie w ich pobliżu. O ich liczbie i rozmieszczeniu decyduje osoba korzystająca ze struktury.
Na niej także spoczywa obowiązek zapewnienia, że wstawianie nowej wartości odbywa się we właściwym
miejscu.

Zastosowanie fingerów pozwala na zredukowanie czasu wyszukiwania z $O(\log n)$, gdzie $n$ oznacza liczbę
wszystkich elementów w zbiorze, do $O(\log d)$, gdzie $d$ jest odległością pomiędzy fingerem $f$ (od
którego rozpoczynamy szukanie) i poszukiwanym elementem $e$.

Jakie korzyści daje użycie FST można przeczytać w części~\ref{sec:zastosowania}.

\subsection{Idea finger search}
Cała idea finger search sprowadza się do tego, że chcemy uniknąć przeszukiwania całej struktury. Dzięki temu,
że dysponujemy fingerem, który potencjalnie znajduje się blisko elementu, którego szukamy, możemy wyszukiwanie
wykonać \textit{lokalnie}. Patrząc na rysunki struktur, możemy dostrzec jak \textit{naturalny} dla człowieka
jest to proces.

\subsubsection{Na tablicy}
\label{sec:wyszukiwanie_wykladnicze}
Spójrzmy jak można zastosować ten pomysł do zbioru przechowywanego w tablicy (rysunek~\ref{fig:wyszukiwanie_wykladnicze}).
\begin{figure}
\caption{Wyszukiwanie wykładnicze na tablicy (rysunek z \cite{B05})}
\label{fig:wyszukiwanie_wykladnicze}
\resizebox{\textwidth}{!}{
\includegraphics{ArrayFingerSearch}
}
\end{figure}
Wykorzystujemy wyszukiwanie wykładnicze. Badamy kolejne przedziały o długościach $2^i-1$ dla rosnących
wartości $i$. Gdy znajdziemy już przedział, do którego należy szukany element, wykonujemy na nim poszukiwanie
binarne. Osiągamy w ten sposób czas $O(\log d)$, ponieważ z każdym kolejnym skokiem pomijamy wykładniczo wiele
elementów (argument taki sam jak w \ref{sec:struktura_gora_szukanie}).

\subsubsection{Na drzewie}
W przypadku drzew proces wyszukiwania wygląda następująco (rysunek \ref{fig:wyszukiwanie_drzewo}).
\begin{figure}
\caption{Finger search na drzewie (rysunek ze strony http://leda-tutorial.org)}
\label{fig:wyszukiwanie_drzewo}
\resizebox{\textwidth}{!}{
\includegraphics{FingerSearch}
}
\end{figure}
Niebieskie strzałki pokazują jaką drogę przebywami wykonując finger search, czarne drogę przebytą w czasie
zwykłego wyszukiwania. W części \ref{sec:struktura_gora_szukanie} pokażemy, że droga złożona z niebieskich 
strzałek ma długość $O(\log d)$.

\subsection{Operacje na FST}
Na omawianej strukturze wykonywać będziemy następujemy operacje:
\begin{itemize}
\item \texttt{Search}(f, x)
\item \texttt{Insert}(f, x)
\item \texttt{Delete}(f, x)
\end{itemize}
Oczekujemy, aby każda z nich zajmowała w pesymistycznym przypadku $O(\log d)$. Operacje \texttt{Insert} i
\texttt{Delete} możemy podzielić na dwie części:
\begin{enumerate}
\item wyszukiwanie miejsca, w którym należy wstawić/usunąć element - $O(\log d)$,
\item dokonanie zmiany - $O(1)$.
\end{enumerate}


\section{Historia}
W tablicy \ref{tab:historia} przedstawiona jest skrócona historia FST. (\textit{Uwaga: czasy podane przy
operacjach uaktualnienia są podane przy założeniu, że miejsce zmiany jest już ustalone}).

Poza wymienionymi pracami należy wspomnieć także o \textit{(2,4)-linked tree} (patrz:
część \ref{sec:struktura_gora}), które umożliwia uaktualnienia w czasie stałym (zamortyzowanym) i
wyszukiwanie w czasie $O(\log d)$. Struktura ta jest używana w praktyce.


\begin{table}
\resizebox{\textwidth}{!}{
\begin{tabular}{l | c | c | c | l}
Struktura & \texttt{Insert} & \texttt{Delete} & \texttt{Search} & Uwagi \\
\hline
`97 Guibas & $O(1)$ & $O(1)$ & $O(\log d)$ & B-drzewo, stała liczba wskaźników \\
`88 Levocopolous, Overmars & $O(1)$ & $O(1)$ & $O(\log n)$ & Dowolna liczba wskaźników \\
`79 Harel, `96 Fleisher, `03 Brodal & $O(1)$ & $O(\log^* n)$ & $O(\log d)$ & Dowolna liczba wskaźników \\
`03 Brodal i in. & $O(1)$ & $O(1)$ & $O(\log d)$ & ,,Optimal finger search trees in the pointer machine'' \\
`94 Dietz, Raman & $O(1)$ & $O(1)$ & $O(\log d)$ & \\
`00 Anderson, Thorup &  $O(1)$ & $O(1)$ & $O\left( \sqrt{\frac{\log d}{\log \log d}} \right)$ & \\
\end{tabular}
}
\caption{Historia}
\label{tab:historia}
\end{table}

\section{Struktura}

\subsection{Model}
Modelem, w którym rozważamy strukturę, jest \textbf{model maszyny RAM}. Zakładamy tutaj, że mamy do dyspozycji
słowa maszynowe długości $\omega = c \log_2 M$, gdzie wartość $M$ oznacza maksymalny rozmiar struktury. Cała
struktura musi zmieścić się w pamięci, więc słowa muszą umożliwiać jej adresowanie. Zakładamy również, że
wszystkie operacje na słowach wykonywane są w czasie stałym.

\subsection{Idea}
Struktura składa się z dwóch części:
\begin{itemize}
\item struktury na górnym poziomie - drzewa,
\item kubełków, których reprezentanci są przechowywani w strukturze na górnym poziomie.
\end{itemize}
Mamy pewną dowolność przy wyborze sposobu przechowywania elementów w kubełku, jak również przy wyborze rodzaju
drzewa. Drzewa umożliwiają uaktualnienia w czasie logarytmicznym, dlatego tutaj będziemy je realizować 
\textit{przyrostowo}, to znaczy przy każdej operacji na strukturze wykonamy pewną stałą ilość kroków
procesu naprawiania struktury na górnym poziomie. Pokażemy, że konieczność takich uaktualnień jest na tyle
rzadka, że jesteśmy w stanie taki proces pomyślnie wykonać.

Opisujemy tu strukturę zaproponowaną przez Dietza i Ramana w \cite{DR89}. Jest to poprawiona wersja struktury
z pracy \cite{LO88}. Wyeliminowana została konieczność \textit{globalnego przebudowania}, gdy liczba elementów
w strukturze sięgała granicznym wartościom. Wymagało ono uruchomienia działacego przryostowo procesu, który
przebudowywał strukturę dla większej/mniejszej liczby elementów. Po przekroczeniu granicznej wartości struktura była zastępowana przygotowaną kopią.

\subsection{Kubełki}
Kubełki będą miały rozmiar $O(\log^2 n)$. \\
Oznaczmy przez $\hat{n}$ maksymalną liczbę elementów w strukturze
do tej pory. Do opisu kubełków definiujemy dodatkowo następuję wartości:
\begin{equation}
\phi(b) = \frac{\text{size}(b)}{\log^2 \hat{n}}
\label{eqn:zapelnienie}
\end{equation}
\begin{equation}
\rho(b, \hat{n}) = \frac{1}{\log^2 \hat{n}} \max \left(0, 0.7 \log^2 \hat{n} - \text{size}(b),
\text{size}(b) - 1.8 \log^2 \hat{n} \right)
\label{eqn:krytycznosc}
\end{equation}
Wartość \ref{eqn:zapelnienie} nazywać będziemy zapełnieniem kubełka, a wartość \ref{eqn:krytycznosc}
krytycznością. Gdy krytyczność danego kubełka będzie większa od $0$ powiemy, że ten kubełek jest krytyczny.

Będziemy dbać, aby $0.5 \le \phi(b) \le 2$. Oznacza to, że kubełek może maksymalnie podwoić swoją wielkość
albo dwukrotnie ją zmniejszyć. Gdy krytyczność kubełka będzie wysoka, będziemy wykonywać na nim operację
\texttt{Split}, \texttt{Merge}, \texttt{Transfer}. Z kolei na podstawie lematu mamy gwarancję, że zdarzenia te
będą na tyle rzadkie, że proces przyrostowego wstawiania/usuwania reprezentanta w górnej strukturze zdąży
zakończyć swoją pracę nim pojawi się konieczność następnej aktualizacji.

\subsubsection{Lemat o zapełnieniu kubełków}
Poniższy lemat gwarantuje, że krytyczność kubełki nigdy nie będzie za duża. Lemat pochodzi z \cite{DS87}.
\begin{lemma}
Niech $x_1, x_2, \dots, x_n$ będą liczbami rzeczywistymi (wszystkie początkowo równe 0). \\
Powtarzamy następujące czynności:
\begin{enumerate}
\item wybierz $x_i$, takie że $x_i = \max_j{x_j}$
\item ustaw $x_i$ na 0
\item wybierz $n$ nieujemnych liczb $a_1, a_2, \dots, a_n$, takich że $\sum_{j=1}^n a_j = 1$
\item ustaw $x_j$ na $x_j + a_j$ (dla każdego $j$).
\end{enumerate}
Wtedy każdy $x_k$ jest zawsze mniejszy niż $H_{n-1} + 1$ ($H_k$ oznacza $k$-tą liczbę harmoniczną).
\end{lemma}

\begin{proof}
\textbf{Obserwacja}: W każdym momencie  suma wszystkich $x_j$ jest nie większa niż $n$:
$S = \sum_{j=1}^n x_j \le n$. Jest to prawdą na samym początku, gdy wszystki $x_j = 0$.
W czasie jednej iteracji procesu opisanego w lemacie wartość $S$ wzrasta do $\frac{n-1}{n} S + 1$.
Składnik $\frac{n-1}{n} S$ wynika z tego, że chcemy, aby po wykonaniu iteracji suma pozostała jak największa,
dlatego rozkładamy \textit{masę} po równo na wszystkich $x_j$ (wtedy usunięcie maksimum usuwa najmniej).
Z kolei $1$ to suma dodanych w tej iteracji $a_j$. Z założenia indukcyjnego $S \le n$, zatem
$\frac{n-1}{n} S + 1 \le \frac{n-1}{n} n + 1 = n$.

Definiujemy ciąg wektorów $x^{(1)}, x^{(2)}, \dots, x^{(m)}$, opisujących stany wartości $x_j$ po kolejnych
iteracjach. Bez straty ogólności zakładamy, że $m \ge n$. Takie założenie jest dopuszczalne, ponieważ możemy dołożyć dowolnie dużo wektorów zerowych na początku ciągu. Zerowe wektory oznaczają iteracje, w których tylko
jedno $a_j$ było równe $1$.
Wybierzmy również ciąg permutacji $\pi_1, \pi_2, \dots, \pi_n$. Będą to permutacje liczb $1, 2, \dots, n$
mające następującą własność:
\begin{equation*}
x_{\pi_k(i)}^{(m - k + 1)} \ge x_{\pi_k(i+1)}^{(m - k + 1)}
\end{equation*}
Permutacja $\pi_k$ mówi jaka jest kolejność kubełków w porządku malejącym w $(m-k+1)$-tej (czyli $k$-tej od
końca) iteracji. Zdefiniujmy wartość:
\begin{equation*}
S_k = \sum_{j=1}^k x_{\pi_k(j)}^{(m-k+1)}
\end{equation*}
oznaczającą sumę $k$ największych elementów w $k$-tej od końca iteracji. $S_1$ to najcięży element w ostatniej
iteracji. Podobnie jak w obserwacji, zauważamy, że $S_k \le \frac{k}{k+1} S_{k+1} + 1$. Wystarczy w $k+1$-szej
od końca iteracji rozłożyć \textit{masę} pomiędzy $k+1$ najciężych elementów. Stąd wynika, że:
\begin{align*}
S_1 \le \frac{1}{2} S_2 + 1 \le \frac{1}{2} \left( \frac{2}{3} S_3 + 1 \right) + 1 =
\frac{1}{3} S_3 + \frac{1}{2} + 1 & \le \dots \le \frac{1}{k} S_k + H_{k-1} \le \\
& \le \dots \le \frac{1}{n} S_n + H_{n-1} \le 1 + H_{n-1}
\end{align*}
Ostatnia nierówność wynika z obserwacji. Natomiast z dowolności wyboru $m$ wynika teza lematu.
\end{proof}

\paragraph{Interpretacja i wykorzystanie lematu}
Zastosowanie lematu w naszym przypadku wymaga odniesienia opisanego w nim procesu do akcji na kubełkach.
Wartości $x_1, x_2, \dots, x_n$ oznaczają przeskalowane \textit{krytyczności} kubełków. Wybór maksimum i jego
wyzerowanie to podzielenie (połaczenie) najbardziej krytycznego kubełka - ten który był krytyczny przestaje 
nim być, a także te których ta akcja dotyczyła (powstały dwa nowe kubełki) nie staną się krytyczne. Ustawienie 
któregoś $a_j$ na $1$ oznacza, zwiększenie krytyczności w $j$-tym kubełku.

My jednak akcję dzielienia najbardziej krytycznego kubełka (usuwania maksimum) wykonujemy co
$k = c \log \hat{n}$ kroków. Więc możemy sobie wyobrazić, że zamiast dodawać $\sum a_i = 1$, gdzie rozmiar
każdego kubełka moglibyśmy ograniczyć przez $H_{n-1} + 1 = O(\log \hat{n})$, możemy dodawać $k$ razy więcej i w 
konsekwencji dostać $k$ razy większe ograniczenie końcowe, które wynosi $O(\log^2 \hat{n})$.

\subsubsection{Zarządanie kubełkami}
Kubełkami będziemy zarządzać w następujący sposób. Co $O(\log \hat{n})$ operacji na strukturze wybierzemy
najbardziej krytyczny kubełek $b$ i wykonamy na nim jedną z operacji:
\begin{itemize}
 \item \texttt{Split}, gdy $\phi(b) > 1,8$. Dzielimy kubełek na dwa podobnej wielkości i dodejmy nowego
 reprezentanta,
 \item \texttt{Transfer}, gdy $\phi(b) < 0,7$ oraz sąsiad $b'$ ma $\phi(b') > 1$. Wyrównujemy wielkości
 kubełków $b$ i $b'$,
 \item \texttt{Fuse}, gdy $\phi(b) < 0,7$ i transfer nie jest możliwy. Usuwamy kubełek $b$, a elementy z
 niego przenosimy do sąsiada $b'$.
\end{itemize}
Na krytycznośc kubełków mają wpływ uaktualnie na strukturze. Jeśli nie zmieniają wartości $\hat{n}$, to
do zapewnienia właściwej wielkości kubełków wystarczy lemat. Natomiast w przypadku wzrostu $\hat{n}$
potrzebne jest dodatkowe oszacowanie.

Popatrzmy o ile wzrasta krytyczność jednego kubełka przy wzroście $\hat{n}$ o $1$. Niech $\delta_b$ oznacza
przyrost w kubełku $b$.
\begin{equation}
\delta_b \le \frac{d \rho(b, \hat{n})}{d \hat{n}} \le \frac{c}{\hat{n}}
\end{equation}
gdzie $c$ jest pewną stałą. Cały przyrost wyraża się wzorem:
\begin{equation}
\sum_{b\text{ - kubełek}} \delta_b \le \sum_{b\text{ - kubełek}} \frac{c}{\hat{n}} =
\frac{\hat{n}}{\log^2 \hat{n}} \cdot \frac{c}{\hat{n}} = O\left( \frac{1}{\log^2 \hat{n}}\right)
\end{equation}
Pomiędzy przebalansowaniami wartość $\hat{n}$ może wzrosnąć co najwyżej $O(\log \hat{n})$ razy. Zatem
całkowity przyrost wyniesie co najwyżej $O(\log^{-1} \hat{n})$. Stosując lemat, widzimy, że górne
ograniczenie na krytyczność dowolnego kubełka to $k H_{\hat{n}-1} + O(1)$, a to pozwala na dobranie
odpowiedniej (stałej) liczby operacji procesu przyrostowego uaktualniania wykonywanych przy każdej operacji na
strukturze.

\subsubsection{Struktura wewnętrzna}
Każdy kubełek reprezentujemy jako drzewo o wysokości $3$ o współczynniku rozgałęzienia $\beta = 
\theta(\log^{2/3} \hat{n})$. Przy uaktualnieniach będziemy dbać, aby ten współczynnik znajdował się
pomiędzy $\beta / 2$ a $2 \beta$. W tym celu zezwalamy na to, aby wierzchołki mogły posiadać dodatkowy
wierzchołek (tak jak na rysunku \ref{fig:dodatkowy_wierzcholek}). Reguły balansowania są dokładniej opisane w
oryginalnej pracy \cite{DR89} - tutaj podamy wyłącznie krótki ich opis.

Przy dodawaniu elementu, gdy $r$ ma
więcej niż $2 \beta$ dzieci, tworzony jest dodatkowy wierzchołek $s$ podłączony wyłącznie do $r$ (nie do $p$).
Z kolei przy usuwaniu, gdy mamy mniej niż $\beta / 2$ dzieci, próbujemy zabrać dzieci sąsiadowi, a jeśli jest
to niemożliwe to sami podczepiamy się jako dodatkowy wierzchołek. Balansowanie ma na celu zachowanienie 
odpowiedniego współczynika rozgałęzienia $\beta$ oraz nierówności $\text{nchild}(s) \le \text{nchild}(r)$, 
która mówi, że $r$ ma więcej dzieci niż $s$. 

\begin{figure}
\caption{Dodatkowy wierzchołek $s$ w drzewie reprezentującym kubełek}
\label{fig:dodatkowy_wierzcholek}
\center{
\includegraphics{ExtraVertex}
}
\end{figure}

Konieczne są dodatkowe operacje, aby nierówności pozostawały spełnione. Operacje na kubełku mogą zaburzyć te
nierówności o $O(1)$, o ile nie zmieniają wartości $\hat{n}$. Z kolei zmiana $\hat{n}$ może spowodować 
zaburzenia we wszystkich kubełkach. Aby je naprawić, uruchomiamy proces, który będzie \textit{inkrementacyjnie}
przesuwać wierzchołki z $s$ do $r$ lub na odwrót. Naprawa pojedynczego węzła to koszt stały. Nim proces powróci 
do danego wierzchołka to wartość $\hat{n}$ może zmienić się maksymalnie o czynnik $1 + o(1)$ (wynika to z tego, 
że $\log^{2/3}(2 \hat{n}) - \log^{2/3} \hat{n} < c$, ponieważ $\lim_{\hat{n} \to \infty } \log^{2/3}(2 \hat{n}) - 
\log^{2/3} \hat{n} = 0$).

Ponadto każdy wewnętrzny wierzchołek drzewa przechowuje zbiór $S$ maksymalnych elementów swoich poddrzew za
pomocą:
\begin{itemize}
\item tablicy $A[1..k]$ przechowująca wskaźniki na elementy
\item tablicy $Perm[1..k]$ reprezentująca permutację elementów z $A$
\begin{equation*}
\text{Perm}[i] =
\begin{cases}
0 & A[i] = null \\
|\{\text{key}(A[j]) : j \le i \wedge \text{key}(A[j]) \le \text{key}(A[i])\}| & \text{wpp.}
\end{cases}
\end{equation*}
\item podwójnie wiązanej listy $L$, na której będą w istocie przechowywane elementy (ponadto każdy element wie 
jaki jest jego
indeks w tablicy $A$)
\end{itemize}
Na zbiorze $S$ będziemy wykonywać operacje wstawiania i usuwania. Chcemy, aby każda z nich działała w czasie
stałym. Poniżej znajduje się opis ich realizacji.

\begin{itemize}
\item \texttt{Insert} - dodawanie elemenentu do zbioru maksimów wygląda w następujący sposób:
\begin{enumerate}
\item Ustalamy $j$, takie że $A[j]$ wskazuje na klucz, za którym będzie wstawiony nowy element,
\item Dołączamy element do listy,
\item Ustawiamy $A[|S|+1]$, żeby wskazywało na ten element,
\item Uaktualniamy $Perm$
\end{enumerate}
\item \texttt{Delete} - usuwanie elementu ze zbioru maksimów:
\begin{enumerate}
\item Ustalamy $j$, takie że $A[j]$ wskazuje na klucz do usunięcia,
\item Zamieniamy $A[j]$ z $A[|S|]$,
\item Ustawiamy $A[|S|]$ na $null$,
\item Usuwamy element z listy,
\item Poprawiamy element wskazywany przez $A[j]$, żeby wskazywał na $j$ (bo aktualnie wzkazuje na $|S|$),
\item Uaktualniamy $Perm$
\end{enumerate}
\end{itemize}

Wstawianie i usuwanie bardzo łatwo zrealizować w czasie $O(|S|)$. My chcemy jednak przyspieszyć te operacje.
Zauważamy, że do zapisania w pamięci tablicy $Perm$ potrzebujemy $|S| \cdot \lceil \log |S| \rceil$ bitów
(ponieważ w $Perm$ znajdują się liczby z $\{0, \dots, |S|\}$, a do zapisu każdej z nich wystarczy nam 
$\log |S|$ bitów).

Pokażemy, że ta potrafimy $Perm$ trzymać w pojedynczym słowie maszynowym. Maksymalny rozmiar zbioru maksimów
$S$ to $2 \log^{2/3} \hat{n}$. Oczywiście $\hat{n}$ nie przekroczy maksymalnego rozmiaru struktury $M$.
Zatem $|S| \le 2 \log^{2/3} \hat{n} \le 2 \log^{2/3} \hat{M}$. Udowodnimy najpierw nierówność $|S|
\le \frac{\log M}{\log \log M}$.
\begin{equation}
\label{eqn:rozmiarS}
|S| \le 2 \log^{2/3} M \le \frac{\log M}{\log \log M}
\end{equation}
\begin{equation*}
2 \log \log M \le \log^{1/3} M = \sqrt[3]{\log M}
\end{equation*}
Dla odpowiednio dużych wartości $M$ ta nierówność zachodzi. Intuicyjnie funkcja $\sqrt[3]{\cdot}$ rośnie
szybciej niż $\log$. Pokażemy teraz, korzystając z nierówności \ref{eqn:rozmiarS}, że $|S| \cdot \lceil \log 
|S| \rceil \le \log M$.
\begin{equation}
|S| \cdot \lceil \log |S| \rceil \le
\frac{\log M}{\log \log M} \cdot \log \frac{\log M}{\log \log M} =
\frac{\log M}{\log \log M} \cdot \left( \log \log M - \log^{(3)} M \right)
\le \log M
\end{equation}

Dzięki temu możemy wykorzystać kilka funkcji pomocniczych i stablicować ich wyniki, a w czasie operacji na
strukturze jedynie pobierać z tablicy ich wynik.
\begin{itemize}
\item \texttt{GetRank}($Perm, i$) - zwraca pozycję ma element $i$-ty w zbiorze $S$ w porządku rosnącym,
\item \texttt{GetIndex}($Perm, i$) - zwraca indeks w tablicy $A$ elementy, który znajduje się na
$i$-tej pozycji w zbiorze $S$ w porządku rosnącym,
\item \texttt{UpdatePerm}($Perm, rank, operation$) - uaktualnia tablicę $Perm$, $operation$ mówi
czy dodajemy, czy usuwamy element, a $rank$ wskazuje ten element
\end{itemize}

Należy jeszcze sprawdzić czy te tablice nie zajmą za dużo miejsca. Przykładowo dla funkcji \texttt{UpdatePerm}
możliwych różnych wartości argumentów jest $2 |S| \cdot 2^{|S| \lceil \log |S| \rceil}$. Pokażemy teraz, że
jest to $O(M)$. Korzystamy z udowodnionej nierówności \ref{eqn:rozmiarS}, która ogranicza rozmiar $S$. Najpierw
przekształcamy $2 |S| \cdot 2^{|S| \lceil \log |S| \rceil}$ do postaci $2 |S|^{|S|+1}$. Dowodzimy nierówności
w notacji $O$, dlatego możemy pominąć stałą $2$. Ostatecznie pokazywać będziemy, że dla $c \le 1$ zachodzi:
\begin{align*}
|S|^{|S|+1} & = M^c \\
(|S| + 1) \log |S| & = c \cdot \log M
\end{align*}
Druga równość powstaje w wyniki zlogarytmowania pierwszej. Po wstawieniu oszacowania \ref{eqn:rozmiarS} mamy:
\begin{equation}
\left( \frac{\log M}{\log \log M} + 1 \right) \cdot ( \log \log M - \log^{(3)} M) = 
\log M + \left[ \log \log M - \log^{(3)} M \cdot \left( \frac{\log M}{\log \log M} + 1 \right) \right]
\end{equation}
Wystarczy teraz pokazać, że składnik w nawiasie kwadratowym jest ujemny. Wprowadźmy najpierw oznaczenie
$x = \log \log M$, wtedy to co chcemy udowonić przedstawia się następująco:
\begin{align*}
x & \le \log x \left( \frac{2^x}{x} + 1 \right) \\
x^2 & \le \log x (2^x + x)
\end{align*}
Tutaj również intuicyjnie widać, że nierówność zachodzi, ponieważ funkcja wykładnicza rośnie dużo szybciej niż
kwadratowa.

Zatem możliwe jest przygotowanie tablic wyników dla funkcji pomocniczych.

\subsubsection{Wyszukiwanie}
Wyszukiwanie wewnątrz kubełka rozpoczynamy od znalezienia LCA finger $f$ i szukanego klucza $s$. Jako, że drzewo
ma wysokość równą 3, możemy to zrobić w czasie stałym. Dalej szukamy odpowiedniego węzła w dół. Bez utraty
ogólności załóżmy, że LCA $f$ i $s$ jest najwyższym wierzchołkiem (korzeniem). Oznaczmy przez $d_1$, $d_2$, $d_3$,
w którym poddrzewie znajduje się $s$, odpowiednio pierwszego, drugiego i trzeciego wierzchołka na ścieżce od
korzenia do $s$. Przy tych oznaczeniach odległość $d$ między $f$ a $s$ wyraża się
$d = d_3 + d_2 \log^{2/3} \hat{n} + d_1 \log^{4/3} \hat{n}$. Asymptotycznie największym składnikiem
(względem $\hat{n}$) jest $d_1 \log^{4/3} \hat{n}$. Znalezienie odpowiedniego poddrzewa w wierzchołku zajmuje
czas $\log d_i$, wykonujemy w tym celu wyszukiwanie wykładnicze (patrz: \ref{sec:wyszukiwanie_wykladnicze})
na tablicy $A$, wykorzystując funkcję \texttt{GetIndex}. W sumie koszt wyszukania to $O(\log d_1) + O(\log d_2) +
O(\log d_3) = O(\log d_1 d_2 d_3) \le O(\log (d_1 \log^{4/3} \hat{n}))$, czyli $O(\log d)$.

\subsection{Struktura na górnym poziomie}
\label{sec:struktura_gora}
W zakresie wyboru struktury na górnym poziomie mamy dowolność, o ile zagwarantujemy, że uaktualnienia w niej
będą wykonywane w czasie $O(\log n)$.

W tej notatce wybieramy \textit{(2,4)-drzewo}. Charakteryzuje się ono tym, że wszystkie liście znajdują się na
tej samej głębokości. Każdy wierzchołek wewnętrzny jest stopnia 2, 3 lub 4. Klucze przechowywane są w liściach,
a węzły wewnętrzne zawierają informację ułatwiająca wyszukiwanie. Przykładowe dzewo znajduje się na rysunku
\ref{fig:24drzewo}. Warto tu zauważyć, że (2,4)-drzewa to \textit{prawie} to samo, co B-drzewa rzędu 4. Dokładny
opis operacji na (2,4)-drzewach można znaleźć w wielu źródłach (np. w \cite{24drzewo_wiki}), więc zostanie tu 
pominięty.

\begin{figure}
\caption{Przykładowe (2,4)-drzewo z połączeniami między węzłami na tym samym poziomie}
\label{fig:24drzewo}
\resizebox{\textwidth}{!}{
\includegraphics{24tree}
}
\end{figure}

Dodatkowo łączymy węzły na tym samym poziomie między sobą. Wykorzystujemy do tego listę dwukierunkową. Na rysunku
\ref{fig:24drzewo} te połączenia są zaznaczone liniami przerywanymi. Ich zastosowanie pozwala na wyszukiwanie w
czasie $O(\log d)$, a ich aktualizacja nie zwiększa czasu uaktualnienień w drzewie.

\subsubsection{Wyszukiwanie}
\label{sec:struktura_gora_szukanie}
Do opisu wyszukiwania wykorzystamy rysunek \ref{fig:24drzewo}. Załóżmy, że mamy finger w miejscu $x$ oraz szukamy
elementu $y$.

Wyszkiwanie rozpoczynamy od ustalenia czy poszukiwany element $y$ jest większy od $x$. Bez straty ogólności
zakładamy, że tak, więc będziemy poszukiwać go w prawo. Następnie idziemy od $x$ w stronę korzenia drzewa,
aż ustalimy, że $y$ znajduje się w poddrzewie aktualnie rozpatrywanego węzła $v$ lub jego prawym sąsiedzie $v'$.
Wtedy rozpoczynamy poszukiwanie w dół zarówno od wierzchołka $v$ jak i $v'$.

Pokażemy teraz, że czas wyszukiwania to $O(\log d)$. Zauważamy, że robiąc krok w górę, pomijamy wykładniczo dużo 
elementów. Wynika to z tego, że każdy węzeł wewnętrzny ma co najmniej dwóch synów, a liście są na tym samym 
poziomie. Tak więc element o wysokości $h$ ma $2^{h-1}$ kluczy pod sobą. Idąc w górę, dodajemy do siebie kolejne 
potęgi dwójki. Wiemy, że robiąc $k$ kroków do górym pominiemy $\sum_{i=1}^k 2^{i-1} = 2^k - 1$, zatem skoro 
odległość pomiędzy $x$ a $y$ wynosiła $d$, to $k = O(\log d)$. Całe wyszukiwanie trwa więc $O(k) = O(\log d)$.

\section{Zastosowania}
\label{sec:zastosowania}
FST mają swoje stasowowanie między innymi w:
\begin{itemize}
\item operacjach na zbiorach
\item geometrii obliczeniowej:
 \begin{itemize}
  \item Three-dimensional layers of maxima
  \item Triangulating a simple polygon
 \end{itemize}
\item algorytmach tekstowych:
 \begin{itemize}
  \item Finding repeats with gaps
  \item Quasiperiodicities in strings
 \end{itemize}
\end{itemize}
Zwykle używając finger search tree możemy zaoszczędzić czynnik $O(\log n)$ w porównaniu z drzewami BST.

\subsection{Łączenie zbiorów}
Niech $X$, $Y$ - zbiory, $|X| = n$, $|Y| = m$. Bez utraty ogólności $n \le m$. Rozważmy prosty algorytm:
\begin{center}
\begin{algorithmic}
\For {$x \in X$}
\State $Y \gets Y \cup \{x\}$
\EndFor
\end{algorithmic}
\end{center}

W przypadku przechowywania zbiorów $X$ i $Y$ za pomocą BST złożoność tego algorytmu wynosi $O(n \log m)$,
$n$ wstawień kosztujących po $\log m$.

Korzystając z FST, możemy przesuwać finger monotonicznie. Wtedy złożoność wyniesie $\sum_{i=1}^n O(\log d_i)$.
Kolejne wartości $d_i$ oznaczają o ile przesuwa się finger przy wstawianiu $i$-tego elementu, oczywiście
$\sum_{i=1}^n = m$.
\begin{equation*}
\sum_{i=1}^n O(\log d_i) = O \left( \sum_{i=1}^n \log d_i \right) \le O \left( n \log \frac{m}{n} \right)
\end{equation*}
Oszacowanie to wynika wprost z nierówności Jensena zastosowanej dla logarytmu, który jest funkcją wklęsłą.

\begin{thebibliography}{99} 
\bibitem{DR89} P. Dietz, R. Raman, \textit{A constant update time finger search tree}, 1989.
\bibitem{LO88} C. Levcopolous, M. Overmars, \textit{A balanced search tree with O(1) worst-case update time}, 1988.
\bibitem{DS87} P. Dietz, D. Sleator, \textit{Two algorithms for maintaining order in a list}, 1987.
\bibitem{B05} G. Brodal, \textit{Finger search trees}, 2005
\bibitem{24drzewo_wiki} Wikipedia, \textit{2-3-4 tree},
 \texttt{http://en.wikipedia.org/wiki/2\%E2\%80\%933\%E2\%80\%934\_tree}
\end{thebibliography}

\end{document}