数据结构-AVL树

目录

二叉树

二叉搜索树的查找方式:

AVL树

AVL树节点的实现

AVL树节点的插入操作

AVL树的旋转操作

右旋转:

左旋转:

左右双旋:

右左双旋:

AVL树的不足和下期预告(红黑树)


二叉树

了解AVL树之前,需要先了解一下二叉搜索树的概念,二叉搜索树具有以下性质:

1,如果左子树不为空,则左子树上所有节点的值都小于跟节点的值。

2,如果右子树不为空,则右子树的所有节点的值都大于跟节点的值。

3,根节点的左右子树也是一颗二叉搜索树。

如果使用二叉树的中序遍历方法来遍历一颗二叉树,则可以得到一个有序的序列。

二叉搜索树的查找方式:

根据上图可以对二叉树进行查找从而得到我们想要的节点。

一个完全二叉树的查找效率可以达到 O(log N) 级别,但如果我们插入的数值都是大于根节点的数值,并且是严格递增的,那么此时整个二叉树就会退化成一个链表的结构,那么此时查找的效率也会退化成O(N)。因此我们就需要考虑一个问题,无论何时进行插入,都可以让二叉树,保持左右子树的相对平衡,随时更改根节点,这样就可以让查找的时间复杂度一直保持在O(log N),所以研究者引入了AVL树的概念。

AVL树

计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis,他们在1962年的论文《An algorithm for the organization of information》中发表了它。

AVL树它本质上其实还是一个二叉树,它的特点符合二叉树的所有特点,在此之外,AVL树还具有平衡的性质,也就是说,它的左子树和右子树的高度差的绝对值不会大于1,因此这样也就保证了AVL树的查找效率。

AVL树节点的实现

为了实现AVL树,我们需要先定义树的节点,和普通的二叉树不同,在定义节点的时候,我们也需要在其中定义一个平衡因子,我们使用bf(balance factor)来表示:AVL树的节点定义如下:

class TreeNode{
    //定义树的左右节点索引和父亲索引
    public TreeNode left = null;
    public TreeNode right = null;
    public TreeNode parent = null;
    public int val;
    public int bf;
    //定义构造函数
    public TreeNode (int val){
        this.val = val;
    }
}

我们定义当前节点的平衡因子 = 右树的高度 - 左树的高度。如果当前节点的bf<0,那么左树就高,bf>0右树就高。bf = 0,那么两边一样高。当然这只是其中的一种实现方式而已(本文是这么定义的)。

AVL树节点的插入操作

首先,我们将其分为两步

1,按照二叉树的插入方式进行插入。

2,对不满足条件的节点进行旋转,使树达到平衡。

此时可以看下接下来这几幅图:

假设我要在二叉树种插入一个值为100,那么此时我应该找到100应该插入到哪个位置,每一次寻找定义cur为要插入的位置,定义parent为cur的父亲节点,那么遍历下来就可以找到插入的位置,此时代码如下:

    public TreeNode root ;

    public void insert(int val){
        //1,首先先进行节点的插入操作;
        TreeNode node = new TreeNode(val);
        if(this.root == null){
            //如果树为空,那么node就是新的root
            this.root = node;
        }else{
            TreeNode parent = null;
            TreeNode cur = this.root;
            // 1.1 先判断要插入的位置,然后再进行插入
            while(cur != null){
                if(cur.val < val){
                    parent = cur;
                    cur = cur.right;
                } else if (cur.val == val) {
                    return;
                }else{
                    parent = cur;
                    cur = cur.left;
                }
            }
            //此时找到了要插入的位置,对node进行插入,插入的位置为parent所指向的节点
            //判断往左边插入还是右边插入,然后再让node指回去。
            if(parent.val < val){
                parent.right = node;
            }else{
                parent.left = node;
            }
            node.parent = parent;
            cur = node;
        }
    }

一定要让node指向指回去,否则子节点会丢失父节点的索引。

AVL树的旋转操作

基于以上的插入,我们可以发现一个问题,就是说,如果每次都插入比上一次大的值,那么势必会让这个树退化成一个链表,那么此时树的存储结构优势将会丢掉,所以AVL树引入了旋转操作来对树进行操作。从而使得这棵树不会退化成链表。

cur插入后,parent的平衡因子一定需要调整,

在插入之前,parent的平衡因子分为三种情况:-1,0, 1

插入时分以下两种情况:  

1. 如果cur插入到parent的左侧,只需给parent的平衡因子 -1 即可  

2. 如果cur插入到parent的右侧,只需给parent的平衡因子 +1 即可  

此时:parent的平衡因子可能有三种情况:0,正负1, 正负2  

1. 如果parent的平衡因子为0,说明插入之前parent的平衡因子为正负1,插入后被调整成0,此时满足AVL树的性质,插入成功

2. 如果parent的平衡因子为正负1,说明插入前parent的平衡因子为0,插入后被更新成正负1,此时以parent为根的树的高度增加,需要继续向上更新  

3. 如果parent的平衡因子为正负2,则parent的平衡因子违反平衡树的性质,需要对其进行旋转处理

此时更新操作就如下:

            while(){
                //更新parent的平衡因子
                if(cur == parent.right){
                    parent.bf++;
                }else{
                    parent.bf--;
                }
                //更新后的平衡因子为0,说明插入后的结果是平衡的,此时无需后续操作
                if(parent.bf == 0){
                    return;
                }
                if(parent.bf != 1 && parent.bf != -1){
                    //此时需要继续向上更新
                    if(parent.bf == 2){
                        if(cur.bf == 1){
                            // parent.bf == 2 cur.bf == 1
                        }else{
                            // parent.bf == 2 cur.bf == -1
                        }
                    }else{
                        if(cur.bf == 1){
                            // parent.bf == -2 cur.bf == 1
                        }else{
                            // parent.bf == -2 cur.bf == -1
                        }
                    }
                }
            }

那么基于以上操作,我们的更新平衡因子的模板已经搭好了,但是在什么情况下需要进行旋转呢?

右旋转:

假设有上面这种情况,原来的cur.bf == 0 , 但是parent.bf == -1 ,此时在左树的最左边插入一个节点,那么此时的节点情况就变成了cur.bf == -1 , parent.bf == -2 。那么此时就需要对parent节点进行右旋转,从而调整树的结构。

此时需要注意以下几点:

 1.  30 节点的右孩子可能存在,也可能不存在。

 2.  60 可能是根节点,也可能是子树。如果是根节点,旋转完成后,要更新根节点     如果是子树,可能是某个节点的左子树,也可能是右子树。

在上图中可以看出,当我们想进行右转操作时,需要将parent.left 标记为 subL,将subL.right标记为subLR.

从2图转换为3图可以如上图表示:

1. 修改parent.left = subLR;

2. 修改subL.right = parent;

3. 修改 subLR.parent = parent (此时需要判断subLR是否为空

4. 保存parent的父亲节点(祖父节点)

5. 修改parent的父亲节点指向subL;

6. 修改祖父节点指向subL(需要确认祖父节点是否存在,如果不存在则parent是根节点

7. 修改subL.parent属性为祖父节点;

8. 判断完了之后还要修改平衡因子。

代码如下:

private void rotateRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        parent.left = subLR;
        subL.right = parent;
        if(subLR != null){
            subLR.parent = parent;
        }
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        if(parent == this.root){
            this.root = subL;
            this.root.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = subL;
            }else{
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        subL.bf = 0;
        parent.bf = 0;
    }

左旋转:

左旋转和右旋转的逻辑是一样的,不过是对称的操作。以下是左旋转的代码演示:

此时最初的parent的bf值为1,进行添加节点之后,则是会变成parent.bf 会变成2,此时的cur.bf

会变成1(因为给cur的右树增加了一层)。此时就需要用到左旋转的方法来进行旋转,从而降低AVL树的高度了。具体代码如下:和右旋转是对称的

 private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        parent.right = subRL;
        subR.left = parent;
        if(subRL != null){
            subRL.parent = parent;
        }
        TreeNode pParent = parent.parent;
        parent.parent = subR;
        if(parent == this.root){
            this.root = subR;
            this.root.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right =subR;
            }
            subR.parent = pParent;
        }
        subR.bf = parent.bf = 0;
    }

左右双旋:

 讲完了上述两种比较简单的情况,其实还有两种比较复杂的情况,比如说,

假如说是上面这种情况呢,此时我要插入的值为40,但是60节点bf更新为-2,此时的30这个节点的bf值为1,50节点bf值为-1,这时候单纯的旋转已经无法解决这些问题了。因此

此时先对30进行左旋转:可以得到50节点bf为-2,60节点 bf 为-2,30节点 bf 为 0

此时再对60节点进行右旋转:此时的50节点 bf 为 0 ,60节点bf为 1 此时的 AVL树已经达到了平衡。

private void rotateLR(TreeNode parent) {
    TreeNode subL = parent.left;
    TreeNode subLR = subL.right;
    int bf = subLR.bf;
    this.rotateRight(parent.left);
    this.rotateLeft(parent);

    if (bf == -1) {
        parent.bf = 1;
        subL.bf = 0;
        subLR.bf = 0;
    } else if (bf == 1) {
        subL.bf = -1;
        subLR.bf = 0;
        parent.bf = 0;
    }
}

右左双旋:

和左右双旋是对称的概念,此处便不再赘述了。

直接贴代码:

 private void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;
        this.rotateRight(parent.right);
        this.rotateLeft(parent);

        if(bf == 1){
            parent.bf = -1;
            subR.bf = 0;
            subRL.bf = 0;
        } else if (bf == -1) {
            parent.bf = 0;
            subR.bf = 1;
            subRL.bf =0;
        }
    }

总之AVL树,就是为了让整个树不退化成链表,才引入的旋转机制。

AVL树的不足和下期预告(红黑树)

但是AVL树虽然保证了查询的效率,但是还是有一些机制上的问题,比如说,旋转非常消耗时间,比如我们在单旋的时候已经进行了8步操作,这只是其中的一次插入,当数据大量插入的时候AVL树显然是不够用的,因此科学家们又引入了红黑树的机制。下一次我会继续写关于红黑树的博客,希望大家能够多多点赞。

上一篇:taro整体架构简析


下一篇:MongoDB 分布式 概述