#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* left(tree*& x) {

tree* y = x->child[1];

x->child[1] = y->child[0];

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

return update(y);

}

tree* right(tree*& x) {

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

x->child[0] = y->child[1];

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

return update(y);

}

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);

} 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) return (root = new tree(val)) != NULL;

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 root;

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

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

}

여기까지 짜봣습니다... 하하 근데 초딩이라서 그런지 좀 힘들군요. 잘못된 부분 있으면 말해주세요.