AVL树及其搜索树

xiaoxiao2021-03-01  10

首先我们先明确两个关于二叉树的基本概念:深度(depth)和高度(height)。

深度:从根节点开始(其深度为1),自顶向下逐层累加;

高度:从叶节点开始(其高度为1),自底向上逐层累加。

虽然树的高度和深度一样,但具体到某个节点,其深度和高度不一样,如:

节点10的高度为2,深度为3;节点7的高度为1,深度为3.

言归正传:

AVL树:一个空二叉树是AVL树;一个非空二叉树T的左右子树TL和TR,若T为AVL树,则TL和TR也为AVL树,且TL和TR的高度差不超过1.

AVL搜索树(AVL search tree):只不过是一个拥有AVL特性的二叉搜索树,如

一个有n个节点的AVL树的高度是O(logn),这有助于评估基于AVL树的算法的复杂度。

下面着重谈一谈AVL搜索树的基本操作:

1)搜索(search):与普通二叉搜索树的操作一样,不过算法复杂度变为O(logn);

2)插入(insert):

平衡因子(balance factor)—— 一个节点左子树的高度减去右子树的高度就是该节点平衡因子,一棵AVL树中不存在平衡因子不是1、-1或0的节点。

寻找X:维持该树的平衡因子不变,从要插入的位置向根节点上溯,找到平衡因子首先为1或-1的祖先节点,记为X。

根据X进行判断是否需要重新平衡树:

a)若X不存在,也就是说从根节点(包括根节点)到要插入的位置的路径上的节点的平衡因子都为0,这是可以判断不需要重新平衡,只需要改变路径上节点的平衡因子即可。

b)X存在,但插入后其平衡因子变为0,也不需要进行平衡,只不过X的左右子树在插入后的高度变得相等罢了。

c)当X的平衡因子由1变为2或由-1变为-2时才需要进行平衡。

不平衡(imbalance)的类型分为LL、LR和RR、RL四种类型,并对应四种旋转以达到平衡。

I)LL旋转(rotation)

II)LR旋转

III)对于RR和RL旋转也是同样的道理,LL和RR的旋转属于单旋转(single rotations),LR和RL的旋转是双旋转(double rotations)。

3)删除(delete):

维持原始平衡因子不变,如果从要删除的节点到根节点路径上的节点的平衡因子都为0,则不需要进行平衡旋转。当删除节点后调整平衡因子,从删除位置向根节点上溯,找到平衡因子首先变为2或-2的节点记为X,我们以它为根节点进行旋转。

I)R1旋转

为什么叫R1旋转?我们首先找到特殊节点X为节点15,由于删除的节点位于15的右子树,所以为R,1是因为删除前15节点左子树的根节点13的平衡因子为1,同理如果平衡因子为0,则为R0旋转,为-1,则为R-1旋转。这里的R1旋转跟上面插入用的LL旋转一模一样:

节点13顶替15的位置,13的右子树作为15的左子树,节点15接在13的右子树上。

II)R0旋转

R0旋转和LL旋转的不同在于B和X的平衡因子。

总结:其实一切都是围绕平衡因子来的,我们通过平衡因子判断是否平衡,并确定旋转区域的根节点(如上面的节点15和节点X),也是根据平衡因子我们制定旋转策略,其在算法实现上,只是根据平衡因子进行局部子树的重组,算法复杂度不论查找、插入还是删除,都为O(logn)。

转载请注明原文地址: https://www.6miu.com/read-4050048.html

最新回复(0)