\documentclass{soiminar}
%\usepackage{cmap}
%\usepackage{ifpdf}
%\ifpdf 
%    \usepackage[pdftex]{graphicx}   % to include graphics
%    \pdfcompresslevel=9 
%    \usepackage[pdftex,     % sets up hyperref to use pdftex driver
%            plainpages=false,   % allows page i and 1 to exist in the same document
%            breaklinks=true,    % link texts can be broken at the end of line
%            colorlinks=true]{hyperref} 
%    \usepackage{thumbpdf}
%\else 
%    \usepackage{graphicx}       % to include graphics
%    \usepackage{hyperref}       % to simplify the use of \href
%\fi 

\usepackage[super,square,comma,sort&compress,numbers]{natbib}
%\usepackage[dvipsnames]{xcolor}

\makeatletter

\usepackage{wrapfig}
\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc} % Makes text copy-pasteable but tuns font into bitmap font
\usepackage{multicol}
\usepackage{float}
\usepackage{booktabs}
\usepackage[skip=2pt]{caption}
\usepackage{titling}
\usepackage{qrcode}
\usepackage{listings}
\usepackage{afterpage}
%\usepackage{subfigure}
\usepackage{placeins}
\usepackage[colorinlistoftodos,prependcaption,textsize=tiny]{todonotes}
\usepackage{alltt}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{scrextend}
\usepackage{enumitem}
\usepackage[titletoc,title]{appendix}

%\usepackage[a4paper, margin=1.25in]{geometry}

\usepackage{url}
\hypersetup{
  colorlinks = true, 
  allcolors  = black, % Make links black
}
\def\UrlBreaks{\do\/\do-} % Allow line breaks after slash and hyphen

% Prevent widows and orphans

\clubpenalty=9996
\widowpenalty=10000
\brokenpenalty=4991
\predisplaypenalty=10000
\postdisplaypenalty=1549
\displaywidowpenalty=1602

% Custom commands

\newcommand{\mli}[1]{\mathit{#1}}
\newcommand{\si}[1]{\mathrm{#1}}
\newcommand{\msi}[1]{\,\mathrm{#1}}

\newcommand{\code}[1]{\texttt{#1}}
\newcommand{\resize}[1]{\resizebox{\dimexpr\columnwidth}{!}{#1}}
\newcommand{\q}[1]{``#1''}

\newcommand{\bigO}{\mathcal{O}}

\newlength{\mkboxlength}
\def\mkbox#1{\makebox[\mkboxlength]{#1\hfill}}

% Listing

\usepackage{listings}
\lstdefinelanguage{Cpp} { %
    language=C++,
    basicstyle=\footnotesize\ttfamily,
    numbers=left,
    numberstyle=\tiny,
    frame=tb,
    tabsize=4,
    columns=fixed,
    showstringspaces=false,
    showtabs=false,
    keepspaces,
    commentstyle=\color{gray},
    keywordstyle=\color{blue},
    stringstyle=\color{red},
    %
    keywordstyle=[2]\color{Fuchsia},
    morekeywords=[2]{T, Treap, Node},
    keywordstyle=[3]\color[rgb]{0.3, 0.3, 0.3},
    morekeywords=[3]{NULL},
    %
    captionpos=b,
    breaklines=true,
    postbreak=\mbox{{$\hookrightarrow$}\space},
    escapechar=§
}

\def\ContinueLineNumber{\lstset{firstnumber=last}}
\def\StartLineAt#1{\lstset{firstnumber=#1}}
\let\numberLineAt\StartLineAt


% Page Formating

\emergencystretch 3em
\setlist[itemize]{itemsep=-1pt}

%
% Title
%

\title{Treap}
\author{Nicolas Camenisch}
\date{Januar 2019}


%
% Document
%

\begin{document}

\ContinueLineNumber
\maketitle

%
% Content
%

\section{What is a treap?}
A treap (conjunction of the words \textbf{tre}e and he\textbf{ap}) is a binary search tree that uses randomization and the binary heap property to maintain balance with a high probability. It maintains a dynamic set of ordered keys and allows binary searches among these keys.\cite{wiki_treap} 

Each node of a treap contains two values: A key (ordered using binary search tree properties) and a priority (ordered using heap properties). The heap order can either be maintained using a max heap or a min heap. In all following examples a max heap will be used.

The structure of a treap follows these rules: \cite{yt_treap}
\begin{enumerate}
    \item The nodes in the left subtree of the root will have key values that are less than the key of the root.
    \(\forall \texttt{x} \in \texttt{root.left}, \quad \texttt{x.key} < \texttt{root.key}\)

    \item The nodes in the right subtree of the root will have key values that are greater than the key of the root.
    \(\forall \texttt{x} \in \texttt{root.right}, \quad \texttt{x.key} > \texttt{root.key}\)

    \item All priorities are unique.
   
    \item The priority value of the root is greater than the priority values of its children.
    \(\forall \texttt{x} \in \texttt{root.left} \cup \texttt{root.right}, \quad \texttt{x.priority} < \texttt{root.priority}\)
\end{enumerate}

These rules ensure, that there is only one unique and valid structure for each possible set of keys and priorities.

\section{Operations}
Treaps support a variety of operations. These operations can either be implemented using tree rotations (Figure \ref{fig:tree_rotation}), or using merge and split. Because the latter supports more operations, we're going to focus on merge and spit.

\begin{figure}[t]
    \centering
    \resizebox{0.7\dimexpr\columnwidth}{!}{\includegraphics{img/Tree_rotation.png}}
    \caption[Tree rotations]{A tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. \cite{wiki_tree_rotation}\cite{wiki_tree_rotation_img}}
    \label{fig:tree_rotation}
\end{figure}

\subsection{Merge \& Split}
We start out by defining the struct for our treap and the corresponding nodes (Listing~\ref{lst:struct}). The \texttt{Treap} struct is very basic and only contains a pointer to the root node and some functions. A \texttt{Node} consists of two pointers pointing to its left and right child, the \texttt{key} and \texttt{priority} values, and a \texttt{size} variable that keeps track of the size of both subtrees. During initialization the priority gets assigned a random integer.

\begin{lstlisting}[language=Cpp, caption={The Treap struct used in the following implementation.}, label={lst:struct}]
template <typename T>
struct Treap {
    struct Node {
        int priority;
        T key;
        size_t size = 0;
        std::unique_ptr<Node> l, r;

        Node(T key): priority(rand()), key(key) {}
    };

    std::unique_ptr<Node> root;

    void insert(const T& key);
    void erase(const T& key);
    T at(size_t index);
    size_t size() const {
        return (root == NULL ? 0 : root->size + 1);
    }

private:
    static std::pair<std::unique_ptr<Node>, std::unique_ptr<Node>> split(std::unique_ptr<Node> current, const T& key);
    static std::unique_ptr<Node> merge(std::unique_ptr<Node> l, std::unique_ptr<Node> r);
};
\end{lstlisting}

\subsubsection{Split}
The split function (Listing~\ref{lst:split}) splits a treap into two separate treaps, those smaller or equal the key \(x\), and those larger than the key \(x\). The following implementation is in-place destructive, but there also exist nondestructive algorithms.

\begin{lstlisting}[language=Cpp, caption={The \texttt{split} function. \cite{acm_treap}}, label={lst:split}]
static std::pair<std::unique_ptr<Node>, std::unique_ptr<Node>> split(std::unique_ptr<Node> current, const T& key) {
    std::unique_ptr<Node> l, r;

    if (current == NULL)
        return {std::move(l), std::move(r)};
    if (key < current->key) {
        r = std::move(current);
        tie(l, r->l) = split(std::move(r->l), key);
        r->size -= (l == NULL ? 0 : l->size + 1);
    } else {
        l = std::move(current);
        tie(l->r, r) = split(std::move(l->r), key);
        l->size -= (r == NULL ? 0 : r->size + 1);
    }

    return {std::move(l), std::move(r)};
}
\end{lstlisting}


\subsubsection{Merge}
The merge function (Listing~\ref{lst:merge}) merges two treaps into one treap. For this to work the greatest key in the first treap has to be less than or equal the smallest value in the second treap. This is always true if the first and second tree both are the result of a split operation. Like the split function, this implementation is in-place destructive, but there also exist nondestructive versions.

\begin{lstlisting}[language=Cpp, caption={The \texttt{merge} function. \cite{acm_treap}}, label={lst:merge}]
static std::unique_ptr<Node> merge(std::unique_ptr<Node> l, std::unique_ptr<Node> r) {
    if (l == NULL || r == NULL)
        return (l != NULL) ? std::move(l) : std::move(r);

    if (l->priority > r->priority) {
        l->size += r->size + 1;
        l->r = merge(std::move(l->r), std::move(r));
        return l;
    } else {
        r->size += l->size + 1;
        r->l = merge(std::move(l), std::move(r->l));
        return r;
    }
}
\end{lstlisting}

\subsection{Basic operation}
Based on the split and merge functions we can implement three different basic operations: search, insert and delete. Because the search operation is a standard binary search in a binary tree (ignoring the priorities), we'll skip over it. Since the following operations only modify the treap by calling the \texttt{merge} and \texttt{split} functions, the heap invariant never gets violated.

\subsubsection{Insert}
To insert a node \texttt{N}, you first search the correct position to insert it into. This means a position that doesn't violate either the BST or max heap properties. 
This can be done by splitting the treap into two treaps \texttt{l} and \texttt{r}, one where all values are less than or equal the key of \texttt{N} (\texttt{l}), and one where the key is greater (\texttt{r}).
Finally you merge \texttt{l}, \texttt{N} and \texttt{r} to form a treap that contains the new node \texttt{N} (Listing~\ref{lst:insert}).

\begin{lstlisting}[language=Cpp, caption={The \texttt{insert} function. \cite{acm_treap}}, label={lst:insert}]
void insert(const T& key) {
    auto node = std::make_unique<Node>(key);

    if (root == NULL) {
        root = std::move(node);
    } else {
        auto [l, r] = split(std::move(root), key);
        root = merge(merge(std::move(l), std::move(node)), std::move(r));
    }
}
\end{lstlisting}


\subsubsection{Delete}
% To delete a node $N$ with the key $k$, you first have to find it using the default BST binary search. Once you have found it, replace $N$ with the result of merging its two subtrees (Listing~\ref{lst:delete}). 
To remove a key $k$, you have to split the treap into three separate treaps: one containing only keys that are smaller than $k$ (\texttt{l}), equal to $k$ (\texttt{eq}) and greater than $k$ (\texttt{r}). You then merge the left and the right subtree of \texttt{eq} to remove the node of highest priority with key $k$. Finally you merge all three treaps back together to form a treap where the node with key $k$ is missing (Listing~\ref{lst:delete}).

\begin{lstlisting}[language=Cpp, caption={The \texttt{erase} function. \cite{acm_treap}}, label={lst:delete}]
void erase(const T& key) {
    if (root == NULL)
        return;

    std::unique_ptr<Node> l, r, eq;

    tie(l, r)  = split(std::move(root), key);
    tie(l, eq) = split(std::move(l), key - 1);

    eq = merge(std::move(eq->l), std::move(eq->r)); // Remove node with max prioirity
    root = merge(merge(std::move(l), std::move(eq)), std::move(r));
}
\end{lstlisting}

\subsection{Indexing}
A treap provides random access (Listing~\ref{lst:at}) in \(\bigO(\log n)\) time. This is possible by storing the size of the subtrees of each node and then walking down the tree until the specified index is reached.

\begin{lstlisting}[language=Cpp, caption={The \texttt{at} function.}, label={lst:at}]
T at(size_t index) {
    Node* current = root.get();

    while (current != NULL) {
        size_t leftSize = (current->l != NULL ? current->l->size+1 : 0);

        if (index < leftSize) {
            current = current->l.get();
        } else if (index > leftSize) {
            current = current->r.get();
            index -= leftSize + 1;
        } else {
            return current->key;
        }
    }

    throw std::out_of_range("");
}
\end{lstlisting}

\subsection{Bulk Operations}
Treaps also support several efficient bulk operations: union, intersection and set difference. The time complexity of these bulk operations is 
\(\bigO(m \log \frac{n}{m})\), where $m$ and $n$ are the treap sizes and $m \leq n$.


\section{Analysis}
Due to the random nature of a treap the expected depth of a node in a tree is less than \(2 \ln n = \bigO(\log n)\), but the worst case depth is \(\bigO(n)\).\cite{cs_cmu_edu_treaps}
Both the split and merge operation have a running time proportional to the height of the treap because they only traverse the path from the root down to the node being split / the node where it was split. Because the expected depth of any node is $\bigO(\log n)$, the expected run time of split and merge is $\bigO(\log n)$.

\begin{table}[bth]
    \center
    \begin{tabular}{lcc}
        \textbf{Operation} & \textbf{Average} & \textbf{Worst case} \\
     \hline
        \textbf{Space}     & $\bigO(n)$           & $\bigO(n)$  \\
        \textbf{Search}    & $\bigO(\log n)$      & $\bigO(n)$  \\
        \textbf{Insert}    & $\bigO(\log n)$      & $\bigO(n)$  \\
        \textbf{Delete}    & $\bigO(\log n)$      & $\bigO(n)$  \\
        \textbf{Indexing}  & $\bigO(\log n)$      & $\bigO(n)$  \\
    \end{tabular}
    \caption{Time complexity of a treap in big O notation.}
\end{table}


\section{Motivation}
During a normal programming contest you have 5 hours of time to solve three to four tasks. Due this tightly limited amount of time it is important to be able to implement algorithms fast and without bugs. When it comes to implementing a balanced BST, there are many options to choose from: 2-3 tree, red-black tree, scapegoat tree and many others. But by far the simplest to implement is the treap.  The implementation of all other BSTs is way to complex and most of the times, the performance improvement due the guaranteed maximal height of \(\log n\) isn't event necessary. \cite{coldatic}

If, for example, you wanted to maintain an ordered set of elements, you could use the \code{std::set} provided by the C\texttt{++} standard library. But since a \code{std::set} only provides \q{random access} in $\bigO(n)$ time, you sometimes have to implement your own set. In that case a treap is the simplest way to implement an ordered set with random access in $\bigO(\log n)$ time.

%
% Bib
%

% Notes:
% - use \footcite{} instead of \cite{}
% - \caption[Short description for LOF / LOT]{Long caption}

\phantomsection
\addcontentsline{toc}{section}{Literatur}

\bibliographystyle{unsrtnat}
\bibliography{ref}

\end{document}