AVL平衡二叉树图+代码详解
平衡二叉树的定义:是一种二叉排序树(可以是空树),其中每一个节点的左右两个子树的高度差的绝对值不超过1。
注意:二叉排序树不一定是平衡二叉树!
平衡因子的概念:
二叉树上节点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor)
例如:
下面这棵树就不是平衡二叉树,因为58、88节点都不符合平衡二叉树的定义,BF分别为2,-2
下面这棵树也不是平衡二叉树,因为58节点都不符合平衡二叉树的定义,BF为3
下面这棵树就是平衡二叉树,每个节点的BF 平衡因子的绝对值不超过1
那么很明显,如何去调整每个节点让其的BF平衡因子的绝对值不超过1就是构建平衡二叉树的主要步骤了。
调整节点有以下两种基本操作:
左旋、右旋
那么什么是左旋
例如:
有一颗树:
当然,还有一种比较复杂例子:需要经过两步的旋转:左旋再右旋 或者 右旋再左旋
例如:
1、先将7节点右旋
2、再将6节点左旋
树就达到平衡了。
左旋理解后,那么右旋也就容易理解了,大致是一样的
旋转明白后就可以开始码代码了,先把最基础的左旋,右旋写出来
左旋:
两种情况:判断需要旋转节点(黄色)的右节点的左孩子是否为空
代码如下:
/**
* 左旋
* @param node
*/
public void rerote_left(AVLTreeNode<E> node){
if(node!=null){
//step① right、 parent
AVLTreeNode<E> nr=node.right;
AVLTreeNode<E> nrl=node.right.left;
node.right=nrl;
if(nrl!=null){
nrl.parent=node;
}
//step②left||right parent
if(node.parent!=null){
if(node.parent.left==node){
node.parent.left=nr;
}else if(node.parent.right==node){
node.parent.right=nr;
}
}else{
root=nr;
}
nr.parent=node.parent;
//step③left、parent
nr.left=node;
node.parent=nr;
}
}
右旋:
两种情况:判断需要旋转节点(黄色)的左节点的右孩子是否为空
代码如下:
/**
* 右旋
* @param node
*/
public void rerote_right(AVLTreeNode<E> node){
if(node!=null){
//step① left、 parent
AVLTreeNode<E> nl=node.left;
AVLTreeNode<E> nlr=node.left.right;
node.left=nlr;
if(nlr!=null){
nlr.parent=node;
}
//step②left||right parent
if(node.parent!=null){
if(node.parent.left==node){
node.parent.left=nl;
}else if(node.parent.right==node){
node.parent.right=nl;
}
}else{
root=nl;
}
nl.parent=node.parent;
//step③right、parent
nl.right=node;
node.parent=nl;
}
}
完成了最基本的左旋和右旋之后,接下来就简单多了。
要使树成为平衡二叉树,先细分工作,一般分为两种情况:左子树过深或者右子树过深。
左平衡操作、有平衡操作
一、左子树过深导致树不平衡,解决左子树过深,实现左平衡有以下操作:
1、如果新的结点插入到t的左孩子的左子树中,则直接进行右旋操作即可
2、如果新的结点插入到t的左孩子的右子树中,则需要进行分情况讨论
设定平衡因子(左子树高度-右子树高度):
LEFT_HEIGHT=1(表示:左子树高)
RIGHT_HEIGHT=-1(表示:右子树高)
EQUAL_HEIGHT=0(表示:左右子树高度相同)
以上就是左子树不平衡的所以情况处理方法,很容易得到规律,叶子节点的balanc不变,第二种情况都是先左旋再右旋。
再来看右子树过深导致树不平衡的情况,那就简单多了。
二、解决右子树过深,实现右平衡有以下操作:
1、如果新的结点插入到t的右孩子的右子树中,则直接进行左旋操作即可
2、如果新的结点插入到t的右孩子的左子树中,则需要进行分情况讨论
以上就是右子树不平衡的所以情况处理方法,很容易得到规律,叶子节点的balanc不变,第二种情况都是先右旋再左旋。
左右子树平衡处理原理明白后,敲代码就简单了
代码如下:
/**
* 左子树平衡操作
* @param node
*/
public void balance_left(AVLTreeNode<E> tree){
AVLTreeNode<E> tl =tree.left;
switch (tl.balanc) {
//新的结点插入到t的左孩子的左子树
case LEFT_HEIGHT:
//直接右旋
rerote_right(tree);
tl.balanc=EQUAL_HEIGHT;
tree.balanc=EQUAL_HEIGHT;
break;
//新的结点插入到t的左孩子的右子树
case RIGHT_HEIGHT:
AVLTreeNode<E> tlr =tl.right;
switch (tlr.balanc) {
//情况b:当t的左孩子的右子树根节点的balance = LEFT_HEIGHT
case LEFT_HEIGHT:
tree.balanc=RIGHT_HEIGHT;
tl.balanc=EQUAL_HEIGHT;
tlr.balanc=EQUAL_HEIGHT;
break;
//情况a:当t的左孩子的右子树根节点的balance = RIGHT_HEIGHT
case RIGHT_HEIGHT:
tree.balanc=EQUAL_HEIGHT;
tl.balanc=LEFT_HEIGHT;
tlr.balanc=EQUAL_HEIGHT;
break;
//情况c:当t的左孩子的右子树根节点的balance = EQUAL_HEIGHT
case EQUAL_HEIGHT:
tree.balanc=EQUAL_HEIGHT;
tl.balanc=EQUAL_HEIGHT;
tlr.balanc=EQUAL_HEIGHT;
break;
}
//先左旋、后右旋
rerote_left(tl);
rerote_right(tree);
break;
}
}
/**
* 右子树平衡操作
* @param node
*/
public void balance_right(AVLTreeNode<E> tree){
AVLTreeNode<E> tr =tree.right;
switch (tr.balanc) {
//新的结点插入到t的右孩子的右子树
case RIGHT_HEIGHT:
//直接左旋
rerote_left(tree);
tr.balanc=EQUAL_HEIGHT;
tree.balanc=EQUAL_HEIGHT;
break;
//新的结点插入到t的右孩子的左子树
case LEFT_HEIGHT:
AVLTreeNode<E> trl =tr.left;
switch (trl.balanc) {
//情况a:当t的右孩子的左子树根节点的balance = LEFT_HEIGHT
case LEFT_HEIGHT:
tree.balanc=EQUAL_HEIGHT;
tr.balanc=RIGHT_HEIGHT;
trl.balanc=EQUAL_HEIGHT;
break;
// 情况b:当t的右孩子的左子树根节点的balance = RIGHT_HEIGHT
case RIGHT_HEIGHT:
tree.balanc=LEFT_HEIGHT;
tr.balanc=EQUAL_HEIGHT;
trl.balanc=EQUAL_HEIGHT;
break;
//情况C:当t的右孩子的左子树根节点的balance = EQUAL_HEIGHT
case EQUAL_HEIGHT:
tree.balanc=EQUAL_HEIGHT;
tr.balanc=EQUAL_HEIGHT;
trl.balanc=EQUAL_HEIGHT;
break;
}
//先右旋、后左旋
rerote_right(tr);
rerote_left(tree);
break;
}
}
接下来就是插入节点了
插入节点
插入节点就按照二叉排序树的规则来插,右子树的节点比左子树的节点要大;
插入后再用回溯去轮询父节点的平衡因子的绝对值BF;如果BF==0,那表示插入节点不影响树的平衡;如果BF==1,那回溯操作:parent=parent.parent;
如果BF==2,那么就进行左右平衡操作。
代码如下:
/**
* 插入节点
* @param data
* @return
*/
@SuppressWarnings("unchecked")
public boolean insertAVLNode(E data){
AVLTreeNode<E> parent=null;
if(root==null){
AVLTreeNode<E> node =new AVLTreeNode<E>(data,parent);
root=node;
root.balanc=EQUAL_HEIGHT;
size=1;
return true;
}else{
AVLTreeNode<E> t =root;
comparable =(Comparable<? super E>)data;
int cmp=0;
//查找插入位置
do{
parent=t;
cmp=comparable.compareTo(t.data);
if(cmp>0){
t=t.right;
}else if(cmp<0){
t=t.left;
}else{
//已经存在就不需要再插入
return false;
}
}while(t!=null);
AVLTreeNode<E> child = new AVLTreeNode<E>(data, parent);
//插入节点
if (cmp < 0) {
parent.left = child;
} else {
parent.right = child;
}
//回溯,左右平衡操作
while(parent!=null){
cmp = comparable.compareTo(parent.data);
if (cmp < 0) {
parent.balanc++;
} else {
parent.balanc--;
}
//这种情况表示插入并没有破坏平衡,不用处理
if(parent.balanc==0){
break;
}
//平衡因子等于2、破坏平衡,需要旋转
if(Math.abs(parent.balanc)==2){
afterInsert(parent);
break;
}else {
parent = parent.parent;
}
}
size++;
return true;
}
}
/**
* 左右平衡操作
* @param parent
*/
private void afterInsert( AVLTreeNode<E>parent) {
if(parent.balanc==2){
//左子树过深,需要左平衡
balance_left(parent);
}else if(parent.balanc==-2){
//右子树过深,需要右平衡
balance_right(parent);
}
}
测试:
Integer[] nums = { 2, 5, 8,0, 1, -2};
AVLTree<Integer> AVTree = new AVLTree<Integer>();
for (int i = 0; i < nums.length; i++) {
AVTree.insertAVLNode(nums[i]);
}
System.out.println(“root : ” +AVTree.root.data);
AVTree.midOrderLook(AVTree.root);
对于数据2,5,8,0,1,-2 依次插入AVL树
当插入1的时候,2节点的平衡因子==2了,导致该树不平衡了,这种情况就是
新的结点插入到T的左孩子的右子树中
需要进行左平衡操作:
先左旋后右旋
当插入-2的时候,5节点的平衡因子==2了,导致该树不平衡了,这种情况就是
新的结点插入到T的左孩子的左子树中
只需要进行右旋就可以了。
那么
根节点的数据是:1
中序遍历应该是:
-2 、0、1、2、5、8
程序运行的结果是:
root :1
-2 0 1 2 5 8
JDK1.8以下是用了AVL树构建TreeMap、TreeSet,测试也可以用其测试
/**
* 递归中序遍历
* @param root
*/
public void midOrderLook(AVLTreeNode<E> root){
if(null==root){
return ;
}
midOrderLook(root.left);
System.out.print(root.data+" ");
midOrderLook(root.right);
}
public void treeSetPrint(Integer[] nums){
TreeSet<Integer>map=new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
map.add(nums[i]);
}
while(!map.isEmpty()){
System.out.print(map.pollFirst()+" ");
}
}
public static void main(String[] args) {
Integer[] nums = { 2, 5, 8,0, 1, -2,32,12,88,54,21,29,34,45};
AVLTree<Integer> AVTree = new AVLTree<Integer>();
for (int i = 0; i < nums.length; i++) {
AVTree.insertAVLNode(nums[i]);
}
System.out.println("root :" +AVTree.root.data);
System.out.print("AVTree :");AVTree.midOrderLook(AVTree.root);
System.out.print("\nTreeSet :");AVTree.treeSetPrint(nums);
}
程序运行的结果是:
root :12
AVTree :-2 0 1 2 5 8 12 21 29 32 34 45 54 88
TreeSet :-2 0 1 2 5 8 12 21 29 32 34 45 54 88
总结:
上面就是AVL树的构建的一整个过程了,删除节点还没有做,不过大概的流程和插入差不多的,也是先查询到被删除节点,删除后再进行左右平衡操作,使AVL树重新达到平衡。
AVL树在JDK1.8以下用的比较多,但是JDK1.8已经用红黑树来代替AVL树了。
至于, 为什么不用 AVL 树作为底层实现,那是因为 AVL 树是高度平衡的树(红黑树放弃了高度严格平衡的优越条件),而每一次对树的修改, 都要重新做左右子树平衡操作,这里的开销会比红黑树大, 红黑树插入只要两次旋转,删除至多三次旋转,但不可否认的是, AVL 树搜索的效率是非常稳定的,选取红黑树, 我认为是一种折中的方案。
下一篇: 春季运动谨记八要点,不宜大汗淋漓