admin管理员组文章数量:1576997
基本概念
avl树也是一颗二叉搜索数,所以也遵循二叉搜索树的定义,根节点的左子树永远比节点小,右子树永远比节点大。
- 树深
根节点的最大的层次
- 平衡因子
某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子(BF,Balance Factor)。
平衡二叉树上所有结点的平衡因子只可能是 -1,0 或 1。否则这棵树就是不平衡的。
- 旋转
节点的平衡因子大于1或者小于-1的时候就要对节点进行旋转。旋转分为四种
左单旋,右单旋,左右双旋,右左双旋
- 左单旋
因为右支更重,所以进行左单旋。
旋转方法是那右孩子的左补自己的右,自己补孩子的左。
/**
* 右重,左单旋
*/
private AvlNode<T> leftRotate(AvlNode<T> node){
//新节点树,就是之前的右孩子节点
AvlNode<T> newNode = node.rightChild;
//拿右孩子左补自己的右
node.rightChild = newNode.leftChild;
//拿自己补孩子的左
newNode.leftChild = node;
//更新节点平衡因子
updateBalanceFactor(node);
updateBalanceFactor(newNode);
//返回旋转后的节点
return newNode;
}
- 右单旋
因为左支更重,所以进行右单旋。
旋转方法是拿左孩子的右补自己的左,然后自己补左孩子的右。
/**
* 左重,右单旋
* @param node
* @return
*/
private AvlNode<T> rightRotate(AvlNode<T> node){
//新节点树,之前的左节点
AvlNode<T> newNode = node.leftChild;
//拿左孩子的右孩子补自己的左节点
node.leftChild = newNode.rightChild;
//拿自己补孩子的右节点
newNode.rightChild = node;
updateBalanceFactor(node);
updateBalanceFactor(newNode);
return newNode;
}
- 左右双旋
左右双旋的诀窍就在于把节点变成可以单旋的形式。所以要经过两次旋转,第一次左孩子左单旋,把节点变成左支过重的情况,现在就可以旋转根节点了,右单旋根节点就可以使节点平衡了。
private AvlNode<T> leftRightRotate(AvlNode<T> node){
node.leftChild = leftRotate(node.leftChild);
return rightRotate(node);
}
- 右左双旋
右左双旋跟左右双旋的情况相反,右孩子右单旋,然后自己左单旋。
/**
* 右重,右左双旋,先孩子右,后自己左
* @param node
* @return
*/
private AvlNode<T> rightLeftRotate(AvlNode<T> node){
//孩子右旋,自己左旋
node.rightChild = rightRotate(node.rightChild);
return leftRotate(node);
}
版权声明:本文标题:avl树的基本概念与节点旋转 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1727798152a1130506.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论