day8 AVL树

2019-05-27 本文已影响0人 coder_feng

AVL树是最早发明的平衡二叉搜索树之一，名字来源于两位发明者的名字G.M.Adelson-Velsky 和 E.M.Landis(来自苏联的科学家)

AVL树的一些相关知识点

AVL树里面有一个平衡因子的Balance Factor的概念：代表这某节点的左右子树的高度差，而且每个节点的平衡因子只有在1，0，-1（绝对值小于等于1）的情况下，树才不会失衡，否则就会失衡，那这个就意味这每个节点的左右子树的高度差不超过1；下面给出两张图，分别观察一下失衡和平衡的情况:

失衡的二叉树

平衡二叉树

前面已经说到出现平衡二叉树是为了提高算法效率哈，因为前面可以知道节点的插入和高度是有一定关系的，插入节点的时候需要遍历整颗树，高度越小，自然就会越快！下面来说说有可能导致失衡的原因

添加导致的失衡

添加失衡

注意：添加导致的失衡会导致所有祖先节点都失衡，父节点是，非祖先节点都不可能失衡

你说如果我们可以将这个失去平衡的树重新平衡一下，那都好呀，答案是肯定可以的，恢复平衡之后将变成如下图：

恢复平衡图

删除导致的失衡

父节点失衡

祖先节点失衡

注意：删除元素会导致父节点或祖先节点失衡（只有一个节点会失衡）其他节点都不可能失衡

在学习怎么恢复平衡的过程之后，我们需要了解到几个概念，分别是LL(右旋转)，RR(左旋转)，LR(RR左旋转，LL右旋转),RL(LL右旋转，RR左旋转)

添加元素的旋转-恢复平衡

LL - 右旋转（单旋）

g.left = p.right;

p.right = g;

让p成为这颗子树的跟节点

仍然是一颗二叉搜索树：T0 < n < T1<p<T2<g<T3

更改T2,p,g的parent属性，并先后更新根g,p高度

之所以成为LL，是因为是在p的left（n）的left添加的元素，经过右旋转之后发现树恢复了平衡；

代码图如下：

方法中涉及到的高度方法图会在后面给出来

RR - 左旋转（单旋）

g.right = p.left;

p.left = g;

让p成为这颗子树的跟节点

仍然是一棵二叉搜索树：T0<g<T1<p<T2<n<T3

T1,p,g的parent属性重新设置，还有g,p的高度设置

代码图如下：

左旋转代码图

LR - RR左旋转，LL右旋转（双旋转）

RL-LL右旋转，RR左旋转（双旋转）

双旋要不就是先左后右，要不然就是先右后左，所以代码实现就是将上面两个方法合起来用就可以啦，下面我们再看看一个恢复平衡的方法

恢复平衡代码

rebalance2

添加之后的修复

afterAdd

删除元素的旋转-恢复平衡

LL-右旋转（单旋）

RR-左旋转（单旋）

LR-RR左旋转，LL右旋转（双旋）

RL-LL右旋转，RR左旋转（双旋）

旋转的处理方式和添加元素的步骤相差不多，不同的就是失衡的情况，删除节点的一次恢复平衡操作有可能会导致祖先节点失衡，需要再次恢复平衡，然后又可能导致更高层的祖先节点失衡，也是因为这个原因，所以在处理AVL删除元素的代码方法里面，调用了恢复平衡之后不能马上调用break，这个和AVL添加元素方法稍微有点不一样（图中的绿色代表就是如果绿色节点不存在的情况下，会导致很多祖先节点有可能失衡，极端情况下，所有祖先节点都需要进行恢复平衡的操作，共O(logn)次调整）

下面展现元素移除之后的的平衡修复代码：