AVL树旋转机制详解

什么是AVL树？

AVL树是一种自平衡二叉查找树，它通过在插入和删除节点时进行特定的旋转操作来保持树的高度尽可能小，从而保证了树中每个节点的最大深度差不超过1。

基本概念

节点定义

AVL树中的每一个节点都包含一个关键字、左右子节点指针以及平衡因子。平衡因子表示左子树和右子树高度的差异值。

class Node {
    int key;
    Node left, right;
    int height;  // 平衡因子
}

高度计算

对于任意一个节点，其高度定义为该节点下最大子树的高度加一。叶子节点高度为0。

旋转操作

AVL树主要通过四种基本的旋转操作来保持平衡：

1. 左旋（Left Rotation）
2. 右旋（Right Rotation）
3. 左右旋（Left-Right Rotation，即先右旋再左旋）
4. 右左旋（Right-Left Rotation，即先左旋再右旋）

左旋

左旋主要用于解决节点插入或删除导致的不平衡情况。假设节点A的右子树高度比其左子树高2及以上，则进行左旋操作。

    A             B
   / \           / \
  B   D     ->  C   A
 / \       =>  / \
C   E        D   E

右旋

右旋用于解决节点插入或删除导致的不平衡情况。假设节点A的左子树高度比其右子树高2及以上，则进行右旋操作。

    B             A
   / \           / \
  A   D     ->  C   B
 / \               / \
C   E             D   E

左右旋

左右旋即先对节点A的右子树中的节点B进行右旋，再对整个节点A进行左旋。

    A             F
   / \           / \
  B   D     ->  C   G
 / \       =>  / \   / \
C   E        B   D E   H
      \       /
       H     F

右左旋

右左旋即先对节点A的左子树中的节点B进行左旋，再对整个节点A进行右旋。

    B             G
   / \           / \
  A   D     ->  C   H
 / \       =>  / \   / \
C   E        F   G D   E
      \       /
       F     B

平衡因子更新

每次进行旋转操作后，需要更新所有受影响节点的平衡因子。根据左右子树的高度差来判断平衡因子。

• 若左子树高度减去右子树高度的结果为1，则平衡因子为1。
• 若左子树高度减去右子树高度的结果为0，则平衡因子为0。
• 若左子树高度减去右子树高度的结果为-1，则平衡因子为-1。

总结

AVL树通过巧妙的旋转机制来保持二叉查找树的高度最小化，从而保证了查询、插入和删除操作的高效性。理解这些基本概念及操作对于深入掌握数据结构和算法有着重要意义。