AVL树

in 数据结构 with 4 comments

二叉排序树中查找操作的执行时间与树形有关系,最坏情况下执行时间为线性(即退化为链表),为了避免这种情况的发生,引入了平衡树的概念。

平衡的二叉树有很多种,其中较为著名的为AVL树,它得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis。

简单定义:

平衡因子:一个节点的平衡因子时该节点的左子树高度减去其右子树高度(或右减去左)。

平衡二叉树:一棵二叉树中每个节点的左右子树高度最多相差1,即该二叉树的每个节点的平衡因子均为1、0或-1。

特殊性:

一般来说,平衡二叉树总是二叉排序树,平衡二叉树是在二叉排序树的基础上增加了树形约束,即要求每个节点是平衡的。

插入删除:

平衡二叉树本质上是二叉排序树,插入和删除基本与二叉排序树一致,只是多了一个调整的步骤:

无论是对一棵平衡树进行插入或是删除操作,都会改变原有节点的平衡因子,有可能使平衡树失衡,因此需要进行必要调整,使其仍是一棵平衡树。

按旋转类型分类:

左旋:

以某一个节点为轴,它的右子枝逆时针旋转,作为新子树的根,称之为逆时针旋转(anticlockwise)或者左旋转。

右旋:

以某一个节点为轴,它的左子枝顺时针旋转,作为新子树的根,称之为顺时针旋转(clockwise)或者右旋转。

调整分为四类,以插入节点引起的失衡为例:

按调整类型分类:

LL型调整:

在节点1插入后,节点5平衡因子变为2(3-1),5-3-2构成LL型不平衡。

右旋转:将3的右子树调整为5的左子树,并将3调整为5的父节点

FPYfjSHRFN.gif

RR型调整:

在节点9插入后,节点5平衡因子变为-2(1-3),5-7-8构成RR型不平衡。

左旋转:将7的左子树调整为5的右子树,并将7调整为5的父节点

a8QkVjt7i5.gif

LR型调整:

在节点4插入后,节点8平衡因子变为2(4-2),8-3-6构成LR型不平衡。

先左旋后右旋:将6的左子树调整为3的右子树,将6的右子树调整为8的左子树,并将6调整为3、8的父节点

WSJrRyRoZB.gif

RL型调整:

在节点7插入后,节点3平衡因子变为-2(2-4),3-8-5构成RL型不平衡。

先右旋后左旋:将5的左子树调整为3的右子树,将5的右子树调整为8的左子树,并将5调整为3、8的父节点

f5i58g4U5W.gif

Responses
  1. study 一起学习 go

    Reply
  2. hello

    study 一起学习

    Reply
  3. hello

    study 一起学习

    Reply
  4. hello

    study 学习

    Reply