什么是平衡二叉树

前言

上篇文章里面,我们已经学习了二叉搜索树的相关内容,二叉搜索树有一个缺点,在插入数据是有序的序列(包括升序和降序),会导致二叉树退化成链表,从而导致在查找,删除,添加时的性能均从O(logN)降低为O(N),这是不能接受的。如下图:

究其原因,是因为二叉搜索树退化成链表的时候,树的高度与节点的个数相等,也就是成正比,所以为了优化这种情况,就出现了具有平衡能力的二叉搜索树,其中AVL树是最早被发明的自平衡二叉查找树。在AVL树中,任一节点对应的两棵子树的最大高度差为1,因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logN)。增加和删除元素的操作则可能需要借由一次或多次树旋转,以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis,他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

平衡二叉树的性质

平衡二叉树本质上是特殊的二叉搜索树(二叉排序树),它具有二叉搜索树所有的特点,此外它有自己的特别的性质,如下:

(1)它是一棵空树或它的左右两个子树的高度差的绝对值不超过1;

(2)平衡二叉树的左右两个子树都是一棵平衡二叉树。

什么是平衡因子

平衡因子指的是,平衡二叉树在保持平衡的时候,是通过平衡因子来判断的,节点的平衡因子 = 该节点的左子树的高度 - 该节点右子树的高度。只有当值等于-1(右子树的高度大),0(左右子树的高度相等),1(左子树的高度大)的时候,能够代表该子树是平衡的除此之外,就认为该节点已经失衡了,需要旋转来维持平衡,如下图的平衡因子分布情况:

平衡二叉树的旋转分类

平衡二叉树在插入和删除的时候都有可能发生旋转来维持平衡,总得来说,旋转分四种情形:

(1)左旋转

如下图,对二叉搜索树分别插入1,2,3升序序列,会导致树向右倾斜,这个我们需要左旋来平衡树:

第一张图标记了,当插入3之后,根节点1失衡了,因为1节点没有左子树,所以左子树的高度等于0,而右子树的高度等于2,故两者相减得到-2,证明树失衡了,通过向左旋转,调整了root的位置,从而使得树变得均衡了。

(2)右旋转

如下图,对二叉搜索树分别插入3,2,1降序序列,会导致树向左倾斜,这种情况下我们需要向右旋转来平衡树:

在插入1后,树发现失衡了,故而通过向右旋转的方式,来调整平衡。

(3)左右旋转

如下图与(2)的情况类似,但不同的是插入的方式是3,1,2,从而导致最后一个2插入的时候,是在右子树上导致失衡的,这种情况下比前面的稍微复杂,需要旋转两次来调整平衡。

先左旋之后,发现仍然失衡,然后接着右旋才维持平衡。

(4)右左旋转

如下图,对二叉搜索树分别插入1,3,2,与上面的(3)情形正好相反

这种情况下,先右旋然后左旋就可以保持平衡

代码实现

平衡二叉树的代码,其实和二叉搜索树的代码大体一致,包括搜索,插入和删除功能,主要的区别在于在树节点定义上多加了一个height字段,用来计算均衡因子使用,此外在插入和删除之后要加上检测平衡的代码,如果发现树失衡了就要及时调整:

public class AVLTree {
    class Node{        int data;        Node left;        Node right;        int height;
        public Node(int data) {            this.data = data;            height = 1;        }
    }
    public int getHeight(Node n){        if(n!=null){            return n.height;        }        return 0;    }
    public int getBalance(Node n){        if(n!=null){            return getHeight(n.left) - getHeight(n.right);        }        return 0;    }

    public Node rightRotate(Node y){        Node x=y.left;        Node T2=x.right;
        //rotation        x.right=y;        y.left=T2;
        x.height=Math.max(getHeight(x.left),getHeight(x.right))+1;        y.height=Math.max(getHeight(y.left),getHeight(y.right))+1;
        return x;
    }
    public Node leftRotate(Node x){            Node y=x.right;            Node T2=y.left;
            //Rotation        y.left=x;        x.right=T2;
        //update height
        x.height=Math.max(getHeight(x.left),getHeight(x.right))+1;        y.height=Math.max(getHeight(y.left),getHeight(y.right))+1;
        return y;
    }
    public Node insert(Node node, int data){        if(node==null){            return new Node(data);        }
        if(node.data>data){            node.left=insert(node.left,data);        }else if(node.data<data){            node.right=insert(node.right,data);        }else {            return node;// 已经存在        }
        node.height=Math.max(getHeight(node.left),getHeight(node.right))+1;
        int balDiff=getBalance(node);

        // 左倾斜,右旋        if(balDiff>1&&data<node.left.data){            return rightRotate(node);        }
        // 右倾斜,左旋
        if(balDiff<-1&&data> node.right.data){            return leftRotate(node);        }
        // 左倾斜,先左旋,再右旋        if(balDiff>1&&data>node.left.data){            node.left=leftRotate(node.left);            return rightRotate(node);        }

        // 右倾斜,先右旋,再左旋        if(balDiff<-1&&data<node.right.data){            node.right=rightRotate(node.right);            return leftRotate(node);        }

        return node;
    }
    private Node delete(Node node, int data){
        if(node==null){            System.out.println("要删除的节点不存在");            return null;        }else if(data<node.data){            node.left=delete(node.left,data);        }else if(data>node.data){            node.right=delete(node.right,data);        }else{//叶子节点,或者只拥有一个孩子节点的处理逻辑是一样的            if(node.left==null){                return node.right;            }else if(node.right==null){                return node.left;            }else{                //到这一步说明删除的节点拥有2个孩子节点                //找到剩下左子树里面最大的节点,或者找到右子树里面最小的节点,这里使用的是前者                //使用最大值覆盖当前要被删除的节点的值                node.data=retrieveData(node.left);                //最后删除,在剩下左子树里面刚才被替换到最大值的节点                node.left=delete(node.left,node.data);            }
        }
        if(node==null) return null;
        node.height=Math.max(getHeight(node.left),getHeight(node.right))+1;
        int balDiff=getBalance(node);
        // 左倾斜,右旋        if(balDiff>1&&getBalance(node.left)>=0){            return rightRotate(node);        }

        // 右倾斜,左旋
        if(balDiff<-1&&getBalance(node.right)<=0){            return leftRotate(node);        }

        // 左倾斜,先左旋,再右旋        if(balDiff>1&&getBalance(node.left)<0){            node.left=leftRotate(node.left);            return rightRotate(node);        }
        // 右倾斜,先右旋,再左旋        if(balDiff<-1&&getBalance(node.right)>0){            node.right=rightRotate(node.right);            return  leftRotate(node);        }
        return node;    }
    private int retrieveData(Node p)    {        while (p.right != null) p = p.right;
        return p.data;    }



    public void inorder(Node root) {        if (root != null) {            inorder(root.left);            System.out.print(" " + root.data);            inorder(root.right);        }    }
    public List<List<Integer>> levelOrder(Node root) {        List result = new ArrayList();
        if (root == null) {            return result;        }
        Queue<Node> queue = new LinkedList<Node>();        queue.offer(root);
        while (!queue.isEmpty()) {            ArrayList<Integer> level = new ArrayList<Integer>();            int size = queue.size();            for (int i = 0; i < size; i++) {                Node head = queue.poll();                level.add(head.data);                if (head.left != null) {                    queue.offer(head.left);                }                if (head.right != null) {                    queue.offer(head.right);                }            }            result.add(level);        }        System.out.println(result);        return result;    }
    public static void main(String[] args) {
        Node root = null;        AVLTree i = new AVLTree();        testCase2(root,i);    }


    private static void testCase1(Node root,AVLTree i ){        root = i.insert(root, 1);        root = i.insert(root, 2);        root = i.insert(root, 3);
        root = i.insert(root, 4);        root = i.insert(root, 5);        root = i.insert(root, 6);        root = i.insert(root, 7);        root = i.insert(root, 8);        i.levelOrder(root);        root = i.delete(root,5);        i.levelOrder(root);    }

    private static void testCase2(Node root,AVLTree i ){        root = i.insert(root, 50);        root = i.insert(root, 25);        root = i.insert(root, 75);
        root = i.insert(root, 15);        root = i.insert(root, 40);        root = i.insert(root, 60);        root = i.insert(root, 80);        root = i.insert(root, 35);        root = i.insert(root, 55);        root = i.insert(root, 65);        root = i.insert(root, 90);        root = i.insert(root, 62);        i.levelOrder(root);
        root = i.delete(root,15);        i.levelOrder(root);

    }

}

`

平衡二叉树的优缺点

优点: 通过严格的平衡性保证,其搜索性能在最差的情况下的也得达到O(logn)

缺点: 为了保证严格的均衡性,导致在插入和删除的时候需要额外花费时间旋转来调整平衡度,从而使得插入和删除的性能下降

总结

本文主要介绍了平衡二叉树的相关内容,AVL平衡二叉树很好的解决了二叉搜索树在遇到有序序列性能退化为O(N)的情况,使得在最坏情况下的搜索效率仍然能够达到O(logN),但这种优化是牺牲了插入和删除的性能换来的,故而AVL树并不适合需要频繁插入和删除的场景,而红黑树则是权衡了 这种情况,其并不强调严格的平衡性,而是保持一定的平衡性,从而使得在搜索,插入,删除的场景下均有一个不错的速度,这个会在后续的文章中分析。

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2019-04-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券