河南建设厅二建公示网站首页,网页与网站的关系,甘肃省住房城乡建设厅网站,极速在线网站目录 一、AVL树的定义二、AVL树的作用三、AVL树的插入操作插入——平衡因子的更新插入——左单旋插入——右单旋插入——左右双旋插入——右左双旋 四、ALVL树的验证五、AVL树的性能 一、AVL树的定义
AVL树#xff0c;全称 平衡二叉搜索#xff08;排序#xff09;树。
二… 目录 一、AVL树的定义二、AVL树的作用三、AVL树的插入操作插入——平衡因子的更新插入——左单旋插入——右单旋插入——左右双旋插入——右左双旋 四、ALVL树的验证五、AVL树的性能 一、AVL树的定义
AVL树全称 平衡二叉搜索排序树。
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
平衡因子Balance Factor简写为bf 平衡因子bf结点的左子树的深度减去右子树的深度。也可以是右子树的深度减去左子树的深度。看个人实现而异。
即 结点的平衡因子 左子树的高度 - 右子树的高度。 或者 节点的平衡因子 右子树的高度 - 左子树的高度。
AVL树本质上是一颗二叉查找树但是它又具有以下特点
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 这就是一颗AVL树 二、AVL树的作用 有一颗二叉树他有n个节点如果他是一颗二叉搜索树他形状多样可能会形成单枝树高度为n,那么在这颗搜索树中查找元素的最坏时间复杂度为O(n),最好时间复杂度是O( l o g 2 n log_2 n log2n)。 如果他是一颗AVL树他的高度稳定为 l o g 2 n log_2 n log2n,查找元素的时间复杂度为O( l o g 2 n log_2 n log2n)。 由上图可知同样的结点由于插入方式不同导致树的高度也有所不同。特别是在带插入结点个数很多且正序的情况下会导致二叉树的高度是O(N)而AVL树就不会出现这种情况树的高度始终是O(lgN).高度越小对树的一些基本操作的时间复杂度就会越小。这也就是我们引入AVL树的原因。 三、AVL树的插入操作
插入——平衡因子的更新 在插入一个元素的时候必然会引起平衡因子的变化所以我们需要在插入的时候把平衡因子同时更新在平衡因子大于1或者小于-1时我们则需要进行旋转操作进行调整使平衡因子再次正常从而保证这颗二叉树一直是一颗AVL树。 使用平衡因子计算 右子树高度 - 左子树高度 情况一 在插入元素后需要更新父节点的平衡因子在父节点的左子树插入元素父节点的平衡因子-1在父节点的左子树插入元素父节点的平衡因子1如果父节点的平衡因子更新过后变为1或者-1则需继续往上更新至根节点因为1或者-1表示该节点的高度发生改变需往上更新。 情况2 在插入元素后需要更新父节点的平衡因子在父节点的左子树插入元素父节点的平衡因子-1在父节点的左子树插入元素父节点的平衡因子1如果父节点的平衡因子更新过后变为0则不需要继续向上更新因为变为0只能说明该树高度没有变化只是相对于原来变得平衡。 如果在更新平衡因子后平衡因子不在(-1/0/1)范围时则需旋转操作下面讲解如何进行旋转操作 由于插入需要旋转的情况较多大致可以分为四大类
插入——左单旋
动图演示 情况一 右子树高时在右子树的右侧插入元素此时需要左单旋 插入——右单旋
动图演示 情况二、 左子树较高时在左子树的左侧插入元素此时需要右单旋 插入——左右双旋 情况三、左子树较高时在左子树的右侧插入元素此时需要左右双旋即先对30进行左单旋然后再对90进行右单旋 插入——右左双旋 情况四、右子树较高时在右子树的左侧插入元素此时需要右左双旋即先对90进行右单旋然后再对30进行左单旋 四、ALVL树的验证
int _Height(Node* root)
{//用来计算二叉树的高度if (root NULL)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;
}bool _IsBalance(Node* root)
{if (root NULL)return true;int leftH _Height(root-_left);int rightH _Height(root-_right);//检查平衡因子if (rightH - leftH ! root-_bf){cout root-_kv.first 节点平衡因子异常 endl;return false;}//通过计算左右子树的高度差判断这颗二叉树是否为AVL树return abs(leftH - rightH) 2 _IsBalance(root-_left) _IsBalance(root-_right);//检查高度差要检查二叉树中所有节点的左右子树的高度差
}bool IsBalance()
{return _IsBalance(_root);
}五、AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即 l o g 2 n log_2 n log2n 。
但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
