• 欢迎访问少将全栈,学会感恩,乐于付出,珍惜缘份,成就彼此、推荐使用最新版火狐浏览器和Chrome浏览器访问本网站。
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏少将全栈吧
  • 欢迎加博主微信:jiang_shaobo

平衡二叉树算法分析

点滴 admin 6年前 (2013-12-09) 234次浏览 已收录 0个评论 扫描二维码

1、平衡二叉树定义:

平衡二叉树(Balanced Binary Tree或Height-Balanced Tree)又称AVL树。它或者是一颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子bf(balance factor)定义为该结点的左子树的深度减去右子树的深度,则平衡二叉树上所有结点的平衡因子只可能为-1、0和1这三个值。

2、失去平衡情况分析:

假设结点A是一颗子平衡二叉树,当在以A为根结点的AVL树上插入一个新结点时,会出现以下三种情况:

1)如果插入前A?bf=1(A的左子树深度比右子树深度多1),如果插入在A的左子树上且A的左子树深度增加了1,则此时A?bf=2需要对树进行调整,如图2.1结点C为新插入的结点,C可以插入到B的左子树上(如图2.1(b))或者右子树上(如图2.1(c))。

2)如果插入前A?bf=0(A的左子树和右子树深度相等),如果插入在A的左子树上且A的左子树深度增加了1,则此时只需要改变A的平衡因子为1即可不需要对树进行调整。如果插入在A的右子树上且A的右子树深度增加了1,则此时只需要改变A的平衡因子为-1即可不需要进行调整。

3)如果插入前A?bf=-1(A的左子树深度比右子树深度少1),如果插入在A的右子树上且A的右子树深度增加了1,则此时A?bf=-2需要对树进行调整,如图2.2结点C为新插入的结点,C可以插入在B的左子树上(如图2.2(b))或者右子树上(如图2.2(c))。

         图2.1                                    图2.2

            注意:上图中为了清楚的看到添加结点后失去平衡时的情况,省去了一些子结点,这些结点在下面的分析中会完整画出来

当出现图2.1(b)中的情况时只需要进行一次右旋转操作,旋转后得到如图2.1(d)所示的平衡二叉树。

当出现图2.1(c)中的情况时需要先对A的左子树B进行左旋操作,然后再进行右旋操作,旋转后得到如图2.1(e)所示的平衡二叉树。

当出现图2.2(b)中的情况时只需要进行一次右旋转操作,旋转后得到如图2.1(d)所示的平衡二叉树。

当出现图2.2(c)中的情况时需要先对A的右子树B进行右旋,然后再进行左旋操作,旋转后得到如图2.2(e)所示的平衡二叉树

3.求旋转后各结点的平衡因子:

旋转后怎么确定各结点的新的平衡因子是平衡二叉树算法的关键点,我们需要按情况来一一推理。

一、当出现图2.1(b)(c)这两种情况时,需进行左平衡处理:

1)当新结点插入到B的左子树上时B?bf=1,由此可知:deep(C)=deep(E)+1,deep(B)=deep(C)+1;由于插入新结点前A?bf=1,deep(B)=deep(D)+1则插入新节点后deep(B)=deep(D)+2;图3.1.1为调整前的二叉树,图3.1.2为对A树进行右旋转后的AVL树:

      图3.1.1 图3.1.2

对比图3.1.1和3.1.2可知旋转后的新树中A的左子树发生了变化,B的右子树发生了变化,其他结点都没变;因此只需要重新算出A的平衡因子和B的平衡因子即可证明调整后的树是否为AVL树。

由上面的等式deep(B)=deep(D)+2,deep(B)=deep(C)+1,deep(C)=deep(E)+1

可以推出deep(E)=deep(C)-1=deep(B)-1-1=deep(D)+2-1-1=deep(D)可得出A?bf=0

由调整后deep(E)=deep(D)可推出调整后deep(A)=deep(E)+1=deep(C)-1+1=deep(C)可得出B?bf=0;

2)当新结点插入到B的右子树上时B?bf=-1,由此可知:deep(C)=deep(E)-1,deep(B)=deep(E)+1;由于插入新结点前A?bf=1,deep(B)=deep(D)+1则插入新节点后deep(B)=deep(D)+2图3.2.1为调整前的二叉树,图3.2.2为先对B树进行左旋然后对A树进行右旋后的AVL树:

图3.2.1 图3.2.2

对比图3.2.1和3.2.2可知调整后的新树中A的左子树发生了变化,B的右子树发生了变化,E的左右子树都发生了变化,其他结点都没变,因此只需要重新算出A的平衡因子、B的平衡因子以及E的平衡因子即可证明调整后的树是否为AVL树。

此时由于调整后的B和A结点的平衡因子与E的左右子树EL和ER有关,因此需要根据E的平衡因子的不同来进行分析:

由上面的分析可得到deep(B)=deep(D)+2,deep(B)=deep(E)+1,deep(C)=deep(E)-1

1、当E?bf=1时:deep(E)=deep(EL)+1,deep(ER)=deep(EL)-1

deep(C)=deep(E)-1=deep(EL)+1-1=deep(EL)可得B?bf=0

deep(D)=deep(B)-2=deep(E)+1-2=deep(ER)+1+1+1-2=deep(ER)+1可得A?bf=-1

由于deep(EL)=deep(ER)+1所以E?bf=0

2、当E?bf=0时:deep(E)=deep(EL)+1,deep(ER)=deep(EL)

deep(C)=deep(E)-1=deep(EL)+1-1=deep(EL)可得B?bf=0

deep(D)=deep(B)-2=deep(E)+1-2=deep(ER)+1+1-2=deep(ER)可得A?bf=0

由于B?bf=0,A?bf=0所以E?bf=0

3、当E?bf=-1时:deep(E)=deep(ER)+1,deep(ER)=deep(EL)+1

deep(C)=deep(E)-1=deep(EL)+1+1-1=deep(EL)+1可得B?bf=1

deep(D)=deep(B)-2=deep(E)+1-2=deep(ER)+1+1-2=deep(ER)可得A?bf=0

由于deep(EL)=deep(ER)-1所以E?bf=0

二、当出现图2.2(b)(c)这两种情况时,需进行右平衡处理:

1)当新结点插入到C的左子树上时C?bf=1,由此可知:deep(C)=deep(E)+1,deep(D)=deep(E)-1;由于插入新结点前A?bf=-1,deep(B)=deep(C)-1则插入新节点后deep(B)=deep(C)-2图3.3.1为调整前的二叉树,图3.3.2为先对C树进行右旋然后对A树进行左旋后的AVL树:

    图3.3.1   图3.3.2 

对比图3.3.1和3.3.2可知调整后的新树中A的右子树发生了变化,C的左子树发生了变化,E的左右子树都发生了变化,其他结点都没变,因此只需要重新算出A的平衡因子、B的平衡因子以及E的平衡因子即可证明调整后的树是否为AVL树。

此时由于调整后的A和C结点的平衡因子与E的左右子树EL和ER有关,因此需要根据E的平衡因子的不同来进行分析:

由上面的分析可得到deep(B)=deep(C)-2,deep(C)=deep(E)+1,deep(D)=deep(E)-1

1、当E?bf=1时:deep(E)=deep(EL)+1,deep(ER)=deep(EL)-1

deep(B)=deep(C)-2=deep(EL)+1+1-2=deep(EL)可得A?bf=0

deep(D)=deep(E)-1=deep(ER)+1+1-1=deep(ER)+1可得C?bf=-1

由于deep(EL)=deep(ER)+1所以E?bf=0

2、当E?bf=0时:deep(E)=deep(EL)+1,deep(ER)=deep(EL)

deep(B)=deep(E)+1-2=deep(EL)+1+1-2=deep(EL)可得A?bf=0

deep(D)=deep(E)-1=deep(ER)+1-1=deep(ER)可得C?bf=0

由于A?bf=0,C?bf=0所以E?bf=0

3、当E?bf=-1时:deep(E)=deep(ER)+1,deep(ER)=deep(EL)+1

deep(B)=deep(C)-2=deep(E)+1-2=deep(EL)+1+1+1-2=deep(EL)+1可得A?bf=1

deep(D)=deep(E)-1=deep(ER)+1-1=deep(ER)可得C?bf=0

由于deep(EL)=deep(ER)-1所以E?bf=0

2)当新结点插入到C的右子树上时C?bf=-1,由此可知:deep(C)=deep(D)+1,deep(D)=deep(E)+1;由于插入新结点前A?bf=-1,deep(B)=deep(C)-1则插入新节点后deep(B)=deep(C)-2图3.4.1为调整前的二叉树,图3.4.2为进行左旋后的AVL树:

图3.4.1                                 图3.4.2

对比图3.4.1和3.4.2可知调整后的新树中A的右子树发生了变化,C的左子树发生了变化,其他结点都没变,因此只需要重新算出A的平衡因子和C的平衡因子即可证明调整后的树是否为AVL树。

由上面的等式deep(B)=deep(C)-2,deep(C)=deep(D)+1,deep(D)=deep(E)+1

可以推出deep(B)=deep(C)-2=deep(D)+1-2=deep(E)+1+1-2=deep(E)可得出A?bf=0

由A?bf=0调整后deep(A)=deep(E)+1=deep(D)-1+1=deep(D)可得出C?bf=0;

4.Java实现代码:

package org.algorithms.tree;

import java.util.concurrent.ConcurrentLinkedQueue;


public class BalanceBiTreeT {

    private Node root;
    
    private int size;
    
    public void insert(T t){
        if(root==null){
            root = new Node();
            root.bf = 0;
            root.data = t;
            size++;
            return;
        }
        addNode(root,t);
    }
    
    private boolean addNode(Node nd,T t){
        boolean taller = false;
        ComparableT cp = (ComparableT)nd.data;
        int i = cp.compareTo(t);
        if(i==0){
            return false;
        }else if(i0){
            if(nd.lChild==null){
                Node child = new Node();
                child.bf = 0;
                child.data = t;
                child.parent = nd;
                nd.lChild = child;
                size++;
                if(nd.bf==0){
                    nd.bf = 1;
                    return true;
                }
                nd.bf = 0;
            }else{
                taller = addNode(nd.lChild, t);
                if(taller){
                    if(nd.bf==1){
                        leftBalance(nd);
                        taller = false;
                    }else if(nd.bf==0){
                        nd.bf = 1;
                        taller = true;
                    }else{
                        nd.bf = 0;
                        taller = false;
                    }
                }
            }
        }else{
            if(nd.rChild==null){
                Node child = new Node();
                child.bf = 0;
                child.data = t;
                child.parent = nd;
                nd.rChild = child;
                size++;
                if(nd.bf==0){
                    nd.bf = -1;
                    return true;
                }
                nd.bf = 0;
            }else{
                taller = addNode(nd.rChild, t);
                if(taller){
                    if(nd.bf==1){
                        nd.bf = 0;
                        taller = false;
                    }else if(nd.bf==0){
                        nd.bf = -1;
                        taller = true;
                    }else{
                        rightBalance(nd);
                        taller = false;
                    }
                }
            }
        }
        return taller;
    }
    
    public int getSize(){
        return size;
    }
    
    private void leftBalance(Node nd){
        Node leftChild = nd.lChild;
        if(leftChild.bf==1){
            nd.bf = 0;
            leftChild.bf = 0;
            rightRotate(nd);
        }else if(leftChild.bf==-1){
            Node rd = leftChild.rChild;
            switch (rd.bf) {
            case 1:
                leftChild.bf=0;nd.bf = -1;
                break;
            case 0:
                leftChild.bf=0;nd.bf = 0;
                break;
            case -1:
                leftChild.bf = 1;nd.bf = 0;
                break;
            }
            rd.bf = 0 ;
            leftRotate(leftChild);
            rightRotate(nd);
        }
    }
    
    private void rightBalance(Node nd){
        Node rightChild = nd.rChild;
        if(rightChild.bf==1){
            Node ld = rightChild.lChild;
            switch (ld.bf) {
            case 1:
                rightChild.bf= -1; nd.bf = 0;
                break;
            case 0:
                rightChild.bf=0;nd.bf = 0;
                break;
            case -1:
                rightChild.bf = 0;nd.bf = 1;
                break;
            }
            ld.bf = 0 ;
            rightRotate(rightChild);
            leftRotate(nd);
        }else if(rightChild.bf==-1){
            nd.bf = 0;
            rightChild.bf = 0;
            leftRotate(nd);
        }
        
    }
    
    private void leftRotate(Node nd){
        Node top = nd.rChild;
        nd.rChild = top.lChild;
        if(top.lChild!=null)
            top.lChild.parent = nd;
        top.lChild = nd;
        top.parent = nd.parent;
        if(nd.parent!=null){
            if(nd.parent.lChild == nd)
                nd.parent.lChild = top;
            else
                nd.parent.rChild = top;
        }else{
            root = top;
        }
        nd.parent = top;
    }
    
    private void rightRotate(Node nd){
        Node top = nd.lChild;
        nd.lChild = top.rChild;
        if(top.rChild!=null)
            top.rChild.parent = nd;
        top.rChild = nd;
        top.parent = nd.parent;
        if(nd.parent!=null){
            if(nd.parent.lChild == nd)
                nd.parent.lChild = top;
            else
                nd.parent.rChild = top;
        }else{
            root = top;
        }
        nd.parent = top;
    }
    
    public void printTree(){
        ConcurrentLinkedQueueNode queue = new ConcurrentLinkedQueueNode();
        ConcurrentLinkedQueueNode tempQueue = new ConcurrentLinkedQueueNode();
        queue.add(root);
        int offset= 0;
        int counter=2;
        for(int i=0;i50;i++)
            System.out.print(" ");
        while(queue.peek()!=null){
            Node node = queue.poll();
            String side = "L";
            if(node.parent!=nullnode.parent.rChild==node)
                side = "R";
            System.out.print(node.data+"("+(node.parent==null?"":node.parent.data)+" "+side+")");
            if(node.parent!=nullnode.parent.rChild!=node)
                for(int i=0;icounter;i++)
                    System.out.print(" ");
            if(node.lChild!=null)
                tempQueue.add(node.lChild);
            if(node.rChild!=null)
                tempQueue.add(node.rChild);
            if(queue.isEmpty()){
                offset += 3;
                //counter--;
                copyQueue(tempQueue,queue);
                System.out.println();
                for(int i=0;i50-offset;i++)
                    System.out.print(" ");
            }
        }
        
    }
    
    private void copyQueue(ConcurrentLinkedQueueNode source,
            ConcurrentLinkedQueueNode target){
        while(source.peek()!=null){
            target.add(source.poll());
        }
    }
    
    private class Node{
        
        public T data;
        
        public Node lChild;
        
        public Node rChild;
        
        public Node parent;
        
        public int bf;
    }
}


喜欢 (0)
[🍬谢谢你请我吃糖果🍬🍬~]
分享 (0)
关于作者:
少将,关注Web全栈开发、项目管理,持续不断的学习、努力成为一个更棒的开发,做最好的自己,让世界因你不同。
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址