AVL平衡二叉树的插入

---

算法精髓：

自底向上方法，高层依赖底层的max(left->height,right->height)+1。利用递归记忆性由低到高沿着来时的路回退修正insert后的树高来替代栈。

---

四种插入方法：

LL,LR,RL,RR四种：

1. LL

//  左支过重  
void R(Node*&root){
  Node* temp=root->left;
  root->left=temp->right;
  temp->right=root;
  // 因为C还有菱形下面的深度没有改变，所以先算A的新深度，再算新根节点B的深度。
  updateheight(root);
  update(temp);
  // 最后调换root指向B，结束操作。
  root=temp;
}

if(getbalancevalue(root)==2){
  // 出现不平衡，且是LL
  if(getbalancevalue(root->left)==1){
    R(root);
  }
}

image.png

---

2. LR

void L(Node*&root)
{
  Node* temp=root->right;
  root->right=temp->left;
  temp->left=root;
  updateheight(root);
  updateheight(temp);
  root=temp;
}

if(getbalancevalue(root)==2){
  // 出现不平衡，且是LR
  if(getbalancevalue(root->left)==-1){
    // 先把左子树左旋，变成上一种情况如何再右旋。
    L(root->left);
    R(root);
  }
}

image.png

---

3.RL

if(getbalancevalue(root)==-2){
  // 出现不平衡，且是RL
  if(getbalancevalue(root->left)==1){
    // 先把右子树右旋，变成下一种情况如何再左旋。
    R(root->right);
    L(root);
  }
}

4.RR

if(getbalancevalue(root)==-2){
  // 出现不平衡，且是RR
  if(getbalancevalue(root->left)==-1){
    // 把右子树左旋
    L(root);
  }
}