Algorithms : complete 02-data_structures 04-binary_search_trees

3 files changed, 231 insertions, 27 deletions

diff --git a/02-data_structures/04-binary_search_trees/01-tree_orders/tree-orders.cpp b/02-data_structures/04-binary_search_trees/01-tree_orders/tree-orders.cpp
index 5ee679c..d9437fa 100644
--- a/02-data_structures/04-binary_search_trees/01-tree_orders/tree-orders.cpp
+++ b/02-data_structures/04-binary_search_trees/01-tree_orders/tree-orders.cpp
@@ -27,27 +27,52 @@ public:
 
   vector <int> in_order() {
     vector<int> result;
-    // Finish the implementation
-    // You may need to add a new recursive method to do that
+    in_order_visit(0, result);
 
     return result;
   }
 
   vector <int> pre_order() {
-    vector<int> result;    
-    // Finish the implementation
-    // You may need to add a new recursive method to do that
-    
+    vector<int> result;
+    pre_order_visit(0, result);
+
     return result;
   }
 
   vector <int> post_order() {
     vector<int> result;
-    // Finish the implementation
-    // You may need to add a new recursive method to do that
-    
+    post_order_visit(0, result);
+
     return result;
   }
+private:
+
+  void in_order_visit(int n, vector<int> &r)
+  {
+      if (left[n] != -1)
+          in_order_visit(left[n], r);
+      r.push_back(key[n]);
+      if (right[n] != -1)
+          in_order_visit(right[n], r);
+  }
+
+  void pre_order_visit(int n, vector<int> &r)
+  {
+      r.push_back(key[n]);
+      if (left[n] != -1)
+          pre_order_visit(left[n], r);
+      if (right[n] != -1)
+          pre_order_visit(right[n], r);
+  }
+
+  void post_order_visit(int n, vector<int> &r)
+  {
+      if (left[n] != -1)
+          post_order_visit(left[n], r);
+      if (right[n] != -1)
+          post_order_visit(right[n], r);
+      r.push_back(key[n]);
+  }
 };
 
 void print(vector <int> a) {
diff --git a/02-data_structures/04-binary_search_trees/02-set_range_sum/set_range_sum.cpp b/02-data_structures/04-binary_search_trees/02-set_range_sum/set_range_sum.cpp
index 8de8e72..c634094 100644
--- a/02-data_structures/04-binary_search_trees/02-set_range_sum/set_range_sum.cpp
+++ b/02-data_structures/04-binary_search_trees/02-set_range_sum/set_range_sum.cpp
@@ -2,6 +2,8 @@
 
 // Splay tree implementation
 
+bool debug = false;
+
 // Vertex of a splay tree
 struct Vertex {
   int key;
@@ -16,6 +18,16 @@ struct Vertex {
   : key(key), sum(sum), left(left), right(right), parent(parent) {}
 };
 
+
+void print(Vertex *v, int l) {
+    if (v == NULL) return;
+    for (int i = 0; i < l; i++)
+        printf(" ");
+    printf("%p [%d]  ->%p -> %p\n", v, v->key, v->left, v->right);
+    if (v->left != NULL) print(v->left, l+1);
+    if (v->right != NULL) print(v->right, l+1);
+}
+
 void update(Vertex* v) {
   if (v == NULL) return;
   v->sum = v->key + (v->left != NULL ? v->left->sum : 0ll) + (v->right != NULL ? v->right->sum : 0ll);
@@ -147,6 +159,7 @@ Vertex* merge(Vertex* left, Vertex* right) {
 Vertex* root = NULL;
 
 void insert(int x) {
+  if (debug) printf("insert %d\n", x);
   Vertex* left = NULL;
   Vertex* right = NULL;
   Vertex* new_vertex = NULL;  
@@ -158,26 +171,41 @@ void insert(int x) {
 }
 
 void erase(int x) {                   
-  // Implement erase yourself
-
+    if (debug) printf("erase %d\n", x);
+    Vertex *v = find(root, x);
+    if (v == NULL)
+        return;
+    splay(root, v);
+    if (v->left != NULL)
+        v->left->parent = NULL;
+    if (v->right != NULL)
+        v->right->parent = NULL;
+    root = merge(v->left, v->right);
 }
 
-bool find(int x) {  
-  // Implement find yourself
-
-  return false;
+bool find(int x) {
+    if (debug) printf("find %d\n", x);
+    Vertex *v = find(root, x);
+    if (v == NULL) return false;
+    if (v != NULL && root != v)
+        splay(root, v);
+    return (v->key == x);
 }
 
 long long sum(int from, int to) {
+  if (debug) printf("sum %d - %d\n", from, to);
   Vertex* left = NULL;
   Vertex* middle = NULL;
   Vertex* right = NULL;
   split(root, from, left, middle);
   split(middle, to + 1, middle, right);
   long long ans = 0;
-  // Complete the implementation of sum
-  
-  return ans;  
+  if (middle != NULL) {
+      update(middle);
+      ans = middle->sum;
+  }
+  root = merge(merge(left, middle), right);
+  return ans;
 }
 
 const int MODULO = 1000000001;
@@ -214,6 +242,7 @@ int main(){
         last_sum_result = int(res % MODULO);
       }
     }
+    if (debug) print(root, 4);
   }
   return 0;
 }
diff --git a/02-data_structures/04-binary_search_trees/03-rope/rope.cpp b/02-data_structures/04-binary_search_trees/03-rope/rope.cpp
index d5f5f35..2f2bb75 100644
--- a/02-data_structures/04-binary_search_trees/03-rope/rope.cpp
+++ b/02-data_structures/04-binary_search_trees/03-rope/rope.cpp
@@ -2,22 +2,170 @@
 #include <string>
 #include <iostream>
 
+/* static bool debug = false; */
+
+struct Vertex {
+  const char *s;
+  size_t weight;
+  Vertex* left;
+  Vertex* right;
+
+  Vertex(const char *s, size_t weight)
+  : s(s), weight(weight), left(NULL), right(NULL) {}
+
+  Vertex(Vertex* left, Vertex* right, size_t weight)
+  : s(NULL), weight(weight), left(left), right(right) {}
+};
 
 class Rope {
 	std::string s;
+    Vertex *root;
 public:
-	Rope(const std::string &s) : s(s) { 
+	Rope(const std::string &s) : s(s) {
+        root = new Vertex(&s[0], s.size());
 	}
 
-	void process( int i, int j, int k ) {
-                // Replace this code with a faster implementation
-                std::string t = s.substr(0, i) + s.substr(j + 1);
-                s = t.substr(0, k) + s.substr(i, j - i + 1) + t.substr(k);
+	void process( int i, int j, int k )
+    {
+        Vertex* left = NULL;
+        Vertex* right = NULL;
+        Vertex* out = NULL;
+        int len = weight(root);
+
+        /* if (debug) std::cout << std::endl << "PROCESS : " << i << " " << j << " " << k << std::endl; */
+
+        if (i > 0) {
+            split(root, i, out);
+            left = root;
+            /* if (debug) { */
+            /*     std::cout << "   left : " << print(left) << std::endl; */
+            /*     std::cout << "    out : " << print(out) << std::endl; */
+            /* } */
+        } else {
+            left = NULL;
+            out = root;
+        }
+
+        if (len > (j + 1)) {
+            split(out, (j - i + 1), right);
+            /* if (debug) { */
+            /*     std::cout << "   out  : " << print(out) << std::endl; */
+            /*     std::cout << "  right : " << print(right) << std::endl; */
+            /* } */
+        } else {
+            right = NULL;
+        }
+
+        /* if (debug) std::cout << "  concat left || right : "; */
+        root = concat(left, right);
+        /* if (debug) std::cout << print(root) << std::endl; */
+
+        left = NULL;
+        right = NULL;
+        if (k > 0) {
+            split(root, k, right);
+            left = root;
+            /* if (debug) { */
+            /*     std::cout << "   left : " << print(left) << std::endl; */
+            /*     std::cout << "  right : " << print(right) << std::endl; */
+            /* } */
+            root = concat(left, concat(out, right));
+            /* if (debug) std::cout << "   root : " << print(root) << std::endl; */
+        } else {
+            root = concat(out, root);
+            /* if (debug) std::cout << "   root : " << print(root) << std::endl; */
+        }
 	}
 
 	std::string result() {
-		return s;
+        return print(root);
 	}
+
+private:
+    std::string print(Vertex *v)
+    {
+        /* std::cout << weight(v) << std::endl; */
+        if (v == NULL) return "NULL";
+        std::string res;
+        in_order(v, res);
+		return res;
+    }
+
+    void in_order(Vertex *v, std::string &r) {
+        if (v == NULL) return;
+        /* if (debug) { */
+        /*     std::cout << v << "  " << v->weight << " "; */
+        /*     if (v->s != NULL) { */
+        /*         for (int i = 0; i < v->weight; i++) */
+        /*             std::cout << v->s[i]; */
+        /*     } */
+        /*     std::cout << std::endl << "   " << v->left<< std::endl; */
+        /*     std::cout << "   " << v->right << std::endl; */
+        /* } */
+
+        in_order(v->left, r);
+        if (v->s != NULL) {
+            for (int i = 0; i < v->weight; i++)
+                r.push_back(v->s[i]);
+        }
+        in_order(v->right, r);
+    }
+
+    size_t weight(Vertex *v) {
+        size_t w = 0;
+        while (v != NULL) {
+            w += v->weight;
+            v = v->right;
+        }
+        return w;
+    }
+
+    Vertex* concat(Vertex *left, Vertex *right) {
+        if (right == NULL)
+            return left;
+        if (left == NULL)
+            return right;
+        return new Vertex(left, right, weight(left));
+    }
+
+    // split into : [0 ; (key-1)] [key; ...]
+    void split(Vertex* v, int key, Vertex*& outer) {
+        /* if (debug) std::cout << " split  " << key  << " " << print(v) << std::endl; */
+        _split(v, key, outer);
+    }
+
+    int _split(Vertex* v, int key, Vertex*& outer) {
+        if (v == NULL) return 0;
+        if (key < v->weight) {
+            if (v->left == NULL) {
+                /* if (debug) std::cout << "      found : " << v->s[key] << std::endl; */
+                Vertex *tmp = new Vertex(&v->s[key], v->weight - key);
+                v->weight = key;
+                outer = concat(tmp, outer);
+                return v->weight;
+            } else {
+                outer = concat(v->right, outer);
+                v->right = NULL;
+                v->weight = _split(v->left, key, outer);
+                // compress
+                if (v->left != NULL && v->left->left != NULL && v->left->right == NULL) {
+                    Vertex *tmp = v->left;
+                    v->left = v->left->left;
+                    delete(tmp);
+                }
+                return v->weight;
+            }
+        } else {
+            key -= v->weight;
+            if (key == 0) {
+                outer = concat(v->right, outer);
+                v->right = NULL;
+                return v->weight;
+            } else {
+                return v->weight + _split(v->right, key, outer);
+            }
+        }
+    }
 };
 
 int main() {
@@ -26,11 +174,13 @@ int main() {
 	std::cin >> s;
 	Rope rope(s);
 	int actions;
+    /* if (debug) std::cout << rope.result() << std::endl; */
 	std::cin >> actions;
-        for (int action_index = 0; action_index < actions; ++action_index) {
-                int i, j, k;
+    for (int action_index = 0; action_index < actions; ++action_index) {
+        int i, j, k;
 		std::cin >> i >> j >> k;
 		rope.process(i, j, k);
+        /* if (debug) std::cout << rope.result() << std::endl; */
 	}
-	std::cout << rope.result() << std::endl;
+    std::cout << rope.result() << std::endl;
 }