AVL树-自平衡的二叉搜索树

本文图片来源:手把手教,手写AVL树 - 不止是编程 - 博客园

AVL树的概念

自平衡

当二叉搜索树处于平衡状态的时候,其操作时间复杂度为O(logN),但当二叉搜索树是单支树的时候,其搜索效率则为O(N)。可见,二叉搜索树的平衡性是影响其操作效率的关键。
由此出发,学者们设计了第一个平衡二叉搜索树,即AVL树。AVL树作为第一个平衡的二叉搜索树,其影响非常深远,后来的很多平衡结构都借鉴了AVL树的设计思想。

AVL树的定义

一棵AVL树或者是空树,或者是具有下列性质的二叉搜索树:

  • 它的左子树和右子树都是AVL树。
  • 左子树和右子树的高度之差的绝对值不超过1

要注意,AVL的平衡性是一种相对的平衡,并非一种绝对的平衡。它不要求左子树和右子树的高度绝对相等,而仅仅是左子树和右子树的高度之差的绝对值不超过1即可。因为绝对的平衡难以实现。

如果给AVL树中的每一个节点都附加一个数字,该数字指示该节点右子树的高度减去左子树的高度所得的高度差,那么这个数字即为该节点的平衡因子。根据AVL树的定义,任一节点的平衡因子只能取-1、0或1。

AVL树的旋转

在一个平衡的二叉搜索树中插入一个新节点,就会造成其失衡,需要从插入位置沿通向根的路径回溯,检查各节点的平衡因子,在某一节点发现高度不平衡,则停止回溯。然后从发生不平衡的节点起,往下取三层,可以归纳为四种情况:

  1. 向某节点的左子树中插入一个左孩子。
  2. 向某节点的右子树中插入一个右孩子。
  3. 向某节点的左子树中插入一个右孩子。
  4. 向某节点的右子树中插入一个左孩子。

对应的处理方式:

单旋

  1. 右旋操作

以中间节点为轴,进行顺时针旋转,该中间节点的原父节点将变成该节点的右子节点,该中间节点的右子树则变成其原父节点的左子树。

基本情况

复杂情况
  1. 左旋操作

对应的,左旋的方法是以三个呈直线排列的节点的中间节点为轴,进行逆时针旋转。该中间节点的原父节点将变成该节点的左子节点,该中间节点的左子树则变成其原父节点的右子树

双旋

  1. 先左后右双旋转

以3个成折线排列的节点中的末节点为轴,进行逆时针旋转。使末节点代替中间节点的位置,也就是让末节点成为原中间节点的父节点,这时,三个节点将成一直线排列,再以新的中间节点为旋转轴做右旋操作,即可完成平衡化操作。

基本情况

复杂情况
  1. 先右后左双旋转

以3个成折线排列的节点中的中间节点为轴,进行顺时针旋转。使末节点代替中间节点的位置,也就是让末节点成为原中间节点的父节点,这时,三个节点将成一直线排列,再以新的中间节点为旋转轴做左旋操作,即可完成平衡化操作。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/avl%e6%a0%91-%e8%87%aa%e5%b9%b3%e8%a1%a1%e7%9a%84%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91/