commit 2602cce5637a32ada794fbca2f9b884899c98531
parent 21705f93b6b23825b418fa76794b739c74c5b0f2
Author: = <=>
Date: Thu, 23 Oct 2025 17:06:56 +0300
Final cpp solution added
Diffstat:
| A | final_solution.cpp | | | 175 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 175 insertions(+), 0 deletions(-)
diff --git a/final_solution.cpp b/final_solution.cpp
@@ -0,0 +1,174 @@
+#include <iostream>
+
+
+struct Node {
+ int val;
+ Node* left;
+ Node* right;
+};
+
+
+Node* init(int);
+
+void add(int, Node*);
+
+Node* parse_pre(Node*);
+
+Node* parse_post(Node*);
+
+Node* parse_inf(Node*);
+
+int get_height(Node*);
+
+Node* balance(Node*);
+
+Node* left_turn(Node*);
+
+Node* right_turn(Node*);
+
+
+int main() {
+
+ Node* root = init(67);
+
+ int k = 1;
+ while (k > 0)
+ {
+ std::cin >> k;
+ add(k, root);
+ root = balance(root);
+
+ }
+}
+
+
+Node*
+init(int val)
+{
+ Node n = { val, NULL, NULL };
+
+ return &n;
+}
+
+
+void
+add(int val, Node* root)
+{
+ if (val < root->val) {
+ if (!root->left)
+ root->left = init(val);
+ else
+ add(val, root->left);
+ }
+ else {
+ if (!root->right)
+ root->right = init(val);
+ else
+ add(val, root->right);
+ }
+}
+
+
+Node*
+parse_pre(Node* root)
+{
+ int val = root->val;
+
+ // do smth with val
+
+ if (root->left) parse_post(root->left);
+ if (root->right) parse_post(root->right);
+
+ return NULL;
+}
+
+
+Node*
+parse_post(Node* root)
+{
+ if (root->left) parse_post(root->left);
+ if (root->right) parse_post(root->right);
+
+ int val = root->val;
+
+ // do smth with val
+
+ return NULL;
+}
+
+
+Node*
+parse_inf(Node* root)
+{
+ if (root->left) parse_inf(root->left);
+
+ int val = root->val;
+
+ // do smth with val
+
+ if (root->right) parse_inf(root->right);
+
+ return NULL;
+}
+
+
+int
+get_height(Node* root)
+{
+ int r, l;
+
+ if (!root)
+ return 0;
+
+ l = get_height(root->left) + 1;
+ r = get_height(root->right) + 1;
+
+ if (l > r) {
+ return l;
+ }
+
+ return r;
+}
+
+
+Node*
+right_turn(Node* root)
+{
+ Node* buf = root->right;
+
+ if (!buf || !root) return NULL;
+
+ root->right = root->right->left;
+ buf->left = root;
+
+ return buf;
+}
+
+
+Node*
+left_turn(Node* root)
+{
+ Node* buf = root->left;
+
+ if (!buf || !root) return NULL;
+
+ root->left = root->left->right;
+ buf->right = root;
+
+ return buf;
+}
+
+
+Node*
+balance(Node* root)
+{
+ int h_l = get_height(root->left), h_r = get_height(root->right);
+
+ if (std::abs(h_l - h_r) > 1) {
+ if (h_l > h_r) return right_turn(root);
+
+ return left_turn(root);
+ }
+
+ return root;
+}
+\ No newline at end of file
