Adding treap code and changes on LCA code.

4 files changed, 46 insertions, 2 deletions

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 9018cd5..7659a7e 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -18,5 +18,8 @@ Dazu: Offset in den inneren Knoten des Baums speichern.
 \subsection{STL-Tree}
 \lstinputlisting{datastructures/stlTree.cpp}
 
-\subsection{STL-Rope}
+\subsection{STL-Rope (Implicit Cartesian Tree)}
 \lstinputlisting{datastructures/stlRope.cpp}
+
+\subsection{Treap (Cartesian Tree)}
+\lstinputlisting{datastructures/treap.cpp}
diff --git a/datastructures/treap.cpp b/datastructures/treap.cpp
new file mode 100644
index 0000000..7c4ce7f
--- /dev/null
+++ b/datastructures/treap.cpp
@@ -0,0 +1,39 @@
+struct item {
+  int key, prior;
+  item *l, *r;
+  item() { }
+  item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
+};
+
+void split (item *t, int key, item *l, item *r) {
+  if (!t) l = r = NULL;
+  else if (key < t->key) split(t->l, key, l, t->l), r = t;
+  else split(t->r, key, t->r, r), l = t;
+}
+
+void insert (item *t, item *it) {
+  if (!t) t = it;
+  else if (it->prior > t->prior) split(t, it->key, it->l, it->r), t = it;
+  else insert(it->key < t->key ? t->l : t->r, it);
+}
+
+void merge (item *t, item *l, item *r) {
+  if (!l || !r) t = l ? l : r;
+  else if (l->prior > r->prior) merge(l->r, l->r, r), t = l;
+  else merge(r->l, l, r->l), t = r;
+}
+
+void erase (item *t, int key) {
+  if (t->key == key) merge (t, t->l, t->r);
+  else erase(key < t->key ? t->l : t->r, key);
+}
+
+item *unite (item *l, item *r) {
+  if (!l || !r)  return l ? l : r;
+  if (l->prior < r->prior) swap(l, r);
+  item * lt, rt;
+  split(r, l->key, lt, rt);
+  l->l = unite(l->l, lt);
+  l->r = unite(l->r, rt);
+  return l;
+}
diff --git a/graph/LCA.cpp b/graph/LCA.cpp
index f494b0b..a57e326 100644
--- a/graph/LCA.cpp
+++ b/graph/LCA.cpp
@@ -1,6 +1,8 @@
 vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N);
 vector<vector<int>> graph(MAX_N);
 
+// Funktioniert nur mit von der Wurzel weggerichteten Kanten.
+// Falls ungerichtete Kanten, visited-check einführen.
 void initLCA(int gi, int d, int &c) { // Laufzeit: O(n)
 	visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++;
 	for(int gn : graph[gi]) {
@@ -16,4 +18,4 @@ int getLCA(int a, int b) { // Laufzeit: O(1)
 // Benutzung:
 int c = 0;
 initLCA(0, 0, c);
-initRMQ(); // Ersetze das data im RMQ-Code von oben durch depth.
+initRMQ();
diff --git a/tcr.pdf b/tcr.pdf
index 84f0c53..6a44315 100644
--- a/tcr.pdf
+++ b/tcr.pdf