前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【数据结构与算法】AVL树

【数据结构与算法】AVL树

作者头像
程序员波特
发布2024-09-29 08:02:39
520
发布2024-09-29 08:02:39
举报
文章被收录于专栏:魔法书

3.3 AVL 树

概述
历史

AVL 树是一种自平衡二叉搜索树,由托尔·哈斯特罗姆在 1960 年提出并在 1962 年发表。它的名字来源于发明者的名字:Adelson-Velsky 和 Landis,他们是苏联数学家,于 1962 年发表了一篇论文,详细介绍了 AVL 树的概念和性质。 在二叉搜索树中,如果插入的元素按照特定的顺序排列,可能会导致树变得非常不平衡,从而降低搜索、插入和删除的效率。为了解决这个问题,AVL 树通过在每个节点中维护一个平衡因子来确保树的平衡。平衡因子是左子树的高度减去右子树的高度。如果平衡因子的绝对值大于等于 2,则通过旋转操作来重新平衡树。 AVL 树是用于存储有序数据的一种重要数据结构,它是二叉搜索树的一种改进和扩展。它不仅能够提高搜索、插入和删除操作的效率,而且还能够确保树的深度始终保持在 O(log n) 的水平。随着计算机技术的不断发展,AVL 树已经成为了许多高效算法和系统中必不可少的一种基础数据结构。

前面介绍过,如果一棵二叉搜索树长的不平衡,那么查询的效率会受到影响,如下图

通过旋转可以让树重新变得平衡,并且不会改变二叉搜索树的性质(即左边仍然小,右边仍然大)

如何判断失衡?

如果一个节点的左右孩子,高度差超过 1,则此节点失衡,才需要旋转

处理高度

如何得到节点高度?一种方式之前做过的一道题目:E05. 求二叉树的最大深度(高度),但由于求高度是一个非常频繁的操作,因此将高度作为节点的一个属性,将来新增或删除时及时更新,默认为 1(按力扣说法)

代码语言:javascript
复制
static class AVLNode {
    int height = 1;
    int key;
    Object value;
    AVLNode left;
    AVLNode right;
    // ...
}

求高度代码

这里加入了 height 函数方便求节点为 null 时的高度

代码语言:javascript
复制
private int height(AVLNode node) {
    return node == null ? 0 : node.height;
}

更新高度代码

将来新增、删除、旋转时,高度都可能发生变化,需要更新。下面是更新高度的代码

代码语言:javascript
复制
private void updateHeight(AVLNode node) {
    node.height = Integer.max(height(node.left), height(node.right)) + 1;
}
何时触发失衡判断?

定义平衡因子(balance factor)如下

平衡因子 = 左子树高度 - 右子树高度

当平衡因子

  • bf = 0,1,-1 时,表示左右平衡
  • bf > 1 时,表示左边太高
  • bf < -1 时,表示右边太高

对应代码

代码语言:javascript
复制
private int bf(AVLNode node) {
    return height(node.left) - height(node.right);
}

当插入新节点,或删除节点时,引起高度变化时,例如

目前此树平衡,当再插入一个 4 时,节点们的高度都产生了相应的变化,8 节点失衡了

在比如说,下面这棵树一开始也是平衡的

当删除节点 8 时,节点们的高度都产生了相应的变化,6 节点失衡了

失衡的四种情况

LL

  • 失衡节点(图中 8 红色)的 bf > 1,即左边更高
  • 失衡节点的左孩子(图中 6)的 bf >= 0 即左孩子这边也是左边更高或等高

LR

  • 失衡节点(图中 8)的 bf > 1,即左边更高
  • 失衡节点的左孩子(图中 6 红色)的 bf < 0 即左孩子这边是右边更高

对称的还有两种情况

RL

  • 失衡节点(图中 3)的 bf <-1,即右边更高
  • 失衡节点的右孩子(图中 6 红色)的 bf > 0,即右孩子这边左边更高

RR

  • 失衡节点(图中 3)的 bf <-1,即右边更高
  • 失衡节点的右孩子(图中 6 红色)的 bf <= 0,即右孩子这边右边更高或等高
实现
解决失衡

失衡可以通过树的旋转解决。什么是树的旋转呢?它是在不干扰元素顺序的情况下更改结构,通常用来让树的高度变得平衡。

观察下面一棵二叉搜索树,可以看到,旋转后,并未改变树的左小右大特性,但根、父、孩子节点都发生了变化

代码语言:javascript
复制
      4                                   2
     / \             4 right             / \
    2   5      -------------------->    1   4
   / \         <--------------------       / \
  1   3              2 left               3   5

右旋

旋转前

  • 红色节点,旧根(失衡节点)
  • 黄色节点,旧根的左孩子,将来作为新根,旧根是它右孩子
  • 绿色节点,新根的右孩子,将来要换爹作为旧根的左孩子

旋转后

代码

代码语言:javascript
复制
private AVLNode rightRotate(AVLNode red) {
    AVLNode yellow = red.left;
    AVLNode green = yellow.right;
    yellow.right = red;
    red.left = green;
    return yellow;
}

左旋

旋转前

  • 红色节点,旧根(失衡节点)
  • 黄色节点,旧根的右孩子,将来作为新根,旧根是它左孩子
  • 绿色节点,新根的左孩子,将来要换爹作为旧根的右孩子

旋转后

代码

代码语言:javascript
复制
private AVLNode leftRotate(AVLNode red) {
    AVLNode yellow = red.right;
    AVLNode green = yellow.left;
    yellow.left = red;
    red.right = green;
    return yellow;
}

左右旋

指先左旋左子树,再右旋根节点(失衡),这时一次旋转并不能解决失衡

左子树旋转后

根右旋前

根右旋后

代码

代码语言:javascript
复制
private AVLNode leftRightRotate(AVLNode root) {
    root.left = leftRotate(root.left);
    return rightRotate(root);
}

右左旋

指先右旋右子树,再左旋根节点(失衡)

右子树右旋后

根左旋前

根左旋后

代码

代码语言:javascript
复制
private AVLNode rightLeftRotate(AVLNode root) {
    root.right = rightRotate(root.right);
    return leftRotate(root);
}

判断及调整平衡代码

代码语言:javascript
复制
private AVLNode balance(AVLNode node) {
    if (node == null) {
        return null;
    }
    int bf = bf(node);
    if (bf > 1 && bf(node.left) >= 0) {
        return rightRotate(node);
    } else if (bf > 1 && bf(node.left) < 0) {
        return rightLeftRotate(node);
    } else if (bf < -1 && bf(node.right) > 0) {
        return leftRightRotate(node);
    } else if (bf < -1 && bf(node.right) <= 0) {
        return rightRotate(node);
    }
    return node;
}

以上四种旋转代码里,都需要更新高度,需要更新的节点是红色、黄色,而绿色节点高度不变

新增
代码语言:javascript
复制
public void put(int key, Object value) {
    root = doPut(root, key, value);
}

private AVLNode doPut(AVLNode node, int key, Object value) {
    if (node == null) {
        return new AVLNode(key, value);
    }
    if (key == node.key) {
        node.value = value;
        return node;
    }
    if (key < node.key) {
        node.left = doPut(node.left, key, value);
    } else {
        node.right = doPut(node.right, key, value);
    }
    updateHeight(node);
    return balance(node);
}
删除
代码语言:javascript
复制
public void remove(int key) {
    root = doRemove(root, key);
}

private AVLNode doRemove(AVLNode node, int key) {
    if (node == null) {
        return null;
    }
    if (key < node.key) {
        node.left = doRemove(node.left, key);
    } else if (node.key < key) {
        node.right = doRemove(node.right, key);
    } else {
        if (node.left == null) {
            node = node.right;
        } else if (node.right == null) {
            node = node.left;
        } else {
            AVLNode s = node.right;
            while (s.left != null) {
                s = s.left;
            }
            s.right = doRemove(node.right, s.key);
            s.left = node.left;
            node = s;
        }
    }
    if (node == null) {
        return null;
    }
    updateHeight(node);
    return balance(node);
}

完整代码备份

代码语言:javascript
复制
public class AVLTree {
    static class AVLNode {
        int height = 1;
        int key;
        Object value;
        AVLNode left;
        AVLNode right;

        public AVLNode(int key) {
            this.key = key;
        }

        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    AVLNode root;

    private AVLNode leftRotate(AVLNode p) {
        AVLNode r = p.right;
        AVLNode b = r.left;
        r.left = p;
        p.right = b;
        updateHeight(p);
        updateHeight(r);
        return r;
    }

    private void updateHeight(AVLNode node) {
        node.height = Integer.max(height(node.left), height(node.right)) + 1;
    }

    private AVLNode rightRotate(AVLNode r) {
        AVLNode a = r.left;
        AVLNode b = a.right;
        a.right = r;
        r.left = b;
        updateHeight(r);
        updateHeight(a);
        return a;
    }

    private AVLNode leftRightRotate(AVLNode p) {
        AVLNode r = p.left;
        p.left = leftRotate(r);
        return rightRotate(p);
    }

    private AVLNode rightLeftRotate(AVLNode p) {
        AVLNode r = p.right;
        p.right = rightRotate(r);
        return leftRotate(p);
    }

    private int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }



    public void remove(int key) {
        root = doRemove(root, key);
    }

    private AVLNode doRemove(AVLNode node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            node.left = doRemove(node.left, key);
        } else if (node.key < key) {
            node.right = doRemove(node.right, key);
        } else {
            if (node.left == null) {
                node = node.right;
            } else if (node.right == null) {
                node = node.left;
            } else {
                AVLNode s = node.right;
                while (s.left != null) {
                    s = s.left;
                }
                s.right = doRemove(node.right, s.key);
                s.left = node.left;
                node = s;
            }
        }
        if (node == null) {
            return null;
        }
        updateHeight(node);
        return balance(node);
    }

    public void put(int key, Object value) {
        root = doPut(root, key, value);
    }

    private AVLNode doPut(AVLNode node, int key, Object value) {
        if (node == null) {
            return new AVLNode(key, value);
        }
        if (key == node.key) {
            node.value = value;
            return node;
        }
        if (key < node.key) {
            node.left = doPut(node.left, key, value);
        } else {
            node.right = doPut(node.right, key, value);
        }
        updateHeight(node);
        return balance(node);
    }

    private int bf(AVLNode node) {
        return height(node.left) - height(node.right);
    }

    private AVLNode balance(AVLNode node) {
        if (node == null) {
            return null;
        }
        int bf = bf(node);
        if (bf > 1 && bf(node.left) >= 0) {
            return rightRotate(node);
        } else if (bf > 1 && bf(node.left) < 0) {
            return rightLeftRotate(node);
        } else if (bf < -1 && bf(node.right) > 0) {
            return leftRightRotate(node);
        } else if (bf < -1 && bf(node.right) <= 0) {
            return rightRotate(node);
        }
        return node;
    }
}
小结

AVL树的优点:

  1. AVL树是一种自平衡树,保证了树的高度平衡,从而保证了树的查询和插入操作的时间复杂度均为O(logn)。
  2. 相比于一般二叉搜索树,AVL树对查询效率的提升更为显著,因为其左右子树高度的差值不会超过1,避免了二叉搜索树退化为链表的情况,使得整棵树的高度更低。
  3. AVL树的删除操作比较简单,只需要像插入一样旋转即可,在旋转过程中树的平衡性可以得到维护。

AVL树的缺点:

  1. AVL树每次插入或删除节点时需要进行旋转操作,这个操作比较耗时,因此在一些应用中不太适用。
  2. 在AVL树进行插入或删除操作时,为保持树的平衡需要不断进行旋转操作,在一些高并发环节和大数据量环境下,这可能会导致多余的写锁导致性能瓶颈。
  3. AVL树的旋转操作相对较多,因此在一些应用中可能会造成较大的空间浪费。

本文,已收录于,我的技术网站 pottercoding.cn,有大厂完整面经,工作技术,架构师成长之路,等经验分享!

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-09-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 3.3 AVL 树
    • 概述
      • 历史
      • 如何判断失衡?
      • 处理高度
      • 何时触发失衡判断?
      • 失衡的四种情况
    • 实现
      • 解决失衡
      • 新增
      • 删除
      • 小结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档