AVL树-自平衡的二叉搜索树

彭晨涛 • 2019年11月25日 18:05 • 算法 • 阅读 40

AVL树的概念

自平衡

当二叉搜索树处于平衡状态的时候，其操作时间复杂度为O(logN)，但当二叉搜索树是单支树的时候，其搜索效率则为O(N)。可见，二叉搜索树的平衡性是影响其操作效率的关键。
由此出发，学者们设计了第一个平衡二叉搜索树，即AVL树。AVL树作为第一个平衡的二叉搜索树，其影响非常深远，后来的很多平衡结构都借鉴了AVL树的设计思想。

AVL树的定义

一棵AVL树或者是空树，或者是具有下列性质的二叉搜索树：

它的左子树和右子树都是AVL树。
左子树和右子树的高度之差的绝对值不超过1。

要注意，AVL的平衡性是一种相对的平衡，并非一种绝对的平衡。它不要求左子树和右子树的高度绝对相等，而仅仅是左子树和右子树的高度之差的绝对值不超过1即可。因为绝对的平衡难以实现。

如果给AVL树中的每一个节点都附加一个数字，该数字指示该节点右子树的高度减去左子树的高度所得的高度差，那么这个数字即为该节点的平衡因子。根据AVL树的定义，任一节点的平衡因子只能取-1、0或1。

AVL树的旋转

在一个平衡的二叉搜索树中插入一个新节点，就会造成其失衡，需要从插入位置沿通向根的路径回溯，检查各节点的平衡因子，在某一节点发现高度不平衡，则停止回溯。然后从发生不平衡的节点起，往下取三层，可以归纳为四种情况：

向某节点的左子树中插入一个左孩子。
向某节点的右子树中插入一个右孩子。
向某节点的左子树中插入一个右孩子。
向某节点的右子树中插入一个左孩子。

对应的处理方式：

单旋

右旋操作

以中间节点为轴，进行顺时针旋转，该中间节点的原父节点将变成该节点的右子节点，该中间节点的右子树则变成其原父节点的左子树。

左旋操作

对应的，左旋的方法是以三个呈直线排列的节点的中间节点为轴，进行逆时针旋转。该中间节点的原父节点将变成该节点的左子节点，该中间节点的左子树则变成其原父节点的右子树

双旋

先左后右双旋转

以3个成折线排列的节点中的末节点为轴，进行逆时针旋转。使末节点代替中间节点的位置，也就是让末节点成为原中间节点的父节点，这时，三个节点将成一直线排列，再以新的中间节点为旋转轴做右旋操作，即可完成平衡化操作。

先右后左双旋转

以3个成折线排列的节点中的中间节点为轴，进行顺时针旋转。使末节点代替中间节点的位置，也就是让末节点成为原中间节点的父节点，这时，三个节点将成一直线排列，再以新的中间节点为旋转轴做左旋操作，即可完成平衡化操作。

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/avl%e6%a0%91-%e8%87%aa%e5%b9%b3%e8%a1%a1%e7%9a%84%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91/

AVL树-自平衡的二叉搜索树

AVL树的概念

自平衡

AVL树的定义

AVL树的旋转

单旋

双旋

相关推荐

发表回复