#include <stdio.h>

struct tree {

tree* child[2] = { NULL };

int val = 0, height = 0;

tree(int x) { val = x; }

};

tree* update(tree* root) {

int x[2] = { (root->child[0] == NULL ? 0 : root->child[0]->height),

(root->child[1] == NULL ? 0 : root->child[1]->height) };

root->height = x[x[0] < x[1]] + 1;

return root;

}

tree* lr(tree* x, bool z){

tree* y = x->child[!z];

x->child[!z] = y->child[z];

y->child[z] = update(x);

return update(y);

}  tree* left(tree* x) { return lr(x, 0); } tree* right(tree* x) { return lr(x, 1); }

int getbal(tree* root) {

if (root == NULL) return 0;

return (root->child[0] == NULL ? 0 : root->child[0]->height)

- (root->child[1] == NULL ? 0 : root->child[1]->height);

}

void rotate(tree*& root) {

int bal = getbal(update(root));

if (bal > 1) {

if (getbal(root->child[1]) < 0) root->child[1] = left(root->child[1]);

root = right(root);

} else if (bal < -1) {

if (getbal(root->child[0]) > 0) root->child[0] = right(root->child[0]);

root = left(root);

}

}

bool insert(tree*& root, int val) {

if (root == NULL) { root = new tree(val); return true; }

if (root->val == val) return false;

if (!insert(root->child[root->val < val], val)) return false;

rotate(root);

return true;

}

tree* find(tree*& root, int val) {

if (root == NULL) return NULL;

if (root->val == val) return root;

return find(root->child[root->val < val], val);

}

void del_1(tree* root, tree*& temp) {

if (temp->child[1] == NULL) {

root->val = temp->val;

tree* x = temp; temp = temp->child[0];

delete x; return;

}

del_1(root, temp->child[1]);

rotate(temp);

}

bool del(tree*& root, int val) {

if (root == NULL) return false;

if (root->val == val) {

tree* temp = NULL;

int n = (root->child[0] != NULL) + (root->child[1] != NULL);

bool x = getbal(root);

if (n == 0) { delete root; root = NULL; }

else if (n == 1) { temp = root; root = root->child[x]; delete temp; }

else del_1(root, root->child[!x]); 

return true;

}

if(del(root->child[root->val < val], val) == NULL) return false;

rotate(root);

return true;

}

잘 짯나요? 그리고 짧은 편인가요?