平衡二叉树的形成：

插入新结点导致失衡的原因主要分为：

1)LL型 2)RR型 3)LR型 4)RL型

在这行模型中，调整平衡是比较简单的，较为麻烦的是每个结点的平衡度(bf)的调整。

根据图分别分析以上四种情况以及解决办法：

1，LL型：

(12 为新插入的结点)，当新结点插入后，致使 30 的左子树的左子树升高1，而使 30 失衡(LL)：我们经过右旋使得二叉树恢复平衡。

右旋步骤：

1，让20的右子树(25)接在30的左子树上;

2，让20的右子树指向30;

3，让20称为根结点。

bf 的调整：30->bf = 0, 20->bf = 0

2，RR型

(45为新结点)当新结点插入后，致使 30 的右子树的右子树升高1，而使 30 失衡(RR)：我们经过左旋使得二叉树恢复平衡。

左旋步骤：

1，让40的左子树(35)接在30的右子树上;

2，让40的左子树指向30;

3，让40称为根结点。

bf 的调整：30->bf = 0, 40->bf = 0;

3，LR型

LR型中又分为三种：(rc->bf = 1, 0, -1)

调整平衡(对于三种情况都一样)：先以20作为调整平衡最高结点 ，进行左旋，再以30作为调整平衡的最高结点，进行右旋。

bf 的调整：

1)rc->bf = 1

rc(25)->bf = 0; 30->bf = -1; 20->bf = 0;

2)rc->bf = 0

rc(25)->bf = 0; 30->bf = 0; 20->bf = 0;

3)rc->bf = -1

rc(25)->bf = 0; 30->bf = 0; 20->bf = 1;

3，RL型

Rl型中也分为三种：(rc->bf = 1, 0, -1)

调整平衡(对于三种情况都一样)：先以40作为调整平衡最高结点 ，进行右旋，再以30作为调整平衡的最高结点，进行左旋。

bf 的调整：

1)lc->bf = 1

lc(25)->bf = 0; 30->bf = 0; 40->bf = -1;

2)lc->bf = 0

lc(25)->bf = 0; 30->bf = 0; 40->bf = 0;

3)lc->bf = -1

lc(25)->bf = 0; 30->bf = 1; 40->bf = 0;

根据提示以及图解，相信你会理解平衡二叉树插入的真髓!

#define _CRT_SECURE_NO_WARNINGS
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             using namespace std; #define LH 1 //左子树比右子树高1 #define EH 0 //左右子树一样高 #define RH -1 //左子树比右子树低1 struct BSTNode { int data; int bf; BSTNode *lchild; BSTNode *rchild; }; typedef BSTNode* BSTree; //左旋 逆时针 void leftRotate (BSTree &root) { BSTree rc = root->rchild; root->rchild = rc->lchild; rc->lchild = root; root = rc; } //右旋 顺时针 void rightRotate (BSTree &root) { BSTree lc = root->lchild; root->lchild = lc->rchild; lc->rchild = root; root = lc; } //对二叉树 root 进行左平衡处理（LL型和LR型） void leftBalance (BSTree &root) { BSTree lc = root->lchild; switch(lc->bf) { //LL型只需要进行右旋操作 case LH: //右旋之后根和左子树都是平衡的 root->bf = EH; lc->bf = EH; rightRotate (root); break; //LR型的需要进行左旋操作，然后进行右旋操作 case RH: BSTree rc = lc->rchild; switch(rc->bf) { case LH: root->bf = RH; lc->bf = EH; break; case EH: root->bf = EH; lc->bf = EH; break; case RH: root->bf = EH; lc->bf = LH; break; } rc->bf = EH; leftRotate (lc); rightRotate (root); break; } } //对二叉树 root 进行左平衡处理（RR型 和 RL型） void rightBalance (BSTree & root) { BSTree rc = root->rchild; switch(rc->bf) { //RR型只需做左旋操作 case RH: root->bf = EH; rc->bf = EH; //左旋操作 leftRotate (root); break; //RL型需先做右旋操作， 然后做左旋操作 case LH: BSTree lc = rc->lchild; switch(lc->bf) { case LH: root->bf = EH; rc->bf = RH; break; case EH: root->bf = EH; rc->bf = EH; break; case RH: root->bf = EH; rc->bf = EH; break; } lc->bf = EH; rightRotate (rc); leftRotate (root); break; } } // 把元素 data 插入平衡二叉树中 bool insert (BSTree & root, int data, bool & taller) { if(NULL == root) { root = (BSTree)malloc (sizeof (BSTNode)); root->lchild = NULL; root->rchild = NULL; root->bf = EH; root->data = data; taller = true; } else { //该元素已存在平衡二叉树中 if(data == root->data) { taller = false; return false; } //插入左子树 else if(data < root->data) { if(!insert(root->lchild, data, taller)) { return false; } //插入成功 if(taller) { switch(root->bf) { case LH: leftBalance (root); taller = false; //平衡二叉树做完左平衡操作后，树高没有变化 break; case EH: root->bf = LH; taller = true; //原来是平衡的顾插入一个元素后，树高必然变高 break; case RH: root->bf = EH; taller = false; //原来是右子树比左子树高，向左子树中插入一个元素的时候，树变平衡了 break; } } } //插入右子树 else { if(!insert(root->rchild, data, taller)) { return false; } if(taller) { switch(root->bf) { case LH: root->bf = EH; taller = false; break; case EH: root->bf = RH; talle