定义：平衡二叉树是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。
平衡二叉树的前提是一棵二叉排序树，二叉排序树的查找性能受树的形状影响较大，所以需要对二叉排序树进行平衡处理，常见的方法有AVL、红黑树、Treap等。
平衡因子：平衡二叉树上每个结点的左子树深度减去右子树深度的值称为该结点的平衡因子。平衡因子的取值只能为0、-1、1。
最小不平衡子树：距离插入结点最近的，且以平衡因子的绝对值大于1的结点为根结点的子树。
平衡二叉树调整过程：
①当最小不平衡子树根结点的平衡因子大于1时，该子树右旋。如图1-1。
②当最小不平衡子树根结点的平衡因子小于-1时，该子树左旋。如图1-3、1-5、1-7。
③插入结点后，最小不平衡子树的平衡因子与它的子树的平衡因子符号相反时，需要对它的子树先进行一次旋转，再对它本身反向旋转一次才能完成平衡操作。如图1-9、1-11。
通过数组{3,2,1,4,5,6,7,10,9,8}演示二叉平衡树的构建过程，结点上方数字代表平衡因子。虚线框代表最小不平衡子树。
按顺序插入3,2时，3的平衡因子为1,2的平衡因子为0。继续插入1时，3的平衡因子为2，需要右旋。
图1-1.png
插入结点4,5，此时结点3的平衡因子为-2，需要左旋处理。
图1-2.png
对最小不平衡子树进行左旋处理。
图1-3.png
插入结点6，根结点2的平衡因子为-2，需要左旋。
图1-4.png
对最小不平衡子树左旋处理。
图1-5.png
插入结点7。结点5的平衡因子为-2，需要左旋。
图1-6.png
对最小不平衡子树进行左旋处理。
图1-7.png
插入结点10,9，此时最小不平衡树的根结点7的平衡因子为-2，其子结点的平衡因子为1，符号不同，所以需要对以10为根结点的子树进行右旋，再对最小不平衡子树进行左旋处理。
图1-8.png
对最小不平衡树先右旋再左旋处理。
图1-9.png
插入结点8，此时最小不平衡子树的根结点6的平衡因子为-2，其子树的根结点9的平衡因子为1，符号不同，所以需要先对以9为根结点的子树进行右旋处理，再对最小不平衡子树进行左旋处理。
图1-10.png
对最小不平衡树先右旋再左旋处理。
图1-11.png
代码实现
结点类：
/**
* @author 作者 Shaw:
* @version 创建时间：2018年12月11日 上午10:10:33
* 类说明:二叉平衡树结点类
*/
class AvlNode {
// 数据域
public int data;
// 平衡因子
public int balance = 0;
// 左右孩子结点
public AvlNode lchild, rchild;
// 父母结点
public AvlNode parent;
public AvlNode() {
}
public AvlNode(int data, AvlNode parent) {
this.data = data;
this.parent = parent;
}
}
平衡二叉树核心类：
/**
* @author 作者 Shaw:
* @version 创建时间：2018年12月11日 上午10:26:33
* 类说明:平衡二叉树类
*/
class BinaryBalanceTree {
//根结点
public AvlNode root;
//结点树
private int size = 0;
//平衡因子的三种取值
private static final int Left_High = 1;
private static final int Equal_High = 0;
private static final int Right_High = -1;
public BinaryBalanceTree() {
root = null;
}
//二叉平衡树插入结点
public boolean insertAVL(int value) {
AvlNode current = root;
// 空树情况
if (current == null) {
root = new AvlNode(value, null);
size = 1;
return true;
}
//插入的结点已存在时直接返回
if (search_AVL(value)) {
return false;
}
AvlNode parent = null;
// while循环找到待插入结点的父结点
while (current != null) {
parent = current;
if (value < current.data) {
current = current.lchild;
} else if (value > current.data) {
current = current.rchild;
} else {
break;
}
}
// 每插入一个结点，都需要调整该结点的父结点以及父结点的父结点的平衡因子，直到根结点为止
AvlNode child = new AvlNode(value, parent);
if (value < parent.data) {
parent.lchild = child;
} else {
parent.rchild = child;
}
// 修改各个父结点的平衡因子
while (parent != null) {
int cmp = parent.data - value;
if (cmp > 0) {
// 插入左结点则平衡因子+1
parent.balance++;
} else {
// 插入的是右结点，平衡因子-1
parent.balance--;
}
// 结点的平衡因子0时，该结点及其父结点都不需要做修改
if (parent.balance == 0) {
break;
}
// 结点的平衡因子为2或-2时二叉排序树不平衡，需要旋转调整
if (Math.abs(parent.balance) == 2) {
fixAfterInsert(parent);
break;
}
parent = parent.parent;
}
size++;
return true;
}
public void fixAfterInsert(AvlNode p) {
// 左子树深度较大导致的不平衡,左平衡算法右旋
if (p.balance == 2) {
// 平衡因子为2时说明左子树导致不平衡，进行左平衡
leftBalance(p);
}
if (p.balance == -2) {
// 平衡因子为-2说明右子树导致不平衡，进行右平衡
rightBalance(p);
}
}
// 左平衡，p为最小不平衡子树的根结点
public void leftBalance(AvlNode p) {
//最小不平衡子树根结点的左孩子
AvlNode lc = p.lchild;
switch (lc.balance) {
//插入的结点在p的左孩子的左子树上，需要右单旋处理
case Left_High:
lc.balance = Equal_High;
p.balance = Equal_High;
//右单旋
right_Rotate(p);
break;
//插入的结点在p的左孩子的右子树上，需要双旋(先左旋再右旋)处理
case Right_High:
//rd指向p的左孩子的右子树树根
AvlNode rd = lc.rchild;
//修改最小不平衡二叉树根结点p以及p的左孩子lc的平衡因子
switch (rd.balance) {
case Left_High:
lc.balance = Equal_High;
p.balance = Right_High;
break;
case Right_High:
lc.balance = Left_High;
p.balance = Equal_High;
break;
case Equal_High:
lc.balance = Equal_High;
p.balance = Equal_High;
break;
}
rd.balance = Equal_High;
//双旋
left_Rotate(p.lchild); //对p的左子树作左旋处理(p的左孩子为空时不操作)
right_Rotate(p); //对p作右旋处理
break;
}
}
//右平衡，p为最小不平衡子树的根
public void rightBalance(AvlNode p) {
//rc指向p的右孩子
AvlNode rc = p.rchild;
switch (rc.balance) {
//插入的结点在p的右孩子的右子树上时，进行左单旋处理
case Right_High:
rc.balance = Equal_High;
p.balance = Equal_High;
//左单旋
left_Rotate(p);
break;
//插入的结点在p的右孩子的左子树上时，进行双旋处理(先右旋再左旋)
case Left_High:
//ld指向p的右孩子的左子树的树根
AvlNode ld = rc.lchild;
switch (ld.balance) {
case Left_High:
p.balance = Equal_High;
rc.balance = Right_High;
break;
case Right_High:
p.balance = Left_High;
rc.balance = Equal_High;
break;
case Equal_High:
p.balance = Equal_High;
rc.balance = Equal_High;
break;
}
ld.balance = Equal_High;
//双旋操作
right_Rotate(p.rchild); //对p的右子树进行右旋处理
left_Rotate(p); //对p进行左旋处理
break;
}
}
// 左旋(逆时针旋转)
public void left_Rotate(AvlNode p) {
if (p != null) {
AvlNode r = p.rchild;
//将p的右子树的左孩子作为p的右孩子
p.rchild = r.lchild;
//p的右子树的左孩子不为空时，将p作为其父结点
if (r.lchild != null) {
r.lchild.parent = p;
}
//r结点左旋称为成为根结点(r指向p.parent)
r.parent = p.parent;
//p的父结点指向r结点
if (p.parent == null) {
root = r;
} else if (p == p.parent.lchild) {
p.parent.lchild = r;
} else if (p == p.parent.rchild) {
p.parent.rchild = r;
}
//p结点左旋成为r的左孩子
r.lchild = p;
//p的父结点是r
p.parent = r;
}
}
// 右旋(顺时针旋转)
public void right_Rotate(AvlNode p) {
if (p != null) {
//l为p的左孩子
AvlNode l = p.lchild;
//将p的左子树的右孩子作为p的左孩子
p.lchild = l.rchild;
//当p的左子树的右孩子不为空时，将p作为它的父结点
if (l.rchild != null) {
l.rchild.parent = p;
}
l.parent = p.parent;
if (p.parent == null) {
root = l;
} else if (p == p.parent.lchild) {
p.parent.lchild = l;
} else if (p == p.parent.rchild) {
p.parent.rchild = l;
}
l.rchild = p;
p.parent = l;
}
}
//二叉平衡树查找
public boolean search_AVL(int value) {
AvlNode current = root;
while(current != null) {
if (value > current.data) {
current = current.rchild;
}else if (value < current.data) {
current = current.lchild;
}else {
return true;
}
}
return false;
}
//获取树中的结点数
public int getNodeSize() {
return size;
}
// 中序遍历
public void InOrderTraverse(AvlNode node) {
if (node == null) {
return;
}
InOrderTraverse(node.lchild);
System.out.print(node.data+" ");
InOrderTraverse(node.rchild);
}
}
测试程序：
/**
* @author 作者 Shaw:
* @version 创建时间：2018年12月11日 上午11:17:26
* 类说明:测试类
*/
public class AVLMain {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {3,2,1,4,5,6,7,10,9,8,3};
BinaryBalanceTree balanceTree = new BinaryBalanceTree();
for (int i = 0; i < a.length; i++) {
balanceTree.insertAVL(a[i]);
}
System.out.print("中序遍历结果：");
balanceTree.InOrderTraverse(balanceTree.root);
System.out.println("\n查找3："+balanceTree.search_AVL(3));
System.out.println("查找11："+balanceTree.search_AVL(11));
System.out.println("二叉平衡树中结点个数："+balanceTree.getNodeSize());
}
}
测试结果：
平衡二叉树测试结果.png
从结果可以看出，数组中重复的数值3并没有被插入到平衡二叉树中，二叉树的结点数为10，可以通过打断点的形式查看每一个结点的父结点、左右结点，验证平衡二叉树的正确性。
总结
二叉平衡树(AVL)是在二叉排序树的基础上进一步完善得到的，所以二叉平衡树首先是一棵二叉排序树，其次它每一个结点的左右子树的高度差最多为1。二叉平衡树平衡因子大于1时右旋，平衡因子小于-1时左旋，进而使树平衡。二叉平衡树查找的时间复杂度为O(logn)，其中n为二叉树结点个数。
网友评论