平衡二叉树构造
上一篇:二叉排序树----添加，删除，修改，查询
平衡二叉树也即AVL树,他可以提高查找的效率，像并查集的构建过程就用到了平衡二叉树的平衡因子特点(不是平衡二叉树啊)，满足任意节点的左子树的深度减去右子树的深度的值之差(称之为平衡因子)绝对值小于等于1，那么这棵二叉树为平衡二叉树。
在构建过程中会发生左旋与右旋的现象，那么当平衡因子大于1就右旋，平衡因子小于-1就左旋
举例看一下右旋:
左旋就是节点绕着他的右子树根节点逆时针旋转，右旋就是节点绕着他的左子树根节点顺时针旋转
下面进入正式的代码阶段
1.定义节点
class Tree
{
int value;//存储值
int bf;//存储平衡因子
Tree left,right;//左右子树
//初始化一个节点
Tree(int value)
{
this.value = value;
this.bf = 0;
this.left=this.right=null;
}
}
接下来的所有代码都在类AVL中，他有成员boolean taller,Tree root;
2.实现左旋与右旋
//parent是当前要旋转的节点root的父节点,L_or_R的值为-1，代表parent的左节点指向
//root,,L_or_R的值为1，代表parent的y右节点指向root
void left_rotate(Tree root,Tree parent,int L_or_R)//左旋
{
Tree right_node = root.right;
Tree temp = right_node.left;
right_node.left = root;
root.right = temp;
if(L_or_R==-1&&parent!=null)
parent.left = right_node;
else if(L_or_R==1&&parent!=null)
parent.right = right_node;
}
//parent是当前要旋转的节点root的父节点
void right_rotate(Tree root,Tree parent,int L_or_R)//右旋
{
Tree left_node = root.left;
Tree temp = left_node.right;
left_node.right=root;
root.left=temp;
if(L_or_R==-1&&parent!=null)
parent.left = left_node;
else if(L_or_R==1&&parent!=null)
parent.right = left_node;
}
3.leftBalance与rightBalance的实现
//当调用这个函数是说明root.bf=2了
void leftBalance(Tree root,Tree parent,int L_or_R)
{
switch (root.left.bf)
{
/*
这里要解释一下为什么不看左子树平衡因子为0
首先要明白root对应的树是最小不平衡子树
root不平衡是因为他的左子树加了一个节点使得左子树
深度+1，现在我们分情况讨论:记左子树的根节点为left_node
①left_node.bf原来为-1,那么这要在left_node的左子树上加上节点
使得left_node.bf=0,但这样导致左子树深度没有+1，矛盾
②left_node.bf原来为0,无论怎么加节点，都无法维持其为0
③left_node.bf原来为1，那么这要在left_node的右子树上加上节点
使得left_node.bf=0,但这样导致左子树深度没有+1，矛盾
*/
//平衡因子为1,见下面的第一张图
case 1:
root.left.bf=root.bf=0;
right_rotate(root,parent,L_or_R);
break;
//平衡因子为-1
case -1:
switch (root.left.right.bf)
{
case 1://见下面的第二张图
root.bf=-1;
root.left.bf=0;
break;
case -1://见下面的第三张图
root.left.bf=1;
root.bf=0;
break;
case 0:
root.left.bf=root.bf=0;
}
root.left.right.bf = 0;
left_rotate(root.left,root,-1);
right_rotate(root,parent,L_or_R);
break;
}
}
void rightBalance(Tree root,Tree parent,int L_or_R)
{
switch(root.right.bf)
{
case -1:
root.right.bf=root.bf=0;
left_rotate(root,parent,L_or_R);
break;
case 1:
switch (root.right.left.bf)
{
case -1:
root.bf=1;
root.right.bf=0;
break;
case 1:
root.bf=0;
root.right.bf=-1;
break;
case 0:
root.bf=root.right.bf=0;
break;
}
root.right.left.bf=0;
right_rotate(root.right,root,1);
left_rotate(root,parent,L_or_R);
break;
}
}
4.插入节点(重难点)
//返回值为真代表插入成功,返回值为假代表插入失败
//root代表要插入的平衡树的根节点
//value代表要插入的节点的值
//taller代表插入后root的深度是否变大,且在整个递归中沿用同一个taller,故必须使用taller为全局变量
boolean insert_node(Tree root ,int value ,Tree parent,int L_or_R)
{
//递归出口在这里，当递归到尽头时，必然会是root为null
if(root==null)
{
if(L_or_R==-1)
parent.left = new Tree(value);
else
parent.right = new Tree(value);
taller = true;
}
else
{
//判断value是否已经存在了,在递归中自然会把可能相等的点遍历到
if(root.value==value)
{
taller = false;//没有插入自然高度没有变化
return false;
}
else
{
if(value<root.value)
{
//未插入
if(!insert_node(root.left,value,root,-1))
{
return false;
}
else
{
if(taller)
{
switch (root.bf)
{
case 1:
leftBalance(root,parent,L_or_R);
taller = false;
break;
case -1:
taller = false;
root.bf=0;
break;
case 0:
taller=true;
root.bf=1;
break;
}
}
}
}
else
{
//未插入
if(!insert_node(root.right,value,root,1))
{
return false;
}
else
{
if(taller)
{
switch (root.bf)
{
case 1:
root.bf=0;
taller = false;
break;
case -1:
taller = false;
rightBalance(root,parent,L_or_R);
break;
case 0:
taller=true;
root.bf=-1;
break;
}
}
}
}
}
}
//运行到这一步说明插入成功，否则前面已经插入失败了返回了
return true;
}
5.正式插入
void Insert_AllNodes(int[] arr)
{
Tree root1 = new Tree(1);//创建这个的原因是为了防止调用insert_node由于整棵树的根节点parent为空发生空指针异常
for (int i : arr) {
insert_node(root1.left,i,root1,-1);
}
root = root1.left;//这里的root是AVL类的全局root
}
6.测试
@Test
public void Test()
{
int[] arr ={3,2,1,4,5,6,7,10,9,8};
Insert_AllNodes(arr);
FirstTransfer(root);
MiddleTransfer(root);
}
void MiddleTransfer(Tree node)
{
if(node!=null)
{
MiddleTransfer(node.left);
System.out.println(node.value);
MiddleTransfer(node.right);
}
}
void FirstTransfer(Tree node)
{
if(node!=null)
{
System.out.println(node.value);
FirstTransfer(node.left);
FirstTransfer(node.right);
}
}
最终完整版代码:
import org.junit.Test;
public class AVL {
boolean taller = true;
Tree root;
//parent是当前要旋转的节点root的父节点,L_or_R的值为-1，代表parent的左节点指向
//root,,L_or_R的值为1，代表parent的y右节点指向root
void left_rotate(Tree root,Tree parent,int L_or_R)//左旋
{
Tree right_node = root.right;
Tree temp = right_node.left;
right_node.left = root;
root.right = temp;
if(L_or_R==-1&&parent!=null)
parent.left = right_node;
else if(L_or_R==1&&parent!=null)
parent.right = right_node;
}
//parent是当前要旋转的节点root的父节点
void right_rotate(Tree root,Tree parent,int L_or_R)//右旋
{
Tree left_node = root.left;
Tree temp = left_node.right;
left_node.right=root;
root.left=temp;
if(L_or_R==-1&&parent!=null)
parent.left = left_node;
else if(L_or_R==1&&parent!=null)
parent.right = left_node;
}
//当调用这个函数是说明root.bf=2了
void leftBalance(Tree root,Tree parent,int L_or_R)
{
switch (root.left.bf)
{
/*
这里要解释一下为什么不看左子树平衡因子为0
首先要明白root对应的树是最小不平衡子树
root不平衡是因为他的左子树加了一个节点使得左子树
深度+1，现在我们分情况讨论:记左子树的根节点为left_node
①left_node.bf原来为-1,那么这要在left_node的左子树上加上节点
使得left_node.bf=0,但这样导致左子树深度没有+1，矛盾
②left_node.bf原来为0,无论怎么加节点，都无法维持其为0
③left_node.bf原来为1，那么这要在left_node的右子树上加上节点
使得left_node.bf=0,但这样导致左子树深度没有+1，矛盾
*/
//平衡因子为1,见下面的第一张图
case 1:
root.left.bf=root.bf=0;
right_rotate(root,parent,L_or_R);
break;
//平衡因子为-1
case -1:
switch (root.left.right.bf)
{
case 1://见下面的第二张图
root.bf=-1;
root.left.bf=0;
break;
case -1://见下面的第三张图
root.left.bf=1;
root.bf=0;
break;
case 0:
root.left.bf=root.bf=0;
}
root.left.right.bf = 0;
left_rotate(root.left,root,-1);
right_rotate(root,parent,L_or_R);
break;
}
}
void rightBalance(Tree root,Tree parent,int L_or_R)
{
switch(root.right.bf)
{
case -1:
root.right.bf=root.bf=0;
left_rotate(root,parent,L_or_R);
break;
case 1:
switch (root.right.left.bf)
{
case -1:
root.bf=1;
root.right.bf=0;
break;
case 1:
root.bf=0;
root.right.bf=-1;
break;
case 0:
root.bf=root.right.bf=0;
break;
}
root.right.left.bf=0;
right_rotate(root.right,root,1);
left_rotate(root,parent,L_or_R);
break;
}
}
//返回值为真代表插入成功,返回值为假代表插入失败
//root代表要插入的平衡树的根节点
//value代表要插入的节点的值
//taller代表插入后root的深度是否变大,且在整个递归中沿用同一个taller,故必须使用taller为全局变量
boolean insert_node(Tree root ,int value ,Tree parent,int L_or_R)
{
//递归出口在这里，当递归到尽头时，必然会是root为null
if(root==null)
{
if(L_or_R==-1)
parent.left = new Tree(value);
else
parent.right = new Tree(value);
taller = true;
}
else
{
//判断value是否已经存在了,在递归中自然会把可能相等的点遍历到
if(root.value==value)
{
taller = false;//没有插入自然高度没有变化
return false;
}
else
{
if(value<root.value)
{
//未插入
if(!insert_node(root.left,value,root,-1))
{
return false;
}
else
{
if(taller)
{
switch (root.bf)
{
case 1:
leftBalance(root,parent,L_or_R);
taller = false;
break;
case -1:
taller = false;
root.bf=0;
break;
case 0:
taller=true;
root.bf=1;
break;
}
}
}
}
else
{
//未插入
if(!insert_node(root.right,value,root,1))
{
return false;
}
else
{
if(taller)
{
switch (root.bf)
{
case 1:
root.bf=0;
taller = false;
break;
case -1:
taller = false;
rightBalance(root,parent,L_or_R);
break;
case 0:
taller=true;
root.bf=-1;
break;
}
}
}
}
}
}
//运行到这一步说明插入成功，否则前面已经插入失败了返回了
return true;
}
void Insert_AllNodes(int[] arr)
{
Tree root1 = new Tree(1);
for (int i : arr) {
insert_node(root1.left,i,root1,-1);
}
root = root1.left;
}
@Test
public void Test()
{
int[] arr ={3,2,1,4,5,6,7,10,9,8};
Insert_AllNodes(arr);
FirstTransfer(root);
MiddleTransfer(root);
}
void MiddleTransfer(Tree node)
{
if(node!=null)
{
MiddleTransfer(node.left);
System.out.println(node.value);
MiddleTransfer(node.right);
}
}
void FirstTransfer(Tree node)
{
if(node!=null)
{
System.out.println(node.value);
FirstTransfer(node.left);
FirstTransfer(node.right);
}
}
}
class Tree
{
int value;//存储值
int bf;//存储平衡因子
Tree left,right;//左右子树
//初始化一个节点
Tree(int value)
{
this.value = value;
this.bf = 0;
this.left=this.right=null;
}
}