二叉搜索树的平衡--AVL树和树的旋转(图解) (2)

设A的右子结点为right,right的左子结点为grandchild。要执行RL旋转,将right结点的左子结点指向grandchild的右子结点,将grandchild的右子结点指向right,将A的右子结点指向grandchild的左子结点,将grandchild的左子结点指向A,最后将原来指向A的指针指向grandchild。

执行RL旋转以后,调整结点的平衡因子取决于旋转前grandchild结点的原平衡因子。这里也有三种情况需要考虑:

如果grandchild的原始平衡因子值为+1,将A的平衡因子更新为0,right的更新为-1;

如果grandchild的原始平衡因子值为  0,将A和right的平衡因子都更新为0;

如果grandchild的原始平衡因子值为-1,将A的平衡因子更新为+1,right的更新为0;

在所有情况中,都将grandchild的新平衡因子设置为0。所有其他结点的平衡因子不发生改变。

二叉搜索树的平衡--AVL树和树的旋转(图解)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpgyxp.html