AVL旋转

AVL树是一种自平衡二叉查找树，它的特点是任何节点的两个子树的高度差最多为1。当插入或删除节点时，可能会破坏这种平衡，因此需要通过旋转操作来恢复平衡。AVL旋转分为左旋和右旋两种：左旋是逆时针旋转45度，右旋是顺时针旋转45度。左旋主要用于处理右子树高度大于左子树的情况，而右旋主要用于处理左子树高度大于右子树的情况。在旋转过程中，会交换一些节点的位置，但不会改变树的结构。通过不断进行旋转操作，AVL树能够保持平衡，从而使得查找、插入和删除操作的时间复杂度都为O(log n)。