C++AVL树4种旋转详讲(左单旋、右单旋、左右双旋、右左双旋)

C++AVL树4种旋转详讲

什么是AVL树?

AVL树是一种自平衡二叉搜索树,它在插入或删除一个节点时,会通过旋转操作进行自平衡。AVL树的特点是保证树的高度始终保持在O(logN)的水平,从而保证了树的查询、插入、删除等操作时间复杂度保持在O(logN)的水平。因此在大规模数据的场景下,使用AVL树能够取得很好的性能表现。

AVL树的基本操作

AVL树的基本操作包含插入节点、删除节点以及查找节点三个操作。由于AVL树是一种自平衡树,因此对于插入与删除操作时,需要进行旋转操作来使树自平衡。

在 AVL 树的删除操作中,当一个节点被删除时,需要找到它的后序中继节点来继承该节点。然后,当对继承的节点进行重平衡时,如果无法确定其子节点的高度(或在重平衡期间降低其他节点的高度)则可能需要进行额外的旋转。

AVL树的4种旋转

左单旋转(left-rotation)

在 AVL 树的 左叶子节点过重 的情况下,需要进行左单旋转来使树保持平衡。左单旋转的基本操作是:将该节点旋转成其右节点的左儿 子,然后维护该节点以及其右节点之间的连接关系。

示例:

        A (-2)                                 B (0)
       /  \               左单旋转             /   \
     B (0)  C (1)         ------>           D     A (0)
    /  \                     A                /     / \
  D (0) E (0)                              E     F   C (1)
        \
       F (0)

右单旋转(right-rotation)

在 AVL 树的 右叶子节点过重 的情况下,需要进行右单旋转来使树保持平衡。右单旋转的基本操作是:将该节点旋转成其左节点的右儿 子,然后维护该节点以及其左节点之间的连接关系。

示例:

          A (2)                             B (0)
         /  \              右单旋转          /   \
       B (0) C (-1)       ------>         A (0)  D
      /  \                              / \    \
    D (0) E (0)                        F   C (-1) E
        /
      F (0)

左右双旋转(left-right-rotation)

在 AVL 树的 左孙子节点过重 的情况下,需要进行左右双旋转来使树保持平衡。左右双旋转的基本操作是:将该节点的右节点进行右单旋转,然 后再将该节点进行左单旋转。最后维护该节点的祖先节点的连接关系。

示例:

        A (-2)                                A (-2)                                C (0)
       /  \               左右双旋转            /  \               左旋转             /   \
     B (1)  C (0)         ------>          B(0)  C (2)          ------>         A (0)   B (0)
    / \    /  \                              /       \                          /  \      \
  D (0) E (1) F (0)                        D         F (1)                      D    E (0)  F (0)
         \                                   \
        G(0)                                 G (0)

右左双旋转(right-left-rotation)

在 AVL 树的 右孙子节点过重 的情况下,需要进行右左双旋转来使树保持平衡。右左双旋转的基本操作是:将该节点的左节点进行左单旋转,然 后再将该节点进行右单旋转。最后维护该节点的祖先节点的连接关系。

示例:

        A (2)                                A (2)                                  C (0)
       /  \               右左双旋转           /   \               右旋转             /   \
     B (-1) C (0)         ------>          B(-1) C (2)          ------>          A (0)   B (0)
    /     / \                                /     \                                   /   \
  D  (0) E  (1) F (0)                      D  (0)   E  (0)                            D     F (0)
         /                                      \
       G (0)                                     G (0)

总结

AVL树是一种高效的自平衡二叉搜索树,其基本操作包括插入、删除和检索操作。在插入和删除操作时,由于需要保证树的平衡,因此需要进行旋转操作。其中常用的四种旋转操作包括左单旋转、右单旋转、左右双旋转和右左双旋转。在实际使用中,根据情况选择不同的旋转方式可以提高性能表现。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++AVL树4种旋转详讲(左单旋、右单旋、左右双旋、右左双旋) - Python技术站

(0)
上一篇 2023年5月22日
下一篇 2023年5月22日

相关文章

  • CDay03

    字符类型 编码 char类型采用ASCII编码,占1个字节,只用了7位(最高位是0),能表示128个字符。 需要记忆的: 空字符 ‘\0’ = 0 ‘ ‘ = 32 ‘0’ = 48 ‘A’ = 65 ‘a’ = 97 转义序列 字符转义序列 数字转义序列 八进制:以 \ 开头,后面最多接三个八进制数 十六进制:以 \x 开头,后面接十六进制数 字符处理函数…

    C语言 2023年4月18日
    00
  • c/c++获取系统时间函数的方法示例

    获取系统时间是编程中常用的功能之一,c/c++提供了多种方法来获取系统时间。下面将介绍获取系统时间的常用方法。 获取系统时间的常用函数 1. time() time()函数返回从1970年1月1日0时0分0秒到当前时间的秒数。time函数的详细定义如下: #include <time.h> time_t time(time_t *timer); …

    C 2023年5月30日
    00
  • C语言详细讲解#error与#line如何使用

    C语言详细讲解 #error与#line如何使用 简介 在C语言中,#error和#line是两个预处理器指令,可以用于编写更好的代码。#error指令用于在遇到错误时生成编译错误,而#line指令用于更改编译器输出的行号和文件名。 #error指令 error指令用于在源代码中显示一个错误消息,并且在编译时会生成一个错误。它的语法如下: #error me…

    C 2023年5月23日
    00
  • 结构体的(.)操作符和(->)操作符区别

    一、结构体的 . 操作符二、结构体的 -> 操作符三、点操作符的优先性和结合性四、总结 一、结构体的 .操作符 1.结构体成员的直接访问:结构体变量的成员是通过操作符 . 访问的。 二、结构体的->操作符 1.结构体成员的间接访问:当我们拥有一个 指向结构体的指针 ,我们访问这个结构的成员的方式是 对指针执行间接访问操作 ,然后再通过 点操作符 …

    C语言 2023年4月18日
    00
  • C语言 while循环

    当我们需要重复执行某个代码块直到满足条件时,可以使用循环语句。C语言提供了三种循环语句:while、for和do-while。其中,while语句用于不确定循环次数的情况。下面是while循环的使用攻略。 while循环基本语法 while循环的基本语法如下: while (condition) { statement; } 其中,condition为循环条…

    C 2023年5月9日
    00
  • C++用new创建对象和不用new创建对象的区别解析

    C++中,我们可以通过new关键字来动态地创建对象。在new关键字的帮助下,我们可以在程序运行时动态地分配内存,并在该内存中创建一个新的对象。与此相对,我们也可以在静态方式下创建对象,即在栈空间中创建对象或全局空间创建对象。下面,我们将详细讲解C++中使用new关键字和静态方式创建对象的区别以及应用场景。 使用new创建对象的区别 内存分配位置不同:使用ne…

    C 2023年5月22日
    00
  • C语言实现车辆信息管理系统

    C语言实现车辆信息管理系统攻略 1. 系统需求分析 在实现车辆信息管理系统之前,我们需要对系统进行需求分析,明确系统所需要实现的功能和对应的数据结构。下面是该系统的功能描述和数据结构设计: 功能描述 添加车辆信息 删除车辆信息 修改车辆信息 查询车辆信息 显示所有车辆信息 数据结构设计 车辆信息包括以下属性: 车牌号 车型 车主姓名 车主电话 因此,我们可以…

    C 2023年5月23日
    00
  • JSON在Java中的使用方法实例

    下面是JSON在Java中的使用方法实例的详细攻略: 什么是JSON JSON是一种轻量级的数据交换格式,全称为JavaScript Object Notation。它是一种易于读写的文本格式,可与几乎所有编程语言一起使用,包括Java。 Java中的JSON库 Java中有多个库可以用于处理JSON,其中最流行的库是GSON和Jackson。这里我们以GS…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部