drzewce.tex

\section{Drzewce}
\sectionauthor{Bartłomiej Betka}

\label{sec:drzewce}

Podobnie jak drzewa AVL oraz drzewa czerwono-czarne drzewce rozwiązują problem potencjalnego niezrównoważenia BST.
Osiągają one jednak ten cel w zupełnie inny sposób.
Zamiast kontrolować wysokość drzewa i jego poddrzew drzewce opierają się na randomizacji, która, jak zaraz pokażemy, zapewnia asymptotycznie równie dobre oczekiwane własności. 

\begin{definition} 
Drzewiec to drzewo binarne, którego każdy węzeł posiada zarówno klucz, jak i priorytet.
Względem kluczy drzewiec jest drzewem przeszukiwań binarnych, a względem priorytetów jest on kopcem.
\end{definition}

\paragraph{Podstawowe operacje, które implementują drzewce:}
\begin{itemize}
    \item \textbf{Find} Wygląda dokładnie tak, jak w drzewie BST (względem kluczy).
    \item \textbf{Insert} Najpierw wstawiamy wartość (wraz z losowym priorytetem) jak do drzewa BST, następnie rotacjami przywracamy porządek kopcowy.
    \item \textbf{Delete} Znajdujemy klucz, rotacjami spychamy go do liścia, następnie usuwamy ten liść (co nie zaburza ani porządku BST, ani kopca).
    \item Pomocniczo potrzebne są również operacje rotacji służące do przywracania porządku kopcowego.
\end{itemize}

Na końcu rozdziału znajduje się pseudokod, który pokazuje, jak można zaimplementować powyższe metody i pozwala przekonać się, że jest to znacznie łatwiejsze niż w przypadku analogicznych operacji na drzewach AVL czy drzewach czerwono-czarnych.

Teraz udowodnimy kilka własności drzewców.
W każdym z poniższych dowodów zakładamy, że wszystkie priorytety są różne.

\begin{theorem}
\label{unique treap}
Dla każdego zbioru par $(klucz, priorytet)$ istnieje dokładnie jeden drzewiec.
\end{theorem}
\begin{proof}
Oczywiście para, w której znajduje się najwyższy priorytet, musi znajdować się w korzeniu drzewa.
W jego lewym poddrzewie znajdować się muszą wszystkie pary o mniejszych kluczach, a w prawym wszystkie pary o większych kluczach, które indukcyjnie tworzą drzewce według tej samej zasady.
\end{proof}

Z twierdzenia tego i jego dowodu wprost wynika, że drzewiec tworzy BST o takim kształcie, jakby kolejne klucze były dodawane w kolejności rosnących priorytetów.

\begin{theorem}
Oczekiwana wysokość drzewca jest $O(log\ n)$.
\end{theorem}
\begin{proof}
Aby udowodnić nasze twierdzenie pokażemy, że wartość oczekiwana głębokości dowolnego węzła (ilość jego przodków) jest $O(log\ n)$.

Oznaczmy $N_k$ - węzeł o kluczu $k$ i wyznaczmy zmienną losową:

$$
X_{ij} =
  \begin{cases} 
  1 &  N_j\text{ jest przodkiem }N_i\\
  0 & $wpp.$
  \end{cases}
$$

Bez straty ogólności załóżmy teraz, że klucze są kolejnymi dodatnimi liczbami naturalnymi ($[1,n]$) i spróbujmy obliczyć $P(X_{ij})$.

Rozważmy węzły o kluczach z $[i, j]$ (węzły z kluczami spoza tego zakresu nie mają znaczenia dla obliczania $P(X_{ij})$) oraz ich priorytety. Mamy trzy możliwe przypadki:
\begin{enumerate}
\item Węzeł $N_i$  ma najniższy priorytet.
W tej sytuacji $N_j$ nie może, oczywiście, być przodkiem $N_i$.
\item Element o kluczu $k$ różnym od $i$ i $j$ ma najniższy priorytet.
W tym przypadku $N_k$ znajdzie się w korzeniu drzewca zawierającego zarówno $N_i$, jak i $N_j$, a ponieważ $i < k< j \lor j < k < i$ to $N_i$ i $N_j$ trafią do różnych poddrzew $N_k$.
\item Element o kluczu $j$ ma najwyższy priorytet.
Tylko w tym wypadku $N_j$ jest przodkiem $N_i$, ponieważ między nimi nie ma żadnego węzła o niższym priorytecie, który rozdzieliłby je do osobnych poddrzew jak w przypadku powyżej.
\end{enumerate}

Interesuje nas zatem $(|j - i|)!$ spośród $(|j - i| + 1)!$ permutacji, czyli $P(X_{ij}) = \frac{1}{|j-i| + 1}$.

A stąd oczekiwana wysokość $N_i$ to:
$$
\begin{aligned}
\mathbf{E}\left[\text{wysokość }N_i\right]={} & \sum_{j=1, j\neq i}^{n} \frac{1}{|j-i| + 1}= \\
& \overbrace{
\sum_{j=1}^{i-1}\frac{1}{i-j+1}+
\sum_{j=i+1}^{n}\frac{1}{j-i+1}
}^\text{szeregi harmoniczne bez jedynek}< \\
& 2ln\ n= \\
& O(log\ n)
\end{aligned}
$$
\end{proof}

\newpage

\begin{theorem}
Oczekiwana ilość rotacji przy \texttt{insert}/\texttt{delete} < 2.
\end{theorem}
\begin{proof}
Nasz dowód rozpoczniemy od pomocniczej definicji:
\begin{definition}
\textbf{Lewym/Prawym Kręgosłupem} drzewa nazywamy ścieżkę od korzenia do węzła z najmniejszym/największym kluczem (złożoną wyłącznie z lewych/prawych krawędzi).
\end{definition}
Rozważmy teraz długość kręgosłupów dzieci dodawanego węzła w czasie operacji \texttt{insert}.
Nie trudno zauważyć, że początkowo oba są długości $0$ oraz że każda rotacja w lewo wydłuża prawy kręgosłup lewego dziecka o $1$.
Analogicznie, każda rotacja w prawo wydłuża lewy kręgosłup prawego dziecka o $1$.
Wynika stąd, że ilość rotacji potrzebnych przy wstawianiu węzła jest równa długości lewego kręgosłupa prawego dziecka i prawego kręgosłupa lewego dziecka nowo wstawionego węzła (po zakończeniu procedury).

Spróbujmy teraz określić wartości oczekiwane tych parametrów.
Weźmy dwa różne węzły $x$ i $y$ należące do drzewca. Oznaczmy $i=y.key$ i $k=x.key$, i wyznaczmy zmienną losową:

$$
X_{ik} =
  \begin{cases}
  1 &  y \in$ prawego kręgosłupa lewego poddrzewa $x\\
  0 & $wpp.$
  \end{cases}
$$

Pokażemy teraz, że $X_{ik} = 1 \iff y.priority > x.priority \land y.key < x.key \land (\forall z\ y.key < z.key < x.key \implies y.priority < z.priority)$

Implikacja w prawo wynika wprost z definicji drzewca.
Rozważmy zatem implikację w drugą stronę.
Ponieważ $y.priority > x.priority \land y.key < x.key$ to $y$ należy do lewego poddrzewa $x$.
W takim razie gdyby $y$ nie należał do prawego kręgosłupa lewego poddrzewa $x$, to musiałby istnieć $z$ t.że $y.key < z.key < x.key$ i $y.priority > z.priority$, co daje sprzeczność.

Bez straty ogólności załóżmy, że klucze są kolejnymi dodatnimi liczbami naturalnymi ($[1,n]$) i spróbujmy obliczyć $P(X_{ik})$.

Rozważmy teraz węzły o kluczach z $[i, k]$. Jeśli chcemy, żeby $\forall z\in[i+1,k-1]\ x.priority < y.priority < z.priority$, to spośród wszystkich $(k-i+1)!$ permutacji interesują nas te, w których $y.priority$ i $x.priority$ są kolejno na dwóch pierwszych pozycjach. Takich permutacji jest  $(k-i-1)!$.
Stąd $P(X_{ik}) = \frac{(k -i - 1)!}{(k -i + 1)!} =  \frac{1}{(k-i+1)(k-i)}$.

Teraz policzmy:
$$
\begin{aligned}
\mathbf{E}\left[\sum_{i=1}^{k}X_{ik}\right]={}  & \sum_{i=1}^{k}\mathbf{E}\left[X_{ik}\right]= \\
& \sum_{i=1}^{k}\frac{1}{(k-i+1)(k-i)}= \\
& \sum_{i=1}^{k}\frac{1}{i(i+1)}= \\
& \sum_{i=1}^{k}(\frac{1}{i}-\frac{1}{i+1})= \\
& 1-\frac{1}{k}
\end{aligned}
$$

Po przeprowadzeniu analogicznego rozumowania dla lewego kręgosłupa prawego poddrzewa (klucze z $[k,n]$) otrzymujemy dla niego wartość oczekiwaną $1 - \frac{1}{n-k+1}$.

To razem daje nam oczekiwaną ilość rotacji równą $1 - \frac{1}{k} + 1 - \frac{1}{n-k+1} = 2 -  \frac{1}{k} - \frac{1}{n-k+1} < 2$.

Identyczna liczba rotacji dla \texttt{delete} wynika wprost z powyższego oraz Twierdzenia \ref{unique treap}.
\end{proof}

Powyższe twierdzenia pokazują, że wysokość drzewców, a tym samym operacje na nich, ma dobrą złożoność asymptotyczną, a przy tym (oczekiwany) narzut związany z rotacjami jest ograniczony przez niewielką stałą.

\newpage

\begin{algorithm}
  \DontPrintSemicolon
  \SetAlgorithmName{Algorytm}{}

  \KwData{ $root$ }

  $new\_root \leftarrow root.right$\;
  $root.right \leftarrow new\_root.left$\;
  $new\_root.left \leftarrow root$\;
  \Return $new\_root$\;
  
  \caption{\texttt{rotateLeft (rotacja w prawo jest analogiczna)}}
  \label{treap-rotate-left}
\end{algorithm}

\begin{algorithm}
  \DontPrintSemicolon
  \SetAlgorithmName{Algorytm}{}

  \KwData{ $root$, $value$ }
  \If{$root = null$}
  {
    \Return $Node(value, random())$\;
  }
  \ElseIf{$root.key = value$}
  {
    \Return $root$\;
  }
  \ElseIf{$root.key > value$}
  {
    $root.left \leftarrow insert(root.left, value)$\;
    \If{$root.left.priority < root.priority$}
    {
      $root \leftarrow rotateLeft(root)$\;
    }
  }
  \ElseIf{$root.key < value$}
  {
    $root.right \leftarrow insert(root.right, value)$\;
    \If{$root.right.priority < root.priority$}
    {
      $root \leftarrow rotateRight(root)$\;
    }
  }
  
  \Return $root$\;
  \caption{\texttt{insert}}
  \label{treap-insert}
\end{algorithm}

\begin{algorithm}
  \DontPrintSemicolon
  \SetAlgorithmName{Algorytm}{}

  \KwData{ $root$, $value$ }
  
  \If{$root = null$}
    {
      \Return $null$\;
    }
  \ElseIf{$root.key > value$}
  {
     $root.left \leftarrow delete(root->left, value)$\;
  }
  \ElseIf{$root.key < value$}
  {
     $root.right \leftarrow delete(root->right, value)$\;
  }
  \ElseIf{$root.key = value$}
  {
  	\If{$root.left = null$}
  	{
  	  \Return $root.right$\;
  	}
  	\ElseIf{$root.right = null$}
  	{
  	  \Return $root.left$\;
  	}
  	\ElseIf{$root.left.priority < root.right.priority$}
  	{
  	  $root \leftarrow rotateLeft(root)$\;
  	  $root.left \leftarrow delete(root.left, value)$\;
  	}
  	\Else
  	{
  	  $root \leftarrow rotateRight(root)$\;
  	  $root.right \leftarrow delete(root.right, value)$\;
  	}
  }
  \Return $root$\;
  \caption{\texttt{delete}}
  \label{treap-delete}
\end{algorithm}