专栏首页javascript艺术程序员的内功心法-AVL树

程序员的内功心法-AVL树

直面弱点,不再逃避!!!

接上篇文章《二叉搜索树》了解到二叉搜索树在极端情况也不能满足我们对于查询性能的要求。

二叉树的一些统计特性

  • 第n层最多的节点个数2n-1
  • 高度为h的二叉树,最多包含2h-1个节点,所以n个节点的二叉树的最小高度是log2n + 1
  • 查找成功时,查找次数不会超过树的高度h

二叉树查询性能的衡量

我们下面来使用 A - H字符来观察二叉搜索树在不同的插入顺序下构造的树的结果

自然顺序的平均查找长度为ASL=(1+ 2 + 3 + 4+ 5+ 6+ 7 +8) / 8 = 4.5

计算特定顺序的平均查找长度ASL=(1 + 2*2 + 3*4 + 4*1) / 8 = 2.6

当我们数据相同,但是采用不同的插入顺序,使平均查找长度不一样。所以我们要解决这个问题,先观察两个初始化方式两个树的特点,大致发现使用特定顺序初始化的树,感觉树的节点分布比较平衡。由于统计特点3和特点2,我们希望n个节点的二叉树的接近log2n + 1,那么我们就可以最大化的提升查询性能.

所以为了解决这个问题,我们引入新的二叉搜索树实现-平衡二叉树(AVL树)

AVL树内容定义

  • 平衡因子BalanceFactor:左右子树的高度差BF=HL - HR
  • 规定左右子树的高度差的绝对值不超过1 |BF| ≤ 1

节点定义

原有节点的基础上增加height属性

class AVLNode<T extends Comparable<T>> {

    private T data;

    //左节点
    private AVLNode<T> left;

    //右节点
    private AVLNode<T> right;

    //当前节点的高度
    private int height;
}

高度计算

由于平衡二叉树的平衡指高度方面的平衡,我们先来计算树的高度

树的高度H指:左HL右HR子树高度的最大值 + 1

}

查找

由于平衡二叉树也是二叉查找树的一种,查询方式和二叉搜索树相同,不再赘述。

调整平衡

为了保证左右平衡,所以我们一系列的操作来维持左右子树的高度在BF规定的范围之内

插入分类

空树时,直接初始化为根结点。

针对作为子节点的插入,插入节点只能为被插入节点的左节点B或者右节点F。而被插入节点D可以是其父节点G的左节点或其父节点A的右节点。所以我们将所有情况分为4类GDB路径(LL插入)、GDF路径(LR插入)、ADF路径(RR插入)、ADB路径(RL插入)

接下来我们将处理所有的情况

RR插入

当插入节点在右子树的右节点上(ADF路径

操作步骤:

  1. 将右子节点D作为根节点
  2. 原根节点A作为新根节点D的左子节点
  3. 将D节点的左子节点B设置为原根节点A的右子节点

实现代码如下:

AVLNode<T> singleRightRotation(AVLNode<T> node) {
    AVLNode<T> result = node.getRight();
    AVLNode<T> left = result.getLeft();
    node.setRight(left);
    result.setLeft(node);
    return result;
}

LL插入

当插入的节点在左子树的左节点上(GDB路径

操作步骤:

  1. 将左子节点D作为根结点
  2. 原根节点G作为新根节点D的右子节点
  3. 将D节点的右子节点F作为原结点G的左子节点

实现代码:

}
RL插入

当插入的节点在右子树的左节点上(ADB路径)

操作步骤:

  • 针对A节点的右子节点D做左旋转
  • 针对A节点做右旋转

实现代码:

AVLNode<T> doubleRightLeftRotation(AVLNode<T> node){
    AVLNode<T> right = singleLeftRotation(node.getRight());
    node.setRight(right);
    return singleRightRotation(node);
}
LR插入

当插入的节点在右子树的左节点上(GDF路径)

操作步骤:

  • 针对G节点的左子节点D做右旋转
  • 针对G节点做左旋转

实现代码:

AVLNode<T> doubleLeftRightRotation(AVLNode<T> node) {
    AVLNode<T> left = singleRightRotation(node.getLeft());
    node.setLeft(left);
    return singleLeftRotation(node);
}

删除节点

我们在删除节点时,思路:

  • 叶子节点直接删除
  • 包含一个子节点,将子节点替换到父节点
  • 包含两个子节点,使用后继节点替换被删除节点,删除后继节点即可 更详细的可以回顾下《二叉搜索树》的内容

平衡调整的思路:节点被删除后,相当于在兄弟节点插入新的节点

代码如下:

AVLNode<T> delete(AVLNode<T> node, T data) {

由于AVL是一个高度严格平衡的二叉搜索树,查找效率在log2n级别。但是在维护节点高度平衡时,需要进行旋转操作(插入时最多两次旋转;删除节点时AVL树需要调整整个查询路径的高度平衡,最多需要log2n次旋转)

后面,我们将介绍另外一种平衡搜索二叉树(红黑树)!

欢迎大家关注留言分享和我交流!

本文分享自微信公众号 - javascript艺术(gh_4e5484fd6b52),作者:郭里奥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-27

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员的内功心法-234树

    红黑树、B树、B+树,都是软件开发中一个比较难理解和掌握的知识点。他们的本质依然是平衡二叉搜索树。如果直接去学习红黑树、B树、B+树的知识点,无异于雾里看花。这...

    javascript艺术
  • 程序员内功心法-设计模式

    房上的猫
  • 程序员内功心法《设计模式》

    设计模式是在软件工程实践过程中,JAVA使用者们总结出的良好的编程方法,使用设计模式能够增加系统的健壮性,易修改性和可扩展性,当你进行开发的软件规模比较大的时候...

    Java架构
  • 程序员的内功心法,你不来看看吗?

    在生活中我们经常会使用到搜索的功能。在我们数据量不大的情况下,可以使用每次遍历全部数据,查询我们的目标数据。当数据量增加时,我们遍历的方式就有些力不从心了;也...

    javascript艺术
  • 数据结构图文解析之:AVL树详解及C++模板实现

    Tencent JCoder
  • 图解:数据结构中的6种「树」,大鹏问你心中有数吗?

    数据结构这门课程是计算机相关专业的基础课,数据结构指的是数据在计算机中的存储、组织方式。

    灵魂画师牧码
  • 《Mac OS系统架构》程序员内功心法索引

    对这幅图的探索已经是3天了~ 它像极了一份神功秘籍 在这份秘籍的指引下 似乎冥冥之中为你的体内注入绵绵深厚的内力 在程序员大神之路的漫长探索过程中 这张图的出现...

    企鹅号小编
  • [TcaplusDB知识库]键值型数据库TcaplusDB是如何进行数据读写的?

    数据库最核心的功能是把数据存储下来,并提供快速读、写能力,因此,对于一个数据库来说,数据的读写是最基础而重要的业务。

    Tcaplus君
  • 算法学习笔记

    这是一个算法题目合集,题目是我从网络和书籍之中整理而来,部分题目已经做了思路整理。问题分类包括:

    芋道源码
  • 数据结构之AVL树

    我们先来回忆一下二分搜索树所存在的一个问题:当我们按顺序往二分搜索树添加元素时,那么二分搜索树可能就会退化成链表。例如,现在有这样一颗二分搜索树:

    端碗吹水
  • 了解红黑树的起源,理解红黑树的本质

    前面两节,我们一起学习了关于跳表的理论知识,并手写了两种完全不同的实现,我们放一张图来简单地回顾一下:

    彤哥
  • 程序员内功:八大排序算法

    版权声明:本文为博主原创文章,未经博主允许不得转载。个人网站:http://cuijiahua.com。 ...

    Jack_Cui
  • 菜鸟网络java岗面经 已拿offer

    牛客网
  • 自已动手作图搞清楚AVL树

    二叉树是一种常用的数据结构,更是实现众多算法的一把利器。 二分搜索树(Binary Search Tree)做为一种能实现快速定位查找的二叉树也得到了广泛应用

    智慧zhuhuix
  • 聊聊java中的哪些Map:(九)TreeMap源码分析

    可以看到,TreeMap继承了AbstractMap,此外实现了NavigableMap、Cloneable和Serializable接口。而Navigable...

    冬天里的懒猫
  • 聊聊整体性学习方法

    「整体性学习方法」是在一本叫做《如何高效学习》的书中看到的。这本书的作者是个老外,他用一年就学完了四年的麻省理工课程。而这本书正是其这一年来的学习心得,书中介绍...

    陈树义
  • 聊聊整体性学习方法

    「整体性学习方法」是在一本叫做《如何高效学习》的书中看到的。这本书的作者是个老外,他用一年就学完了四年的麻省理工课程。而这本书正是其这一年来的学习心得,书中介绍...

    范蠡
  • 其实算法就这么点东西

    以笔试为目的的修炼都是耍流氓。但也许,我们就想当个好流氓。秋招已到,希望大家都能收货满意的offer。

    程序员小浩
  • 轻松搞定面试中的红黑树问题

    http://blog.csdn.net/silangquan/article/details/18655795

    bear_fish

扫码关注云+社区

领取腾讯云代金券