1 #include <iostream>
  2 #include <cstdlib>
  3 using namespace std;
  4 struct node
  5 {
  6     int v;
  7     int df;
  8     node * left_c;
  9     node * right_c;
 10 };
 11 void right_rotate(node *&ptr)
 12 {
 13     if (ptr->right_c->df==-1)
 14     {
 15         node * child = ptr->right_c;
 16         ptr->right_c = child ->left_c;
 17         child ->left_c = ptr;
 18         ptr->df = 0;
 19         child->df = 0;
 20         ptr = child;
 21     }
 22     else
 23     {
 24        node * child = ptr->right_c;
 25        node * g_child = child ->left_c;
 26        child ->left_c = g_child ->right_c;
 27        ptr->right_c = g_child -> left_c;
 28        g_child->left_c = ptr;
 29        g_child->right_c = child;
 30        switch(g_child->df)
 31        {
 32        case 0:ptr->df = 0;child->df =0;break;
 33        case 1:ptr->df = 0; child->df = -1;g_child->df = 0;break;
 34        case -1:ptr->df = 1; child->df = 0;g_child->df = 0;break;
 35        }
 36        ptr = g_child;
 37     }
 38 }
 39 void left_rotate(node *&ptr)
 40 {
 41     if (ptr->left_c->df==1) // LL型旋转
 42     {
 43         // ptr 的左二子成为老子 ptr成为其右儿子
 44         node * child = ptr->left_c;
 45         ptr->left_c = child ->right_c;
 46         child ->right_c = ptr;
 47         ptr->df = 0;
 48         child->df = 0;
 49         ptr = child;
 50     }
 51     else // LR型旋转
 52     {
 53        node * child = ptr->left_c; // L儿子
 54        node * g_child = child ->right_c; // LR 孙子
 55        
 56        // 孙子的两个儿子 根据 二叉查找树定义 分别给 child 和 ptr
 57        child ->right_c = g_child ->left_c;
 58        ptr->left_c = g_child -> right_c;
 59        //孙子成为老子
 60        g_child->right_c = ptr;
 61        g_child->left_c = child;
 62        //根据孙子的df调整各点
 63        switch(g_child->df)
 64        {
 65        case 0:ptr->df = 0;child->df =0;break; 
 66        case -1:ptr->df = 0; child->df = 1;g_child->df = 0;break;
 67        case 1:ptr->df = -1; child->df = 0;g_child->df = 0;break;
 68        }
 69        ptr = g_child;
 70     }
 71 }
 72 void avl_insert(node * &ptr ,int t,bool &if_b)
 73 {
 74     if (ptr == NULL) // 新节点
 75     {
 76         if_b = false;
 77         ptr = (node *)malloc(sizeof(node));
 78         ptr->df = 0;
 79         ptr->left_c = NULL;
 80         ptr->right_c = NULL;
 81         ptr->v = t;
 82     }
 83     else if (t > ptr->v) // 与左子树完全对称
 84     {
 85         avl_insert(ptr->right_c,t,if_b);
 86         if (!if_b)
 87         {
 88             switch(ptr->df)
 89             {
 90                 case 0:ptr->df = -1;break;
 91                 case 1:ptr->df = 0;if_b = true; break;
 92                 case -1:right_rotate(ptr);if_b = true;break;
 93             }
 94         }
 95     }
 96     else if (t < ptr->v) // 在左子树中加入
 97     {
 98         avl_insert(ptr->left_c,t,if_b);
 99         if (!if_b)
100         {
101             switch(ptr->df)
102             {
103                 case 0:ptr->df = 1;break;//不平衡
104                 case -1:ptr->df = 0;if_b = true; break; //恰好调节平衡
105                 case 1:left_rotate(ptr);if_b = true;break; //旋转后调节平衡
106             }
107         }
108     }
109     else // 找到元素
110     {
111         cout <<t <<"cunzai"<<endl;
112         if_b = true;
113         return;
114     }
115 }
116 void proorder(node * ptr) //中序遍历
117 {
118     if (ptr ==NULL) return;
119     proorder(ptr->left_c);
120     cout << ptr->v <<" ";
121     proorder(ptr->right_c);
122 }
123 int main()
124 {
125     int N;
126     cin >> N;
127     node* root = NULL;
128     bool if_b = false;
129     for (int i = 1 ; i<=N; i++)
130     {
131         int x;
132         cin >> x;
133         if_b = false;
134         avl_insert(root,x,if_b);
135     }
136     proorder(root);
137     cout <<endl;
138 }