AfanasevGad7

This is a task for our favourite professor
git clone git://git.stellar-nexus.ru/AfanasevGad7
Log | Files | Refs

final_solution.cpp (2879B)

      1 #include <iostream>
      2 
      3 
      4 struct Node {
      5 	int val;
      6 	Node* left;
      7 	Node* right;
      8 };
      9 
     10 
     11 Node* init(int);
     12 
     13 Node* add(int, Node*);
     14 
     15 Node* parse_pre(Node*);
     16 
     17 Node* parse_post(Node*);
     18 
     19 Node* parse_inf(Node*);
     20 
     21 int get_height(Node*);
     22 
     23 Node* balance(Node*);
     24 Node* balance2(Node*);
     25 
     26 Node* left_turn(Node*);
     27 
     28 Node* right_turn(Node*);
     29 
     30 Node* search(Node*, int);
     31 
     32 
     33 int main() {
     34 
     35 	Node* root = nullptr;
     36 
     37 	int k = 1;
     38 	while (k > 0)
     39 	{
     40 		std::cin >> k;
     41 		if (k > 0)
     42 			root = add(k, root);
     43 	}
     44 
     45 	// value_node = search(root, 'int value from input'));
     46 
     47 	return 0;
     48 }
     49 
     50 
     51 Node*
     52 init(int val)
     53 {
     54 	Node *n = (Node *) malloc(sizeof(Node));
     55 	if (n == NULL)
     56 		return NULL;
     57 	
     58 	n->val = val;
     59 	n->left = NULL;
     60 	n->right = NULL;
     61 
     62 	return n;
     63 }
     64 
     65 
     66 Node*
     67 add(int val, Node* root)
     68 {
     69 	if (!root)
     70 		return init(val);
     71 	
     72 	if (val < root->val)
     73 		root->left = add(val, root->left);
     74 	else if (val > root->val)
     75 		root->right = add(val, root->right);
     76 	else
     77 		return root;
     78 
     79 	return balance2(root);
     80 }
     81 
     82 
     83 Node* 
     84 parse_pre(Node* root) 
     85 {
     86 	int val = root->val;
     87 
     88 	// do smth with val
     89 
     90 	if (root->left) parse_pre(root->left);
     91 	if (root->right) parse_pre(root->right);
     92 	
     93 	return NULL;
     94 }
     95 
     96 
     97 Node*
     98 parse_post(Node* root) 
     99 {
    100 	if (root->left) parse_post(root->left);
    101 	if (root->right) parse_post(root->right);
    102 	
    103 	int val = root->val;
    104 
    105 	// do smth with val
    106 
    107 	return NULL;
    108 }
    109 
    110 
    111 Node*
    112 parse_inf(Node* root)
    113 {
    114 	if (root->left) parse_inf(root->left);
    115 
    116 	int val = root->val;
    117 
    118 	// do smth with val
    119 
    120 	if (root->right) parse_inf(root->right);
    121 
    122 	return NULL;
    123 }
    124 
    125 
    126 int
    127 get_height(Node* root)
    128 {
    129 	int r, l;
    130 
    131 	if (!root)
    132 		return 0;
    133 
    134 	l = get_height(root->left) + 1;
    135 	r = get_height(root->right) + 1;
    136 
    137 	if (l > r) {
    138 		return l;
    139 	}
    140 
    141 	return r;
    142 }
    143 
    144 inline int
    145 get_balance_factor(Node* root)
    146 {
    147 	if (!root)
    148 		return 0;
    149 	
    150 	return get_height(root->left) - get_height(root->right);
    151 }
    152 
    153 
    154 Node*
    155 right_turn(Node* root) 
    156 {
    157 	if (!root || !root->left)
    158 		return root;
    159 
    160 	Node* buf = root->left;
    161 	root->left = buf->right;
    162 	buf->right = root;
    163 	return buf;
    164 }
    165 
    166 
    167 Node*
    168 left_turn(Node* root)
    169 {
    170 	if (!root || !root->right)
    171 		return root;
    172 
    173 	Node* buf = root->right;
    174 	root->right = buf->left;
    175 	buf->left = root;
    176 	return buf;
    177 }
    178 
    179 
    180 Node*
    181 balance(Node* root)
    182 {
    183 	int h_l = get_height(root->left), h_r = get_height(root->right);
    184 
    185 	if (std::abs(h_l - h_r) > 1) {
    186 		if (h_l > h_r) return right_turn(root);
    187 		
    188 		return left_turn(root);
    189 	}
    190 
    191 	return root;
    192 }
    193 
    194 Node*
    195 balance2(Node* root)
    196 {
    197 	if (!root)
    198 		return nullptr;
    199 	
    200 	int bf = get_balance_factor(root);
    201 
    202 
    203 	if (bf > 1) {
    204 		if (get_balance_factor(root->left) < 0)
    205 			root->left = left_turn(root->left);
    206 		return right_turn(root);
    207 	}
    208 
    209 	if (bf < -1) {
    210 		if (get_balance_factor(root->right) > 0)
    211 			root->right = right_turn(root->right);
    212 		return left_turn(root);
    213 	}
    214 
    215 	return root;
    216 }
    217 
    218 
    219 Node*
    220 search(Node* root, int val)
    221 {
    222 	if (root->val == val) return root;
    223 
    224 	if (root->val > val) return search(root->left, val);
    225 	
    226 	return search(root->right, val);
    227 }