Titan笔记

  • 首页
  • Java
  • 数据结构
  • C语言
  • Web
  • 杂谈
  • 移动开发
  • 逸笔挥墨
Titan笔记
分享学习,研究与开发的点滴记忆
  1. 首页
  2. 数据结构
  3. 正文

[数据结构] 平衡二叉查找树 (AVL树)

2020年3月22日 1699点热度 7人点赞 4条评论

AVL树(平衡二叉查找树)

AVL树本质上是一颗二叉查找树,但是它又具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为平衡二叉树。下面是平衡二叉树和非平衡二叉树对比的例图:

[数据结构] 平衡二叉查找树 (AVL树)插图

平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1<=bf<=1;

AVL树的作用:

  我们知道,对于一般的二叉搜索树(Binary Search Tree),其期望高度(即为一棵平衡树时)为log2n,其各操作的时间复杂度(O(log2n))同时也由此而决定。但是,在某些极端的情况下(如在插入的序列是有序的时),二叉搜索树将退化成近似链或链,此时,其操作的时间复杂度将退化成线性的,即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况,但是在进行了多次的操作之后,由于在删除时,我们总是选择将待删除节点的后继代替它本身,这样就会造成总是右边的节点数目减少,以至于树向左偏沉。这同时也会造成树的平衡性受到破坏,提高它的操作的时间复杂度。
  例如:我们按顺序将一组数据1,2,3,4,5,6分别插入到一颗空二叉查找树和AVL树中,插入的结果如下图:

[数据结构] 平衡二叉查找树 (AVL树)插图1[数据结构] 平衡二叉查找树 (AVL树)插图2

由上图可知,同样的结点,由于插入方式不同导致树的高度也有所不同。特别是在带插入结点个数很多且正序的情况下,会导致二叉树的高度是O(N),而AVL树就不会出现这种情况,树的高度始终是O(lgN).高度越小,对树的一些基本操作的时间复杂度就会越小。这也就是我们引入AVL树的原因。

AVL树的基本操作:

AVL树的操作基本和二叉查找树一样,这里我们关注的是两个变化很大的操作:插入和删除!

我们知道,AVL树不仅是一颗二叉查找树,它还有其他的性质。如果我们按照一般的二叉查找树的插入方式可能会破坏AVL树的平衡性。同理,在删除的时候也有可能会破坏树的平衡性,所以我们要做一些特殊的处理,包括:单旋转和双旋转!

AVL树的插入,单旋转的第一种情况  右旋
[数据结构] 平衡二叉查找树 (AVL树)插图3

由上图可知:在插入之前树是一颗AVL树,而插入之后结点T的左右子树高度差的绝对值不再 < 1,此时AVL树的平衡性被破坏,我们要对其进行旋转。由上图可知我们是在结点T的左结点的左子树上做了插入元素的操作,我们称这种情况为左左情况,我们应该进行右旋转(只需旋转一次,故是单旋转)。具体旋转步骤是:

T向右旋转成为L的右结点,同时,Y放到T的左孩子上。这样即可得到一颗新的AVL树,旋转过程图如下:

[数据结构] 平衡二叉查找树 (AVL树)插图4

 

左左情况的右旋举例:

[数据结构] 平衡二叉查找树 (AVL树)插图5

AVL树的插入,单旋转的第二种情况  左旋

[数据结构] 平衡二叉查找树 (AVL树)插图6

由上图可知:在插入之前树是一颗AVL树,而插入之后结点T的左右子树高度差的绝对值不再 < 1,此时AVL树的平衡性被破坏,我们要对其进行旋转。由上图可知我们是在结点T的右结点的右子树上做了插入元素的操作,我们称这种情况为右右情况,我们应该进行左旋转(只需旋转一次,故事单旋转)。具体旋转步骤是:

T向右旋转成为R的左结点,同时,Y放到T的左孩子上。这样即可得到一颗新的AVL树,旋转过程图如下:

[数据结构] 平衡二叉查找树 (AVL树)插图7

右右情况的左旋举例:

[数据结构] 平衡二叉查找树 (AVL树)插图8

以上就是插入操作时的单旋转情况!我们要注意的是:谁是T谁是L,谁是R还有谁是X,Y,Z!T始终是开始不平衡的左右子树的根节点。显然L是T的左结点,R是T的右节点。X、Y、Y是子树当然也可以为NULL.NULL归NULL,但不能破坏插入时我上面所说的左左情况或者右右情况。

AVL树的插入,双旋转的第一种情况  左右(先左后右)旋
[数据结构] 平衡二叉查找树 (AVL树)插图9

由上图可知,我们在T结点的左结点的右子树上插入一个元素时,会使得根为T的树的左右子树高度差的绝对值不再 < 1,如果只是进行简单的右旋,得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转:

[数据结构] 平衡二叉查找树 (AVL树)插图10

左右情况的左右旋转实例:

[数据结构] 平衡二叉查找树 (AVL树)插图11

AVL树的插入,双旋转的第二种情况  右左(先右后左)旋

由上图可知,我们在T结点的右结点的左子树上插入一个元素时,会使得根为T的树的左右子树高度差的绝对值不再 < 1,如果只是进行简单的左旋,得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转:

[数据结构] 平衡二叉查找树 (AVL树)插图12

右左情况的右左旋转实例:

[数据结构] 平衡二叉查找树 (AVL树)插图13

以上关于二叉树的介绍转载自 https://www.cnblogs.com/zhuwbox/p/3636783.html ,很具体,便于理解。

下面提供我所写的插入(建树)操作代码以供参考

#include<stdio.h>
#include<stdlib.h>
//平衡二叉树 AVL树的实现 By Titan
typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode{
  int Data;
  Position Left;
  Position Right;
  int Height;
}; 

int Max(int a,int b){
  return a > b ? a : b;
}
int getHeight(AVLTree T){
  if(!T){
    return -1;
  }else{
    return T->Height;
  }
}
int getMaxHeight(AVLTree A,AVLTree B){
  return Max(getHeight(A),getHeight(B));
}

//定义右单旋
AVLTree S_RR(AVLTree A){
  AVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = getMaxHeight(A->Right,A->Left)+1;
    B->Height = getMaxHeight(A->Right,A->Left)+1;
    return B;
}
//定义左单旋
AVLTree S_LR(AVLTree A){
  AVLTree B=A->Right;
  A->Right=B->Left;
  B->Left=A;
  A->Height = getMaxHeight(A->Right,A->Left)+1;
    B->Height = getMaxHeight(A->Right,A->Left)+1;
    return B;
}
//定义左右双旋(先左旋后右旋) 
AVLTree D_LR(AVLTree A){
  A->Left=S_LR(A->Left);
  AVLTree B=S_RR(A);
  return B;
} 
//定义右左双旋(先右旋后左旋) 
AVLTree D_RL(AVLTree A){
  A->Right=S_RR(A->Right);
  AVLTree B=S_LR(A);
  return B;
}

AVLTree Insert(AVLTree T,int X){
  //树空的话直接建树
  if(!T){
    T=(AVLTree)malloc(sizeof(struct AVLNode));
    T->Data=X;
    T->Left=T->Right=NULL;
    T->Height=0; 
  }
  //插入到左子树
  else if(T->Data>X){
    T->Left=Insert(T->Left,X);
    //判断是否要平衡 
    if(getHeight(T->Left)-getHeight(T->Right)==2){
      // X插入到左树的左边,右单旋转 
      if(X<T->Left->Data){
        T = S_RR(T);
      }
      // X插入到左树的右边,左右双旋 
      else if(X>T->Left->Data){
        T=D_LR(T);
      }
    } 
  }
  //插入到右子树 
  else if(T->Data<X){
    T->Right=Insert(T->Right,X);
    if(getHeight(T->Right)-getHeight(T->Left)==2){
      // X插入到右树的右边,左单旋转 
      if(X>T->Right->Data){
        T = S_LR(T);
      }
      // X插入到右树的左边,右左双旋 
      else if(X<T->Right->Data){
        T=D_RL(T);
      }
    }
      
  }// else 没插入就不用旋转了
  //更新树的高度
  T->Height = getMaxHeight(T->Right,T->Left)+1;
  return T; 
}
int main(void){
  int n,temp;
  scanf("%d",&n);
  AVLTree T=NULL;
  for(int i=0;i<n;i++){
    scanf("%d",&temp);
    T = Insert(T,temp);
  }
  printf("%d",T->Data);
}

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: AVL树 二叉查找树 二叉树 平衡二叉查找树
最后更新:2022年12月9日

Titan

不为岁月流逝蹉跎,不为潮流的势头去附和

点赞
< 上一篇
下一篇 >

文章评论

  • Haha

    怪厉害的 :cool:

    2020年6月5日
    登录以回复
  • Haha

    第一耶

    2020年6月5日
    登录以回复
  • Haha

    建议作者充分利用一下右边空白,而不是制造很长的页面,
    毕竟滑起来怪费事的。 :eek: :eek:

    2020年6月5日
    登录以回复
    • Titan

      @Haha 这个是适应不同分辨率的响应式布局,在min-width小于767px的时候container是充满页面的。

      2020年6月13日
      登录以回复
  • 您需要 登录 之后才可以评论
    最新 热点 随机
    最新 热点 随机
    Docker配置IPv6容器网络支持 什么是Elastic Stack,ELK的发展历程 K8s中Pod的基本概念 Pushkin AI - 基于OpenAI-ChatGPT / GPT3的问答机器人 云原生 - 浅谈容器基础与K8S架构设计 腾讯Serverless体验,使用TypeScript编写并部署云函数
    Docker配置IPv6容器网络支持
    Spring与Mybatis的整合 [PHP] Laravel框架介绍、安装及配置 Python爬虫获取豆瓣TOP250电影详情 [数据结构] 平衡二叉查找树 (AVL树) Java核心技术之动态代理 Spring Cloud 微服务学习笔记 - IDEA工程搭建
    分类
    • Android
    • C语言
    • Elasticsearch
    • Hadoop
    • Hive
    • Java
    • JavaWeb
    • Kubernetes
    • Linux运维之道
    • Mybatis学习笔记
    • Python
    • SpringCloud
    • Web
    • Web前端
    • Web后端
    • 云原生
    • 并发编程
    • 开发工具
    • 数据库
    • 数据结构
    • 杂谈
    • 移动开发
    • 移动测试
    • 诗词歌赋
    • 软件测试
    • 逸笔挥墨
    • 随摘
    标签聚合
    二叉树 链式存储 Python 数据结构 Apache-Hive Mybatis学习笔记 JavaWeb Java

    COPYRIGHT © 2013-2021 Titan. ALL RIGHTS RESERVED.

    Theme Kratos Made By Seaton Jiang

    豫ICP备20001822号-1

    豫公网安备 41010502004418号