diff options
Diffstat (limited to '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; } |