（4.5）树与二叉树之AVL树

本文主要是介绍（4.5）树与二叉树之AVL树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.构造二叉排序树以及求出查找成功的平均查找长度

• （1）已知输入序列1，2，3，4，5，请构造二叉排序树，并求出查找成功的平均查找长度
  先放节点1，节点2比1大，应该是其右子树，比2大(这个节点是空的)，是其右子树，。。节点4比1大，是其右子树，比2大，是其右子树，比3大，是其右子树，比4大(这个节点是空的)，
  

• （2）输入序列3，1，2，4，5，请构造二叉排序树，并求出查找成功的平均查找长度
  先放入节点3，节点1比3小，是其左子树，节点2，比3小，是其左子树，比1大，是其右子树，比节点2大(节点是空的)，是其右子树。。。。以此类推
  

2.平衡二叉树的定义

• 平衡二叉树或者是一颗空树，或者是具有下列性质的二叉排序数：
  （1）它的左、右子树都是平衡二叉树
  （2）并且左、右子树的深度之差不超过1
  （3）（a）中63节点的深度差计算：4-5=-1
  

• eg：若一颗平衡二叉树不平衡了，该如何调整？所有的不平衡状态可能有哪些？
  每次插入一个节点都要保证他是二叉排序树的定义，所以需要旋转。
  下面的LL，LR，RL，RR都是在一颗平衡的二叉树上，增加一个节点而不平衡的。插入后，对于节点A而言，二叉树的高度由1（左子树高度为1，右子树高度为0）->2or-2，，高度值发生了变化，所以需要单旋或者多旋。
  （1）LL型和RR型类似：将中间值B右旋成为上面的点，树高由3->2，RR型左旋。
  LL型为例，因为中间的比A小，比B大，所以右旋的结果满足二叉排序树的定义，啥都不变。RR型类似
  （2）LR型和LL型类似：中间值是c，需要2次旋转
  LL型为例，因为节点C比节点A大，比节点B小，所以2次旋转后A为B的左子树，B为A的右子树，旋转过后还是满足二叉排序树的定义！
  

• 代码

AvlTree Insert(Elementype X, AvlTree T)
{if (T==NULL){T=malloc(sizeof(struct AvlNode));if (T==NULL)FatalError("Out of space!!!");else{T->Element=X;T->Height=0;T->left=T->right=NULL;}}else if (X<T->Element){}else if (X>T->Element){}T->Height=Max(Heigh(T->Left),Height(T->Right))+1;return T;
}=============================================================================
接着else if (X<T->Element)，左子树的插入操作
else if(X<T-Element)
{T->Left=Insert(X,T->Left);//成为当前节点的左孩子if (Height(T->Left) - Height(T->Right) == 2){if (X<T->Left->Element)//LL型T=SingleRotateWithLeft(T);else			//LR型T=doubleRotateWithLeft(T);}
else if (X>T->Element)//接着else if (X>T->Element)，右子树的插入操作
{T->Right=Insert(X,T->Right);//成为当前节点的右孩子if (Height(T->Right) - Height(T->Left) == 2){if (X>T->Left->Element)//RR型T=SingleRotateWithRight(T);else			//RL型T=doubleRotateWithRight(T);}
}================================================
SingleRotateWithLeft的代码如下：
AvlTree SingleRotateWithLeft(AvlTree T)
{AvlTree pt=T,pT2=T->Left->Right;T-T->T->Left;//新根T->Right=pT;pt->Left=pT2;return T;
}
//将B作为中间节点，进行旋转

这篇关于（4.5）树与二叉树之AVL树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---