- LR型失衡
定义:当在某个节点的左孩子的右子树上插入或删除一个节点后,如果这个右子树仍然有其他非空节点存在,导致该节点的左子树的高度比右子树高2,则发生LR型失衡。
调整方法:需要先进行RR旋转(围绕左孩子的右孩子),然后再进行LL旋转(围绕原节点)。这两次旋转使树重新获得平衡。
if (balance < -1 && value < node.right.value) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
- RL型失衡
定义:当在某个节点的右孩子的左子树上插入或删除一个节点后,如果这个左子树仍然有其他非空节点存在,导致该节点的右子树的高度比左子树高2,则发生RL型失衡。
调整方法:**需要先进行LL旋转(围绕右孩子的左孩子),然后再进行RR旋转(围绕原节点)。**这两次旋转使树重新获得平衡。
if (balance > 1 && value > node.left.value) {
node.left = leftRotate(node.left);
return rightRotate(node);
}