欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

AVL平衡二叉树图+代码详解

程序员文章站 2022-06-07 08:14:29
...

平衡二叉树的定义:是一种二叉排序树(可以是空树),其中每一个节点的左右两个子树的高度差的绝对值不超过1。
注意:二叉排序树不一定是平衡二叉树!

平衡因子的概念:
二叉树上节点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor)

例如:
下面这棵树就不是平衡二叉树,因为58、88节点都不符合平衡二叉树的定义,BF分别为2,-2

AVL平衡二叉树图+代码详解

下面这棵树也不是平衡二叉树,因为58节点都不符合平衡二叉树的定义,BF为3

AVL平衡二叉树图+代码详解

下面这棵树就是平衡二叉树,每个节点的BF 平衡因子的绝对值不超过1

AVL平衡二叉树图+代码详解

那么很明显,如何去调整每个节点让其的BF平衡因子的绝对值不超过1就是构建平衡二叉树的主要步骤了。

调整节点有以下两种基本操作:

左旋、右旋

那么什么是左旋

例如:
有一颗树:
AVL平衡二叉树图+代码详解
AVL平衡二叉树图+代码详解
当然,还有一种比较复杂例子:需要经过两步的旋转:左旋再右旋 或者 右旋再左旋

例如:

1、先将7节点右旋
AVL平衡二叉树图+代码详解
AVL平衡二叉树图+代码详解
2、再将6节点左旋
AVL平衡二叉树图+代码详解
AVL平衡二叉树图+代码详解

树就达到平衡了。

左旋理解后,那么右旋也就容易理解了,大致是一样的

旋转明白后就可以开始码代码了,先把最基础的左旋,右旋写出来

左旋:
两种情况:判断需要旋转节点(黄色)的右节点的左孩子是否为空
AVL平衡二叉树图+代码详解

代码如下:

    /**
     * 左旋
     * @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;
            }
}

右旋:
两种情况:判断需要旋转节点(黄色)的左节点的右孩子是否为空
AVL平衡二叉树图+代码详解
代码如下:

    /**
     * 右旋
     * @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的左孩子的左子树中,则直接进行右旋操作即可
AVL平衡二叉树图+代码详解
2、如果新的结点插入到t的左孩子的右子树中,则需要进行分情况讨论

 设定平衡因子(左子树高度-右子树高度):
 LEFT_HEIGHT=1(表示:左子树高)
 RIGHT_HEIGHT=-1(表示:右子树高)
 EQUAL_HEIGHT=0(表示:左右子树高度相同)

AVL平衡二叉树图+代码详解

以上就是左子树不平衡的所以情况处理方法,很容易得到规律,叶子节点的balanc不变,第二种情况都是先左旋再右旋。

再来看右子树过深导致树不平衡的情况,那就简单多了。
二、解决右子树过深,实现右平衡有以下操作:

1、如果新的结点插入到t的右孩子的右子树中,则直接进行左旋操作即可
AVL平衡二叉树图+代码详解
2、如果新的结点插入到t的右孩子的左子树中,则需要进行分情况讨论
AVL平衡二叉树图+代码详解
AVL平衡二叉树图+代码详解
以上就是右子树不平衡的所以情况处理方法,很容易得到规律,叶子节点的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树
AVL平衡二叉树图+代码详解

当插入1的时候,2节点的平衡因子==2了,导致该树不平衡了,这种情况就是
新的结点插入到T的左孩子的右子树中
需要进行左平衡操作:
先左旋后右旋
AVL平衡二叉树图+代码详解
当插入-2的时候,5节点的平衡因子==2了,导致该树不平衡了,这种情况就是
新的结点插入到T的左孩子的左子树中
只需要进行右旋就可以了。
AVL平衡二叉树图+代码详解
那么
根节点的数据是: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 树搜索的效率是非常稳定的,选取红黑树, 我认为是一种折中的方案。