% Alla i gruppen ska lämna in individuellt i Moodle. 
%Det ska dock vara samma fil för alla så att vi kan se vilka som har jobbat ihop.
\documentclass[a4paper,10pt,oneside,onecolumn]{article}

\usepackage[swedish]{babel}

% Får ni problem med att pdf-filen ser suddig ut på skärmen så beror det på att ni inte har 
% en fullständig fontuppsättning och att bitmappade fonter i fel skala används. Den bästa lösningen 
% är att uppdatera fontuppsättningen, men man kan också plocka bort denna rad. Avstavning fungerar 
% dock betydligt sämre då.
\usepackage[T1]{fontenc}

% Här väljer ni naturligtvis den teckenkod ni använder er av
\usepackage[utf8]{inputenc}

\usepackage{a4wide}
\usepackage{graphicx}
\usepackage{cite}
\usepackage{url}
\usepackage{listings}
\lstset{language=Java, tabsize=3, numbers=left, frame=line}



% Glöm inte att uppdatera rubriken
\title{}


% Sortera gruppdeltagarna efter Efternamn. Om två personer har samma efternamn sorteras dessa efter förnamnen.
% Detta är viktigt eftersom vissa uppgifter bestäms av i vilken ordning namnen står. Tar man fel uppgift vid någon av dessa tillfällen blir man automatiskt underkänd.
\author{Ásgeir Davidsson\\sgda4222  \and David Rogers\\davi-rog} 

\begin{document}

\maketitle

\section{Treaps}

A treap is a mix of both a Tree and a Heap, hence the name Treap. It is actually a Binary Search Tree that is heap-ordered by a randomized priority.

A Binary Search Tree is a tree that always has at most two nodes. The data in these nodes needs a compareTo method since it is constructed in such a way that the right child node is always bigger than its parent node and the left child node is always smaller than its parent node. As you can probably figure out this makes for pretty fast searches in the tree.
A Heap is a datastructure where the children nodes have a lower priority than its parent. This means that the root node always have the highest priority in the heap.

So after that short explanation on the basic structures in treaps we can imagine how a node would be constructed. It needs its data of course but also a right child reference, a left child reference and a number serving as its priority. The priority is made with a random number generator.

A treap also has a nullNode that will always be at the bottom of the heap. This is done by setting its priority to infinite. In reality the nullNodes priority would probably be set to 0 (or a very high number if you want to have low numbers have higher priority) as it is pretty simple to fiddle with the random number generator so it never gives a 0.

\section{Methods for Treaps}

Before we can describe the basic methods used in treaps there is something that needs another quick explanation and that is rotations.
Rotations are done in Binary Search Trees to maintain its structure. Simply put we rotate when a child node is not placed correctly. For example if a node has two children that are both greater than the parent we rotate the parent node left. What this means is that we swap the places of the left child node and the parent. Depending on how the datastructure is implemented you may have to continue rotating down the tree to maintain its structure.

\subsection{Search} 
Finding a specific node in a treap is exactly the same as in a binary search tree. You start at the tree node and compare its data to the data you are after; if it is higher you go to the right child node and repeat the procedure, if it is lower you go to the left. Just continue doing this until you find the node you are looking for.

\subsection{Insert}
To insert a new node into a treap you first search for the best spot to place it as in a binary search tree. You do this with a modified search call that just finds the best spot for the new node compared to the other nodes. You then add this node as a leaf (a leaf is a node without children). You then simply rotate the node up until you have found the correct spot for it according to its priority.

\subsection{Remove}
The easiest way to remove a node in a treap is to first find that node and then just set its priority to the lowest possible (in effect the same as the nullNode). You then rotate it down until it has become a leaf and then the remove is very simple, you just put its parent reference to null.

\subsection{Split}
To do a split on a treap where you end up with all values smaller than X in one treap and values larger than X in another treap you simply add a new node with the value X and give it maximum priority. X then becomes the root and the new treaps is the left and right subtreaps of X.

\subsection{Merge}
To merge two treaps that were split in the previously explained fashion is fairly simple. You already know that the greatest value in the left subtreap is smaller than the smallest value in the right subtreap and vice versa. So what you do is pretty close to what you do with splits. You insert a new node X that has a greater value than the greatest value in the left treap and a smaller value than the smallest in the right treap (left and right is arbitrary names but it is easier to connect to the insert method) and give it minimum priority. After the insert is done X is a leaf node and can easily be deleted and what has happened is that you have effectively “un-done” the split. You can probably see some nifty similarities between Insert and Merge.
\vspace{10mm}
The inventors of the treap (Cecilia R. Aragon and Raimund Seidel) suggested a way to optimize a treap. What they suggested was to give nodes that are accessed more often than others a higher priority so that they are placed higher up in the treap. This makes the search for them a lot faster but you do loose the random shape of the treap.


\section{Why use a Treap?}

Treaps are relatively fast compared to other datastructures. Searching is as fast as in an unbalanced binary search tree (assuming you didn’t implement Aragon and Seidel’s suggested optimization, then it is faster). Insertion is just a bit slower than in an unbalanced binary search tree. Deletion is slower but it is still pretty fast. All in all treaps are slower than balanced binary search trees (using worst case scenarios), so why use them? Well they are a lot simpler to implement. Balanced binary search trees are pretty tricky to implement and bug test whereas treaps are actually very, very simple. And treaps are not that far off in performance. 

Treaps are very general and can work well in many situations. Any time you need a fast datastructure but don’t have time to properly bug-test it a treap works extremely well.
It has been suggested (by Naor and Nissim) that you can use treaps for authorization certificates (basically security magic that requires you to have a public key linked to some identity. 


\section{Pooluppgift}

 There are some easily recognized problems with a randomized priority. What are they and how do they affect the overall structure?
\vspace{4mm}

\noindent
G:
Mentions both when a random number is generated with the same priority as a node already in the treap. Also mentions that with a bad random number generator you can get a 0 as priority.
VG:
Mentions some sort of solution to at least the random number generator problem. Should probably at least mention some kind of solution to the other problem as well since the first one is so very easy to solve.


% Nedanstående är bara för om ni vill använda bibtex för att hantera referenser. 

%\bibliographystyle{plain}
%\bibliography{bibtex}
%\bibdata{bibtex}


\end{document}
