平衡二叉树 平衡二叉树怎么旋转

平衡二叉树 AVL树

1.平衡因子:二叉排序树中Balance Fector(BF)=|左子树的深度-右子树的深度|

2.平衡二叉树的性质

(1)树中节点的BF<=1

(2)左右子树都是平衡二叉树


3.平衡二叉树的构造

最小不平衡树:每插入一个结点后,首先检查是否破坏了树的平衡性,如果因插入结点而破坏了二叉查找树的平衡,则找出离插入点最近的不平衡结点,然后将该不平衡结点为根的子树进行旋转操作,我们称该不平衡结点为旋转根,以该旋转根为根的子树称为最小不平衡子树。

失衡状态可归纳为4种,它们对应着4种旋转类型:

LL型旋转:插入新节点5

RR旋转:插入新节点90


LR(L)旋转:插入新节点32


LR(R)旋转:插入新节点46


RL(L)旋转:插入新节点32


RL(R)旋转:插入新节点43


当旋转根的BF值为2时:

如果旋转根的左孩子的BF值为1,则进行LL型旋转;

如果旋转根的左孩子的BF值为-1,则进行LR型旋转。

当旋转根的BF值为-2时:

如果旋转根的右孩子的BF值为1,则进行RL型旋转;

如果旋转根的右孩子的BF值为-1,则进行RR型旋转。

4.代码实现

publicclass BinarySearchTree : IBinaryTree //实现画树接口
{//成员变量
private Node_head; //头指针
private Node[]path = new Node[32];//记录访问路径上的结点
private int p;//表示当前访问到的结点在_path上的索引
INodeIBinaryTree.Head //显式接口实现
{
get {return (INode)_head; }
}
publicbool Add(intvalue) //添加一个元素
{//如果是空树,则新结点成为二叉排序树的根
if (_head == null)
{
_head = new Node(value);
_head.BF = 0;
return true;
}
p = 0;
//prev为上一次访问的结点,current为当前访问结点
Nodeprev = null,current = _head;
while (current != null)
{
path[p++] =current; //将路径上的结点插入数组
//如果插入值已存在,则插入失败
if (current.Data == value)
{
returnfalse;
}
prev = current;
//当插入值小于当前结点,则继续访问左子树,否则访问右子树
current = (value <</SPAN> prev.Data) ? prev.Left :prev.Right;
}
current = new Node(value); //创建新结点
current.BF = 0;
if (value <</SPAN> prev.Data) //如果插入值小于双亲结点的值
{
prev.Left = current; //成为左孩子
}
else //如果插入值大于双亲结点的值
{
prev.Right =current; //成为右孩子
}
path[p] = current; //将新元素插入数组path的最后
//修改插入点至根结点路径上各结点的平衡因子
int bf= 0;
while (p >0)
{ //bf表示平衡因子的改变量,当新结点插入左子树,则平衡因子+1
//当新结点插入右子树,则平衡因子-1
bf = (value <</SPAN> path[p - 1].Data) ? 1: -1;
path[--p].BF += bf;//改变当父结点的平衡因子
bf =path[p].BF; //获取当前结点的平衡因子
//判断当前结点平衡因子,如果为0表示该子树已平衡,不需再回溯
//而改变祖先结点平衡因子,此时添加成功,直接返回
if (bf ==0)
{
returntrue;
}
else if (bf== 2 ||bf == -2)//需要旋转的情况
{
RotateSubTree(bf);
return true;
}
}
returntrue;
}
//删除指定值
public bool Remove(int value)
{
p = -1;
//parent表示双亲结点,node表示当前结点
Nodenode = _head;
//寻找指定值所在的结点
while (node != null)
{
path[++p] =node;
//如果找到,则调用RemoveNode方法删除结点
if (value == node.Data)
{
RemoveNode(node);//现在p指向被删除结点
return true;//返回true表示删除成功
}
if (value <</SPAN> node.Data)
{ //如果删除值小于当前结点,则向左子树继续寻找
node =node.Left;
}
else
{ //如果删除值大于当前结点,则向右子树继续寻找
node =node.Right;
}
}
returnfalse; //返回false表示删除失败
}
//删除指定结点
private void RemoveNode(Node node)
{
Node tmp = null;
//当被删除结点存在左右子树时
if (node.Left != null&& node.Right != null)
{
tmp = node.Left; //获取左子树
path[++p]= tmp;
while (tmp.Right != null)//获取node的中序遍历前驱结点,并存放于tmp中
{//找到左子树中的最右下结点
tmp =tmp.Right;
path[++p] =tmp;
}
//用中序遍历前驱结点的值代替被删除结点的值
node.Data = tmp.Data;
if (path[p - 1]== node)
{
path[p - 1].Left= tmp.Left;
}
else
{
path[p - 1].Right = tmp.Left;
}
}
else //当只有左子树或右子树或为叶子结点时
{//首先找到惟一的孩子结点
tmp =node.Left;
if (tmp== null)//如果只有右孩子或没孩子
{
tmp = node.Right;
}
if (p >0)
{
if (path[p - 1].Left== node)
{ //如果被删结点是左孩子
path[p - 1].Left= tmp;
}
else
{ //如果被删结点是右孩子
path[p - 1].Right = tmp;
}
}
else //当删除的是根结点时
{
_head = tmp;
}
}
//删除完后进行旋转,现在p指向实际被删除的结点
int data =node.Data;
while (p >0)
{ //bf表示平衡因子的改变量,当删除的是左子树中的结点时,平衡因子-1
//当删除的是右子树的孩子时,平衡因子+1
int bf =(data <= path[p - 1].Data) ? -1: 1;
path[--p].BF += bf;//改变当父结点的平衡因子
bf =path[p].BF; //获取当前结点的平衡因子
if (bf!= 0)//如果bf==0,表明高度降低,继续后上回溯
{
//如果bf为1或-1则说明高度未变,停止回溯,如果为2或-2,则进行旋转
//当旋转后高度不变,则停止回溯
if (bf ==1 || bf== -1|| !RotateSubTree(bf))
{
break;
}
}
}
}
//旋转以root为根的子树,当高度改变,则返回true;高度未变则返回false
private bool RotateSubTree(int bf)
{
bool tallChange = true;
Node root = path[p], newRoot = null;
if (bf== 2)//当平衡因子为2时需要进行旋转操作
{
int leftBF = root.Left.BF;
if (leftBF == -1)//LR型旋转
平衡二叉树 平衡二叉树怎么旋转
{
newRoot = LR(root);
}
else if (leftBF == 1)
{
newRoot = LL(root); //LL型旋转
}
else //当旋转根左孩子的bf为0时,只有删除时才会出现
{
newRoot = LL(root);
tallChange =false;
}
}
if (bf ==-2)//当平衡因子为-2时需要进行旋转操作
{
int rightBF = root.Right.BF; //获取旋转根右孩子的平衡因子
if (rightBF == 1)
{
newRoot = RL(root); //RL型旋转
}
else if(rightBF == -1)
{
newRoot = RR(root); //RR型旋转
}
else //当旋转根左孩子的bf为0时,只有删除时才会出现
{
newRoot = RR(root);
tallChange =false;
}
}
//更改新的子树根
if (p> 0)
{
if (root.Data <</SPAN> path[p - 1].Data)
{
path[p - 1].Left= newRoot;
}
else
{
path[p - 1].Right = newRoot;
}
}
else
{
_head = newRoot; //如果旋转根为AVL树的根,则指定新AVL树根结点
}
return tallChange;
}
//root为旋转根,rootPrev为旋转根双亲结点
private NodeLL(Node root) //LL型旋转,返回旋转后的新子树根
{
Node rootNext =root.Left;
root.Left = rootNext.Right;
rootNext.Right =root;
if (rootNext.BF == 1)
{
root.BF = 0;
rootNext.BF =0;
}
else //rootNext.BF==0的情况,删除时用
{
root.BF = 1;
rootNext.BF =-1;
}
returnrootNext; //rootNext为新子树的根
}
private NodeLR(Node root) //LR型旋转,返回旋转后的新子树根
{
Node rootNext =root.Left;
Node newRoot =rootNext.Right;
root.Left = newRoot.Right;
rootNext.Right =newRoot.Left;
newRoot.Left =rootNext;
newRoot.Right =root;
switch (newRoot.BF) //改变平衡因子
{
case 0:
root.BF = 0;
rootNext.BF =0;
break;
case 1:
root.BF = -1;
rootNext.BF =0;
break;
case -1:
root.BF = 0;
rootNext.BF =1;
break;
}
newRoot.BF =0;
return newRoot; //newRoot为新子树的根
}
private NodeRR(Node root) //RR型旋转,返回旋转后的新子树根
{
Node rootNext =root.Right;
root.Right =rootNext.Left;
rootNext.Left =root;
if (rootNext.BF == -1)
{
root.BF = 0;
rootNext.BF =0;
}
else //rootNext.BF==0的情况,删除时用
{
root.BF = -1;
rootNext.BF =1;
}
returnrootNext; //rootNext为新子树的根
}
private NodeRL(Node root) //RL型旋转,返回旋转后的新子树根
{
Node rootNext =root.Right;
Node newRoot =rootNext.Left;
root.Right =newRoot.Left;
rootNext.Left =newRoot.Right;
newRoot.Right =rootNext;
newRoot.Left =root;
switch (newRoot.BF) //改变平衡因子
{
case 0:
root.BF = 0;
rootNext.BF =0;
break;
case 1:
root.BF = 0;
rootNext.BF =-1;
break;
case -1:
root.BF = 1;
rootNext.BF =0;
break;
}
newRoot.BF =0;
return newRoot; //newRoot为新子树的根
}
}







  

爱华网本文地址 » http://www.413yy.cn/a/25101017/356145.html

更多阅读

如何扫描二维码 手机扫描二维码怎么用

如何扫描二维码——简介二维码可以印刷在报纸、杂志、广告、图书、包装等多种载体上,用户通过手机摄像头如何扫描二维码_扫描二维码如何扫描二维码——二、微信端(安卓版)如何扫描二维码 1、依次选择微信端“发现”->“扫一扫”。如

微信如何创建个人二维码 怎么创建微信二维码

微信如何创建个人二维码——简介现在二维码随处可见;网站,商品、促销单页;明星片都可以;我们如何创建个人二维码信息;让别人扫一下就可以加我们好有呢;大部分朋友可能都知道;这里就和还没发现的朋友分享一下微信如何创建个人二维码——方

发财树花卉养殖方法 小盆栽发财树怎么养

发财树花卉养殖方法——简介发财树寓意喜庆,深受广大业主们的喜爱。发财树四季常绿,体形优美,用于美化厅、堂、宅,有“发财”之寓意,以图吉祥如意。发财树净化室内空气、吸收甲醛等有害气体方面可以起到很好的效果。发财树花卉养殖方法

米兰花怎么养 幸福树怎么养才茂盛

米兰为楝科常绿灌木至小乔木。 分枝多,叶为奇数羽状复叶,小叶3-5枚,倒卵形,深绿色。圆锥花序腋生,花细小而繁密,黄色,清香。四季开花。 米兰喜湿润肥沃、疏松的壤土或砂壤土,以略呈酸性为宜。盆土可用25%堆肥、50%腐叶土、25%河砂混合配制。

声明:《平衡二叉树 平衡二叉树怎么旋转》为网友末世岛域分享!如侵犯到您的合法权益请联系我们删除