没写出，平衡二叉树需要多练多思考多画图.
注意点：
1、有可能并不是根结点的左右子树未平衡，遇到这种情况时，做平衡操作后，需要让该节点的父亲结点指向更新后的孩子结点，以保证树中间不断掉.
通过它们实现：
root->left = insert(root->left, val);
root->right = insert(root->right, val);
每次递归结束都会返回当前根结点，这样在递归回来时，当前根结点便会自然的指向已更新后的左孩子与右孩子（即上一递归结束返回过来的结点）.
2、若根结点的左右子树未平衡，则平衡操作后，根结点会更换，因此insert()函数每次的调用都应将最新的根结点返回出来，以保证下次作插入操作时，树是完整的.

//柳神 
#include <iostream>
using namespace std;
struct node {int val;struct node *left, *right;
};
node *rotateLeft(node *root) {node *t = root->right;root->right = t->left;t->left = root;return t;
}
node *rotateRight(node *root) {node *t = root->left;root->left = t->right;t->right = root;return t;
}
node *rotateLeftRight(node *root) {root->left = rotateLeft(root->left);return rotateRight(root);
}
node *rotateRightLeft(node *root) {root->right = rotateRight(root->right);return rotateLeft(root);
}
int getHeight(node *root) {                               //每次通过递归获取高度 if(root == NULL) return 0;return max(getHeight(root->left), getHeight(root->right)) + 1;            
}
node *insert(node *root, int val) {if(root == NULL) {root = new node();root->val = val;root->left = root->right = NULL;} else if(val < root->val) {root->left = insert(root->left, val);//递归回来时，若根结点的左子树做了修改，返回回来的一定是最新的左子结点. if(getHeight(root->left) - getHeight(root->right) == 2)                       root = val < root->left->val ? rotateRight(root) : rotateLeftRight(root);//通过比较目标值与root的左孩子值，确定是LL/LR } else {root->right = insert(root->right, val);//递归回来时，若根结点的右子树做了修改，返回回来的一定是最新的右子结点. if(getHeight(root->left) - getHeight(root->right) == -2)root = val > root->right->val ? rotateLeft(root) : rotateRightLeft(root);//通过比较目标值与root的左孩子值，确定是RL/RR}return root;                        //插入完成后返回root指针赋值给main函数里的root 
}
int main() {#ifdef ONLINE_JUDGE#elsefreopen("1.txt","r",stdin);#endifint n, val;scanf("%d", &n);node *root = NULL;for(int i = 0; i < n; i++) {scanf("%d", &val);root = insert(root, val);}printf("%d", root->val);return 0;
}