C++AVL树4种旋转详讲(左单旋、右单旋、左右双旋、右左双旋)

C++AVL树4种旋转详讲

什么是AVL树？

AVL树是一种自平衡二叉搜索树，它在插入或删除一个节点时，会通过旋转操作进行自平衡。AVL树的特点是保证树的高度始终保持在O(logN)的水平，从而保证了树的查询、插入、删除等操作时间复杂度保持在O(logN)的水平。因此在大规模数据的场景下，使用AVL树能够取得很好的性能表现。

AVL树的基本操作

AVL树的基本操作包含插入节点、删除节点以及查找节点三个操作。由于AVL树是一种自平衡树，因此对于插入与删除操作时，需要进行旋转操作来使树自平衡。

在 AVL 树的删除操作中，当一个节点被删除时，需要找到它的后序中继节点来继承该节点。然后，当对继承的节点进行重平衡时，如果无法确定其子节点的高度（或在重平衡期间降低其他节点的高度）则可能需要进行额外的旋转。

AVL树的4种旋转

左单旋转（left-rotation）

在 AVL 树的 左叶子节点过重 的情况下，需要进行左单旋转来使树保持平衡。左单旋转的基本操作是：将该节点旋转成其右节点的左儿 子，然后维护该节点以及其右节点之间的连接关系。

示例：

        A (-2)                                 B (0)
       /  \               左单旋转             /   \
     B (0)  C (1)         ------>           D     A (0)
    /  \                     A                /     / \
  D (0) E (0)                              E     F   C (1)
        \
       F (0)

右单旋转（right-rotation）

在 AVL 树的 右叶子节点过重 的情况下，需要进行右单旋转来使树保持平衡。右单旋转的基本操作是：将该节点旋转成其左节点的右儿 子，然后维护该节点以及其左节点之间的连接关系。

示例：

          A (2)                             B (0)
         /  \              右单旋转          /   \
       B (0) C (-1)       ------>         A (0)  D
      /  \                              / \    \
    D (0) E (0)                        F   C (-1) E
        /
      F (0)

左右双旋转（left-right-rotation）

在 AVL 树的 左孙子节点过重 的情况下，需要进行左右双旋转来使树保持平衡。左右双旋转的基本操作是：将该节点的右节点进行右单旋转，然 后再将该节点进行左单旋转。最后维护该节点的祖先节点的连接关系。

示例：

        A (-2)                                A (-2)                                C (0)
       /  \               左右双旋转            /  \               左旋转             /   \
     B (1)  C (0)         ------>          B(0)  C (2)          ------>         A (0)   B (0)
    / \    /  \                              /       \                          /  \      \
  D (0) E (1) F (0)                        D         F (1)                      D    E (0)  F (0)
         \                                   \
        G(0)                                 G (0)

右左双旋转（right-left-rotation）

在 AVL 树的 右孙子节点过重 的情况下，需要进行右左双旋转来使树保持平衡。右左双旋转的基本操作是：将该节点的左节点进行左单旋转，然 后再将该节点进行右单旋转。最后维护该节点的祖先节点的连接关系。

示例：

        A (2)                                A (2)                                  C (0)
       /  \               右左双旋转           /   \               右旋转             /   \
     B (-1) C (0)         ------>          B(-1) C (2)          ------>          A (0)   B (0)
    /     / \                                /     \                                   /   \
  D  (0) E  (1) F (0)                      D  (0)   E  (0)                            D     F (0)
         /                                      \
       G (0)                                     G (0)

总结

AVL树是一种高效的自平衡二叉搜索树，其基本操作包括插入、删除和检索操作。在插入和删除操作时，由于需要保证树的平衡，因此需要进行旋转操作。其中常用的四种旋转操作包括左单旋转、右单旋转、左右双旋转和右左双旋转。在实际使用中，根据情况选择不同的旋转方式可以提高性能表现。