平衡二叉树AVL-双旋

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


下一篇:力扣hot100学习记录(十一)