AVL树

介绍

AVL树是最常见的自平衡二叉搜索树了。关于二叉搜索树大致的描述如下:

  1. 每个节点只有左右两个子节点
  2. 每个节点的左子节点的值小于该节点值,每个节点的右子节点的值大于该节点的值

AVL树是一颗平衡二叉树,所谓平衡的概念如下:
二叉搜索树中任何一个节点,左子树的高度与右子树的高度差小于等于1。子树的高度定义为子树的左右子树中高度大的值。

当一个二叉搜索树为平衡二叉树的时候,查询效率是很高的,时间复杂度为O(lgn)。但如果对这个树做了多次的插入与删除操作后,这个树就很可能失去了平衡,变成了一个链表结构。

AVL树插入与删除节点后都需要重新计算当前节点是否平衡,如果不平衡,则通过旋转来使节点保持平衡。

旋转

旋转有四种情况,左旋转两种,右旋转两种,其中左旋转与右旋转是镜对称动作,我们只看左旋转就好。参考如下两张图,应该可以很清晰的说明两种左旋转的过程。注意:旋转前后,颜色相同的节点代表了值相同的节点。 右旋的操作,可以自己去画一下。

左旋一

左旋一

左旋二

左旋二

关于删除

突然发现,二叉查找树中节点的删除其实也不是一个特别简单的过程。所以单开一个小节来描述一下。

通用方法

当需要删除一个节点的时候我们需要的操作如下:

  1. 持有该节点的父节点与子节点
  2. 断开父节点到该节点的连接,以及该节点到子节点的连接
  3. 如果该节点没有右子节点,则将该节点的左子节点设置为父节点的左子节点,结束
  4. 如果该节点有右子节点,则需要从右子节点中找到最小值的节点,然后做如下操作
    4.1 如果最小值节点就是当前节点的右子节点,则将最小值节点设置为父节点的左子节点,然后把原左子节点设置为最小值节点的左子节点,结束
    4.2 如果最小值节点不是当前节点的右子节点,则需要在右子节点的子树中删除最小值节点,然后创建新的最小时节点,将新的最小时节点设置为父节点的左子节点,然后把原左子节点设置为新的最小值节点的左子节点,右子节点为新的最小值节点的右子节点,结束。

看图

红色的节点表示删除后需要重新计算高度并判断是否需要旋转的节点

步骤3的删除操作

步骤3的场景

步骤4.1的删除操作

步骤4.1的场景

步骤4.2的删除操作

步骤4.2的场景

这个图里,oldRight到minNode的虚线表示的意思是minNode不一定是oldRight的直接左子节点,有可能是很多层之后的一个子节点。但肯定在oldRight为根的树中,它是最左边的。

Talk is cheap

/**
 * AVL树节点类
 * 节点中持有的对象的类必须实现Comparable接口
 * 此类中封装了计算子树高度,计算自身节点高度,判断是否需要旋转,以及旋转实现的方法 作为树节点的基础功能
 *
 * @author goofy.wang
 */
public class AVLNode<T extends Comparable> implements Comparable<AVLNode<T>>{

    private T value;

    private int leftDepth;

    private int rightDepth;

    private AVLNode<T> left;

    private AVLNode<T> right;

    public AVLNode(T value) {
        this(value, null, null);
    }


    public AVLNode(T value, AVLNode<T> left, AVLNode<T> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public AVLNode<T> getLeft() {
        return this.left;
    }

    public void setLeft(AVLNode<T> left) {
        this.left = left;
    }

    public AVLNode<T> getRight() {
        return this.right;
    }

    public void setRight(AVLNode<T> right) {
        this.right = right;
    }

    public void setValue(T value){
        this.value = value;
    }


    public T getValue(){
        return this.value;
    }


    public boolean hasLeft(){
        return this.left != null;
    }


    public boolean hasRight(){
        return this.right != null;
    }

    /**
     * 获取当前节点深度的方法
     * @return
     */
    public int getDepth(){
        int maxSubDepth = this.leftDepth > this.rightDepth ? this.leftDepth : this.rightDepth;
        return maxSubDepth + 1;
    }

    /**
     * 计算左右子树深度的方法
     */
    public void calculateDepth(){
        this.leftDepth = this.left == null ?  0 :  this.left.getDepth();
        this.rightDepth = this.right == null ?  0 :  this.right.getDepth();
    }

    /**
     * 判断是否需要旋转
     * @return
     */
    public boolean needRotate(){
        return Math.abs(this.leftDepth - this.rightDepth) > 1;
    }

    /**
     * 旋转方法,内部判断需要左旋还是右旋
     */
    public void rotate(){
        if(this.leftDepth > this.rightDepth){
            this.leftRotateToRight();
        }else{
            this.rightRotateToLeft();
        }
        this.calculateDepth();
    }

    /**
     * 左旋方法
     * if 实现旋转一
     * else 实现旋转二
     */
    private void leftRotateToRight(){

        AVLNode<T> leftRight = this.left.getRight();
        T currentValue = this.getValue();

        if(leftRight == null){
            T leftValue = this.left.getValue();
            AVLNode<T> newRight = new AVLNode<T>(currentValue, null, this.getRight());
            newRight.calculateDepth();
            this.setValue(leftValue);
            this.setRight(newRight);
            this.setLeft(this.getLeft().getLeft());
        }else{
            T leftRightValue = leftRight.getValue();
            AVLNode<T> leftRightLeft = leftRight.getLeft();
            AVLNode<T> leftRightRight = leftRight.getRight();
            AVLNode<T> newRight = new AVLNode<T>(currentValue, leftRightRight, this.getRight());
            newRight.calculateDepth();
            this.setValue(leftRightValue);
            this.setRight(newRight);
            this.left.setRight(leftRightLeft);
            this.left.calculateDepth();
        }
    }


    /**
     * 右旋方法,与左旋镜对称
     */
    private void rightRotateToLeft(){

        AVLNode<T>  rightLeft = this.right.getLeft();
        T currentValue = this.getValue();

        if(rightLeft == null){
            T rightValue = this.right.getValue();
            AVLNode<T> newLeft = new AVLNode<T>(currentValue, this.left, null);
            newLeft.calculateDepth();
            this.setValue(rightValue);
            this.setLeft(newLeft);
            this.setRight(this.right.getRight());
        }else{
            T rightLeftValue = rightLeft.getValue();
            AVLNode<T> rightLeftLeft = rightLeft.getLeft();
            AVLNode<T> rightLeftRight = rightLeft.getRight();
            AVLNode<T> newLeft = new AVLNode<T>(currentValue, this.left,  rightLeftLeft);
            newLeft.calculateDepth();
            this.setValue(rightLeftValue);
            this.setLeft(newLeft);
            this.right.setLeft(rightLeftRight);
            this.right.calculateDepth();
        }
    }

    /**
     * 比较方法
     * @param o
     * @return
     */
    @Override
    public int compareTo(AVLNode<T> o) {
        return this.value.compareTo(o.getValue());
    }
}

/**
 * AVL树类
 * 此类用于组织AVLNode节点,使得这些节点以正确的平衡二叉树方式关联在一起
 * 并在添加与删除元素后,控制树节点完成高度计算,平衡性判断,以及旋转等行为
 *
 * @author goofy.wang
 */
public class AVLTree<T extends Comparable> {

    private AVLNode<T> root;

    /**
     * 添加节点的方法,如果值在树中存在相等的节点,则将此节点中的值替换为当前值
     * @param nodeValue
     */
    public void append(T nodeValue){
        AVLNode<T> newNode = new AVLNode<T>(nodeValue);
        if(this.root == null){
            this.root = newNode;
        }else{
            this.innerAppend(this.root, newNode);
        }
    }

    /**
     * 判断树中是否存在某个值对象的方法
     * @param nodeValue
     * @return
     */
    public boolean contains(T nodeValue){
        if(this.root == null){
            return false;
        }
        AVLNode<T> condition = new AVLNode<T>(nodeValue);
        if(root.compareTo(condition) == 0){
            return true;
        }else{
            return this.containsInChilren(this.root, condition);
        }
    }

    /**
     * 从树中删除某个值对象的方法
     * @param nodeValue
     * @return 如果存在该元素且删除完成返回true,如果不存在该元素则返回false
     */
    public boolean remove(T nodeValue){

        if(root == null){
            return false;
        }

        AVLNode<T> toBeRemove = new AVLNode<T>(nodeValue);
        if(root.compareTo(toBeRemove) == 0){
            if(root.hasRight()){

                AVLNode<T> minumumNodeFromRight = this.getMinumumNode(this.root.getRight());
                if(this.root.getRight().compareTo(minumumNodeFromRight) == 0){
                    AVLNode<T> left = this.root.getLeft();
                    this.root.getRight().setLeft(left);
                    this.root = this.root.getRight();
                }else{
                    this.innerDelete(this.root.getRight(), minumumNodeFromRight);
                    minumumNodeFromRight.setRight(this.root.getRight());
                    minumumNodeFromRight.setLeft(this.root.getLeft());
                    this.root = minumumNodeFromRight;
                }
                this.calcAndRotateIfNeeded(this.root);
            }else{
                this.root = this.root.getLeft();
            }
        }else{
            this.innerDelete(this.root, toBeRemove);
        }
        return false;
    }

    private void innerAppend(AVLNode<T> currentNode, AVLNode<T> newNode){
        int compareResult = currentNode.compareTo(newNode);
        if(compareResult > 0){
            if(currentNode.hasLeft()){
                this.innerAppend(currentNode.getLeft(), newNode);
            }else{
                currentNode.setLeft(newNode);
            }
        }else if(compareResult < 0){
            if(currentNode.hasRight()){
                this.innerAppend(currentNode.getRight(), newNode);
            }else{
                currentNode.setRight(newNode);
            }
        }else{
            currentNode.setValue(newNode.getValue());
        }

        /**
         *
         * 此方法是标准的二叉树插入操作,唯一要注意的是下面这行代码
         * 因为我们是递归调用innerAppend方法,直到把要插入的节点放到正确的位置上
         * 所以在节点被放置完毕后,此节点的所有父节点都需要重新计算一次高度,并在必要时进行旋转
         *
         * 只有一个例外,就是当节点是更新操作的时候,是不需要执行下面这行代码的
         * 其实我们可以通过boolean变量来控制是否要执行,不过我比较懒
         *
         */
        this.calcAndRotateIfNeeded(currentNode);
    }


    private boolean containsInChilren(AVLNode<T> currentNode, AVLNode<T> condition){

        if(currentNode == null){
            return false;
        }

        int compareResult = currentNode.compareTo(condition);
        if(compareResult > 0){
            return this.containsInChilren(currentNode.getLeft(), condition);
        }else if(compareResult < 0){
            return this.containsInChilren(currentNode.getRight(), condition);
        }else{
            return true;
        }
    }


    /**
     * 删除方法,因为我们在执行删除逻辑的时候,需要处理当前节点的父节点与子节点的关系,所以把父节点作为参数传递进来
     * 方法内不判断是否要删除父节点,而是判断是否要删除父节点的子节点
     * @param parentNode
     * @param condition
     * @return
     */
    private boolean innerDelete(AVLNode<T> parentNode, AVLNode<T> condition){

        int compareResult = parentNode.compareTo(condition);
        boolean deleted = false;

        if(compareResult > 0 && parentNode.hasLeft()){
            /**
             * 如果父节点比当前要删除的节点大,并且当前父节点存在左节点
             * 则判断当前父节点的左节点是否是要删除的节点,如果是就删除当前父节点的左节点
             * 如果不是则递归
             */
            AVLNode<T> leftSub = parentNode.getLeft();
            if(leftSub.compareTo(condition) == 0){
                this.realDeleteLeft(parentNode);
                deleted = true;
            }else{
                deleted = this.innerDelete(leftSub, condition);
            }
        }else if(parentNode.hasRight()){
            AVLNode<T> rightSub = parentNode.getRight();
            if(rightSub.compareTo(condition) == 0){
                this.realDeleteRight(parentNode);
                deleted = true;
            }else{
                deleted = this.innerDelete(rightSub, condition);
            }
        }

        /**
         * 如果确实删除了当前节点的某个层级子节点,则当前节点需要重新计算高度,并有可能完成旋转
         */
        if(deleted){
            this.calcAndRotateIfNeeded(parentNode);
        }
        return deleted;
    }

    private void realDeleteLeft(AVLNode<T> parentNode){

        AVLNode<T> toBeDelete = parentNode.getLeft();
        AVLNode<T> oldLeft = toBeDelete.getLeft();
        AVLNode<T> oldRight = toBeDelete.getRight();

        if(oldRight == null) {
            /**
             * 当前要删除的节点不存在右子树
             * 删除逻辑3的场景
             */
            parentNode.setLeft(oldLeft);
        }else{
            AVLNode<T> minumumNodeFromRight = this.getMinumumNode(oldRight);
            if(minumumNodeFromRight.compareTo(oldRight) == 0){
                /**
                 * 要删除的右子树的根节点没有左节点
                 * 删除逻辑4.1的场景
                 */
                parentNode.setLeft(oldRight);
                oldRight.setLeft(oldLeft);
            }else{
                /**
                 * 要删除的节点的右子树的根节点存在比根节点还小的子节点
                 * 但是这个要找的节点的位置还不确定,所以我偷懒用递归从右子树中删除最小节点
                 * 删除逻辑4.2的场景
                 */
                this.innerDelete(oldRight, minumumNodeFromRight);
                parentNode.setLeft(minumumNodeFromRight);
                minumumNodeFromRight.setLeft(oldLeft);
                minumumNodeFromRight.setLeft(oldRight);
            }
            this.calcAndRotateIfNeeded(parentNode.getLeft());
        }
    }


    private void realDeleteRight(AVLNode<T> parentNode){

        AVLNode<T> toBeDelete = parentNode.getRight();
        AVLNode<T> oldLeft = toBeDelete.getLeft();
        AVLNode<T> oldRight = toBeDelete.getRight();

        if(oldRight == null){
            parentNode.setRight(oldLeft);
        }else{

            AVLNode<T> minumumNodeFromRight = this.getMinumumNode(oldRight);
            if(oldRight.compareTo(minumumNodeFromRight) == 0) {
                /**
                 * 走入这个分支,说明要删除的节点的右子树的根节点没有左子树
                 */
                parentNode.setRight(oldRight);
                oldRight.setLeft(oldLeft);
            }else{
                this.innerDelete(oldRight, minumumNodeFromRight);
                parentNode.setRight(minumumNodeFromRight);
                minumumNodeFromRight.setRight(oldRight);
                minumumNodeFromRight.setLeft(oldLeft);
            }

            this.calcAndRotateIfNeeded(parentNode.getRight());
        }
    }

    /**
     * 给定一个节点,从这个节点和这个节点的所有子节点中找到值最小的节点
     * @param currentNode
     * @return
     */
    private AVLNode<T> getMinumumNode(AVLNode<T> currentNode){
        if(currentNode.hasLeft()){
            return this.getMinumumNode(currentNode.getLeft());
        }else{
            return currentNode;
        }
    }

    /**
     * 重新计算节点高度,并在需要旋转时控制节点进行旋转的方法
     * 当某个节点的子节点高度发生变化的时候,会调用这个方法
     * @param node
     */
    private void calcAndRotateIfNeeded(AVLNode<T> node){
        node.calculateDepth();
        if(node.needRotate()){
            node.rotate();
        }
    }

}

预告

接下来我想写的是多路查找树中的2-3树

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,817评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,329评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,354评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,498评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,600评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,829评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,979评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,722评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,189评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,519评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,654评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,329评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,940评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,762评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,993评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,382评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,543评论 2 349

推荐阅读更多精彩内容