数据结构 平衡二叉树

平衡二叉树（Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree）:是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1.
即左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1.二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor),那么平衡二叉树上所有结点的平衡因子只可能是-1,0和1.

距离插入结点最近的，切平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。

旋转规律：
    当最小不平衡子树根结点的平衡因子BF是大于1时，就右旋，小于-1就左旋。在插入结点后，最小不平衡子树的BF与它的子树的BF符号相反时，就需要对结点先进行一次旋转以使得符号相同后，再反向旋转一次才能够完成平衡操作。

一般情况下，假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a(即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行调整的规律可归纳为下列4种情况：
   (1) 单向右旋处理：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使*a为根的子树失去平衡，则需进行一次向右的顺时针旋转操作，操作过后的结果：左子树取代结点的位置，结点成为其右子树，左子树的右字树成为结点的左子树。
   (2) 单向左旋处理: 由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根结点的子树失去平衡，则需进行一次向左的逆时针旋转操作，操作过后，右子树取代结点的位置，结点成为其左子树，右子树的左子树成为结点的右子树。
   (3) 双向旋转(先左后右)平衡处理：由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根结点的子树失去平衡，则需进行两次旋转操作
 (先左旋后右旋)。
   (4) 双向旋转(先右后左)平衡处理:由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子有-1变成-2，致使*a为根结点的子树失去平衡，则需进行两次旋转(先右旋后左旋)操作。

在平衡二叉树BBST上插入一个新的数据元素e的递归算法可描述如下：
  (1)若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1；
  (2)若e的关键字和BBST的根结点的关键字相等，则不进行插入；
  (3)若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加(+1)时，分别就下列不同情况处理之：
  a： BBST的根节点的平衡因子为-1(右子树的深度大于左子树的深度)，则将根结点的平衡因子更改为0，BBST的深度不变。
  b： BBST的根节点的平衡因子为0(右子树的深度等于左子树的深度)，则将根结点的平衡因子更改为+1，BBST的深度增1。
  c： BBST的根结点的平衡因子为1(左子树的深度大于右子树的深度)：若BBST的左子树根结点的平衡因子为1，则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；

      #include <stdio.h>
      #include <stdlib.h>
      typedef int ElemType;
      typedef struct BSTNode
      {
      	ElemType data;
     	int bf;
     	struct BSTNode *lchild,*rchild;
      }BSTNode, *BiTree;
      /*对以*p为根的二叉排序树作右旋转处理，处理之后p指向新的树根结点，
       即旋转处理之前的左子树的根结点
       ⑥
       / \
       ④ ⑦ 插入② --->
       / \
       ③ ⑤
       ⑥
       / \
       ④ ⑦ 右旋转 --->
       / \
       ③ ⑤
       /
       ②
       ④
       / \
       ③ ⑥
       / / \
       ② ⑤ ⑦
      */
      void R_Rotate(BiTree &p)
      {
      	BiTree lc = p->lchild;  //示意图中的⑥为p，lc指向结点④
      	p->lchild = lc->rchild ; //④的右孩子⑤成为⑥的左孩子
      	lc->rchild = p; //⑥成为④的右孩子
      	p = lc; //p指向新的结点
      }
      /*对以*p为根的二叉排序树作左旋转处理，处理之后p指向新的树根结点，
       即旋转处理之前的右子树的根结点
       ⑥
       / \
       ⑤ ⑧ 插入⑩ --->
       / \
       ⑦ ⑨
       ⑥
       / \
       ⑤ ⑧ 左旋转 --->
       / \
       ⑦ ⑨
       \
       ⑩
       ⑧
       / \
       ⑥ ⑨
       / \ \
       ⑤ ⑦ ⑩
      */
      void L_Rotate(BiTree &p)
      {
      	BiTree rc = p->rchild;  //示意图中的⑥为p，lc指向结点⑧
      	p->rchild = rc->lchild; //⑧的左孩子⑦成为⑥的右孩子
      	rc->lchild = p; //⑥成为⑧的左孩子
      	p = rc; //p指向新的根结点
      }
      #define LH +1 /*左高*/
      #define EH 0 /*等高*/
      #define RH -1 /*右高*/
      #define TRUE 1
      #define FALSE 0
      /*
      对指针T所指向结点为根的二叉树作左平衡旋转处理
      本算法结束时，指针T指向新的根结点
      */
      void LeftBlance(BiTree &T)
      {
      	BiTree L,Lr;
      	L = T->lchild;   /* L指向T的左子树根结点*/
     	switch(L->bf)
      	{/*检查T的左子树的平衡度，并作相应平衡处理*/
     	case LH: /*新结点插入在T的左孩子的左子树上，符号相同，要作单右旋处理*/
      		T->bf = L->bf = EH;
      		R_Rotate(T);
     		break;
     	case RH: /*新结点插入在T的左孩子的右子树上，,符号不同，要做双旋处理*/
      		Lr = L->rchild; /*Lr指向T的左孩子的右子树根*/
     		switch(Lr->bf)  /*修改T及其左孩子的平衡因子*/
      		{
     		case LH:
      			T->bf = RH;
      			L->bf = EH;
     			break;
     		case EH:
      			T->bf = L->bf = EH;
     			break;
     		case RH:
      			T->bf = EH;
      			L->bf = LH;
     			break;
      		}
      		Lr->bf = EH;
      		L_Rotate(T->lchild);   /*对T的左子树作左旋平衡处理*/
      		R_Rotate(T); /*对T作右旋平衡处理*/
      	}
      }
      /*
      对指针T所指向结点为根的二叉树作右平衡旋转处理
      本算法结束时，指针T指向新的根结点
      */
      void RightBlance(BiTree &T)
      {
      	BiTree L,Ll;
      	L = T->rchild;   /* L指向T的右子树根结点*/
     	switch(L->bf)
      	{/*检查T的右子树的平衡度，并作相应平衡处理*/
     	case RH: /*新结点插入在T的右孩子的右子树上，符号相同，要作单右旋处理*/
      		T->bf = L->bf = EH;
      		L_Rotate(T);
     		break;
     	case LH: /*新结点插入在T的右孩子的左子树上，,符号不同，要做双旋处理*/
      		Ll = L->lchild; /*Lr指向T的右孩子的左子树根*/
     		switch(Ll->bf)  /*修改T及其右孩子的平衡因子*/
      		{
     		case RH:
      			T->bf = RH;
      			L->bf = EH;
     			break;
     		case EH:
      			T->bf = L->bf = EH;
     			break;
     		case LH:
      			T->bf = EH;
      			L->bf = LH;
     			break;
      		}
      		Ll->bf = EH;
      		R_Rotate(T->rchild);   /*对T的右子树作右旋平衡处理*/
      		L_Rotate(T); /*对T作左旋平衡处理*/
      	}
      }
      int InsertAVL(BiTree &T, int e, int &taller)
      {
     	if (!T)
      	{/*插入新结点，树长高，置taller为TRUE*/
      		T = (BiTree) malloc(sizeof(BSTNode));
      		T->data = e;
      		T->lchild = T->rchild = NULL;
      		T->bf = EH;
      		taller = TRUE;
      	}
     	else
      	{
     		if (e == T->data)
      		{
      			taller = FALSE;
     			return FALSE;
      		}
     		if (e < T->data)
      		{/*应继续在T的左子树中进行搜索*/
     			if (!InsertAVL(T->lchild,e,taller))/*未插入*/
      			{
      return FALSE;
      			}
     			if (taller)
      			{/* 已插入到T的左子树中且左子树"长高"*/
      switch( T->bf ) /*检查T的平衡度*/
       {
      case LH: /*原本左子树比右子树高，需要作左平衡处理*/
       LeftBlance(T);
       taller = FALSE;
      break;
      case EH:/*原本左右子树等高，现因左子树增高而树增高*/
       T->bf = LH;
       taller = TRUE;
      break;
      case RH: /*原本右子树比左子树高，现左右子树等高*/
       T->bf = EH;
       taller = FALSE;
      break;
       }
      			}
      		}
     		else
      		{/*应继续在T的右子树中进行搜索*/
     			if (!InsertAVL(T->rchild,e,taller))/*未插入*/
      			{
      return FALSE;
      			}
     			if (taller)
      			{/* 已插入到T的右子树中且右子树"长高"*/
      switch( T->bf ) /*检查T的平衡度*/
       {
      case LH: /*原本左子树比右子树高，现左右子树等高*/
       T->bf = EH;
       taller = FALSE;
      break;
      case EH:/*原本左右子树等高，现因右子树增高而树增高*/
       T->bf = RH;
       taller = TRUE;
      break;
      case RH: /*原本右子树比左子树高，现左右子树等高*/
       RightBlance(T);
       taller = FALSE;
      break;
       }
      			}
      		}
      	}
     	return TRUE;
      }
      void InOrderTraverse(BiTree T)
      {
     	if (T == NULL)
      	{
     		return;
      	}
      	InOrderTraverse(T->lchild);//访问左子树
     	printf("%d ",T->data);//访问根结点
      	InOrderTraverse(T->rchild);//访问右子树
      }
      int main()
      {
     	int i;
     	int a[] = {3,2,1,4,5,6,7,10,9,8,25,13,46,26,68,98,15,12};
      	BiTree T = NULL;
     	int taller;
     	for (i=0; i<(int)sizeof(a)/sizeof(a[0]); i++)
      	{
      		InsertAVL(T,a[i],taller);
      	}
      	InOrderTraverse(T);
     	printf("\n");
     	return 0;
      }
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/17287235