两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。

AVL树即是高度平衡的二叉搜索树。

②左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

③如果一棵二叉搜索树是高度平衡的它就是AVL树。

如果它有n个结点其高度可保持在log_2N,搜索的时间复杂度是log_2N。

AVL树的定义中①拥有键值对。

②多加一个双亲节点用于调整平衡二叉树。

③增加平衡因子用于判断插入或删除后是否还是一棵AVL树。

templateclass

AVL树的插入分成两步第一步是按照二叉搜索树的方式来新增节点。

第二步是是调整节点使其成为一棵平衡的二叉搜索树。

1.首先按照二叉搜索树的方式来新增节点但这需要新增一个双亲指针方便后续在调节节点。

因此在新增节点的最后部分的代码中我们需要让cur-_parent指向双亲节点parent。

①当平衡因子_bf等于0的时候说明parent节点一边高一边矮新增的这个节点填上了矮的地方这种情况就不需要更新了直接beak掉。

②当平衡因子_bf等于1或者-1的时候说明parent原本的平衡因子是0parent两边一样高新增了节点之后有一边变高了。

这种情况需要继续往上走。

③当平衡因子_bf等于2或-2的时候说明之前parent-_bf

-1现在插入严重不平衡违反规则此时需要原地旋转即以当前节点为轴旋转。

随后将重点分析当平衡因子是2或-2的时候说明需要通过旋转调节节点。

那该如何去旋转呢

bool

false;}}//找到插入的位置后即确认了是在左子树还是右子树cur

new

parent;}//更新平衡因子判断插入后的树是否是一棵AVL树while

(cur

parent-_left){parent-_bf--;//一般是右-左因此如果是插入在左边那就是减一}else

//是右孩子{parent-_bf;}//更新完平衡因子后判断是否是一棵AVL树//如果平衡因子是0任何节点的平衡因子都没被改变if

(parent-_bf

-1){//如果平衡因子是1或-1那么就说明父节点往上的节点的平衡因子有可能被改变了cur

parent;parent

//先左旋后右旋{RotateLR(parent);}else

(parent-_bf

//先右旋再左旋{RotateRL(parent);}}else

//不排除在创建一棵AVL树的时候代码写错了{assert(false);}}return

true;}

⭐让这颗子树的高度跟插入前保持一致。

因为这样就不会对上层的平衡因子造成影响此时就可以结束对这棵树的更新旋转。

这种情况是新增的节点位于比较高的左子树的左侧的某个位置上此时在往上检查平衡因子发现值为60的节点是平衡因子为-2说明左子树的高度是比右子树高的这里选择右减左所以当我们的判断条件if(parent-_bf-2

cur-_bf

-1)成立时就表示着符合当前情况。

所以我们需要将60的节点的平衡因子减小那就是将它按下去以60的节点为轴旋转

⭐旋转的动作因为b是30节点的右孩子根据二叉搜索树的性质b子树所有的值肯定是大于30小于60的而且60节点需要下来说明60节点是要成为30节点的右孩子的因此b子树就需要成为60节点的左孩子了。

⭐当然我们需先判断一下30节点的右孩子是否为空即30节点没有右孩子。

如果没有右孩子那么就不能让它指向60节点的左孩子。

⭐然而我们旋转的这颗树可能是一颗子树因此需要判断一下60节点的双亲节点是否为空如果为空说明它不是子树此时就可以让_root指向subL成为新的根然后subL的双亲节点置为nullptr因为subL-parent原本是指向60节点的。

⭐如果不为空那就说明它是一棵子树那么就让60节点的双亲节点的左或右孩子点指向30节点30节点的双亲指向60原先的双亲节点。

void

parent){//一开始例子中的60节点便是parent//先创建指向30节点的指针和指向b节点的指针Node*

subL

subL-_right;//这一步是让60节点的左孩子指向b节点parent-_left

subLR;//这一步判断b节点是否为空,如果不为空那么就让它的双亲节点指向60节点本来是指向subL的if

parent;}//上面两步成功将b节点改链接到60节点上去//先保存60节点的双亲节点Node*

ppNode

parent-_parent;//让30节点subL的右孩子指向60节点即60节点链接到了30节点subL的右孩子上subL-_right

parent;//60节点的双亲节点指向30节点subLparent-_parent

(ppNode

//如果parent是原先的双亲节点的左孩子{ppNode-_left

subL;

//如果parent是原先的双亲节点的右孩子{ppNode-_right

subL;}//链接后再让成为新根后的30节点subL的双亲节点指向ppNodesubL-_parent

ppNode;}//最后将30节点subL和60节点parent的平衡因子修改//subL-_bf

parent-_bf

0;//此时右单旋完成//因为旋转的要求是让这颗子树的高度跟插入前保持一致//那就说明此时完成旋转的这树不会对上层的平衡因子造成影响此时就可以结束对这棵树的更新旋转}

这种情况是新增的节点位于比较高的右子树的右侧的某个位置上此时在往上检查平衡因子发现值为30的节点是平衡因子为2说明右子树的高度是比左子树高的这里选择右减左所以当我们的判断条件if(parent-_bf2

cur-_bf

1)成立时就表示着符合当前情况。

所以我们需要将30的节点的平衡因子减小那就是将它按下去以30的节点为轴旋转

⭐旋转的动作因为b是60节点的左孩子根据二叉搜索树的性质b子树所有的值肯定是大于30小于60的而且30节点需要下来说明30节点是要成为60节点的左孩子孩子的因此b子树就需要成为30节点的右孩子了。

⭐同样的我们需先判断一下60节点的左孩子是否为空即60节点没有左孩子。

如果没有左孩子那么就不能让它指向30节点的右孩子。

⭐同样的需要盘点一下是否是一棵子树。

因此需要判断一下30节点的双亲节点是否为空如果为空说明它不是子树此时就可以让_root指向subR成为新的根然后subR的双亲节点置为nullptr因为subR-parent原本是指向30节点的。

⭐如果不为空那就说明它是一棵子树那么就让30节点的双亲节点的左或右孩子点指向60节点60节点的双亲指向30原先的双亲节点。

左单旋代码如下

parent){//创建60节点subR右右是左旋嘛Node*

subR

parent-_right;//创建指向b节点的指针subRLNode*

subRL

subR-_left;//先让parent的右孩子节点指向subRL。

parent-_right

subRL;//判断subRL是否为空不为空那就让subRL的父节点指向parentif

parent;}//上面步骤成功将b节点链接到了parent上//先把parent的父节点保存起来不管存在不存在Node*

ppNode

parent-_parent;//接下来就是把parent按下了成为subR的左孩子让subR成为新根subR-_left

subR;//让subR成为新根if

这种情况是新增的节点位于比较高的左子树的右侧的某个位置上此时在往上检查平衡因子发现值为parent节点的平衡因子为-2说明左子树的高度是比右子树高的这里选择右减左所以当我们的判断条件if(parent-_bf-2

cur-_bf

1)成立时就表示着符合当前情况。

这种情况采取的旋转方式是先左旋后右旋。

左旋的轴是subL节点右旋的轴就是parent节点。

此时我们复用左单旋和右单旋的情况即可。

但是需要注意的是尽管在右单旋和左单旋中已经对平衡因子进行了修改但我们通过画图可以看出来修改过的平衡因子并不符合实际上的值因此我们需要重新修改一遍。

代码如下

subLR-_bf;//记录调整节点之前subLR的平衡因子因为subLR最后是新根//开始调整RotateL(parent-_left);RotateR(parent);//修改平衡因子if

(bf

-1)//说明是在左子树上新增节点即图中的b子树{parent-_bf

1;subL-_bf

if(bf0)//说明subLR自己就是新增的节点{parent-_bf

0;subL-_bf

这种情况是新增的节点位于比较高的右子树的左侧的某个位置上此时在往上检查平衡因子发现值为parent节点的平衡因子为2说明右子树的高度是比左子树高的这里选择右减左所以当我们的判断条件if(parent-_bf2

cur-_bf

-1)成立时就表示着符合当前情况。

这种情况采取的旋转方式是先右旋后左旋。

右旋的轴是subR节点左旋的轴就是parent节点。

此时我们复用左单旋和右单旋的情况即可。

但是需要注意的是尽管在右单旋和左单旋中已经对平衡因子进行了修改但我们通过画图可以看出来修改过的平衡因子并不符合实际上的值因此我们需要重新修改一遍。

代码如下

subRL-_bf;//记录调整节点之前subRL的平衡因子因为subRL最后是新根RotateR(parent-_right);RotateL(parent);if

(bf

//说明subRL本身就是那个新增的节点{parent-_bf

0;subR-_bf

假如以pParent为根的子树不平衡即pParent的平衡因子为2或者-2分以下情况考虑

①pParent的平衡因子为2说明pParent的右子树高设pParent的右子树的根为pSubR。

②pParent的平衡因子为-2说明pParent的左子树高设pParent的左子树的根为pSubL

旋转完成后原pParent为根的子树个高度降低已经平衡不需要再向上更新。

验证AVL树

由于AVL树是在二叉搜索树的基础上加了平衡性后得到的树因此需要确认一棵树是AVL树那么就需要以下两步

1.先确定是否是一棵二叉搜索树如果中序遍历可得到一个有序的序列就说明为二叉搜索树。

2.验证其是否平衡①每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)。

②节点的平衡因子是否计算正确。

代码如下

Inorder(){_Inorder(_root);}void

_Inorder(Node*

nullptr)return;_Inorder(root-_left);cout

root-_kv.first

Height(root-_left);//然后计算右子树的高度int

1;}

Height(root-_right);//如果不同那就将当前节点的值打印出来并提升异常if

(rightHeight

false;}//通过递归验证每一个节点的平衡因子是否符合return

abs(rightHeight

AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即log_2

但是如果要对AVL树做一些结构修改的操作性能非常低下因为做修改就很大可能需要进行旋转每一次旋转都是比较消耗性能的