AVL Tree

定义

AVL树（以发明者Adelson-Velsky和Landis的名字命名）是一种自平衡二叉搜索树。在AVL树中，任何节点的两个子树高度差最多为一；如果在任何时候高度差超过一，就会进行重新平衡以恢复这一特性。查找、插入和删除操作在平均情况和最坏情况下的时间复杂度都是O(log n)，其中n是操作前树中节点的数量。插入和删除可能需要通过一次或多次树旋转来重新平衡树。

AVL Tree 为了维护节点平衡性，需要进行4种旋转操作

1.由于该节点左孩子的左子树增加导致的不平衡，需要进行一次右旋转（rightRotate）

T1, T2, T3 and T4 are subtrees.
         z                                      y
        / \                                   /   \
       y   T4       Right Rotate (z)         x      z
      / \          - - - - - - - - ->      /  \    /  \
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

function rightRotate(z: TreeNode) {
  const y = z.left;
  const T3 = y.right;
  y.right = z;
  z.left = T3;
  return y;
}

Common function for rightRotate

      node                                   temp
      / \                                   /   \
    temp  T4     Right Rotate (node)      x      node
    / \          - - - - - - - - ->      /  \    /  \
    x   T3                               T1  T2  T3  T4
  / \
T1   T2

function rightRotate(node: TreeNode) {
  const temp = node.left;
  node.left = temp.right;
  temp.right = node;
  return temp;
}

2.由于该节点右孩子的右子树增加导致的不平衡，需要进行一次左旋转（leftRotate）

  z                                y
 /  \                            /   \
T1   y      Left Rotate(z)      z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

function leftRotate(z: TreeNode) {
  const y = z.right;
  const T2 = y.left;
  y.left = z;
  z.right = T2;
  return y;
}

Common function for leftRotate

 node                             temp
 /  \                            /   \
T1  temp   Left Rotate(node)  node     x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

function leftRotate(node: TreeNode) {
  const temp = node.right;
  node.right = temp.left;
  temp.left = node;
  return temp;
}

3.由于该节点左孩子的右子树增加导致的不平衡，需要进行一次左旋和一次右旋（LR）

     z (node)                        z                           x
    / \                            /   \                        /  \
   y   T4   Left Rotate (y)       x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

function LR(node: TreeNode) {
  node.left = leftRotate(node.left);
  return rightRotate(node);
}

4.由于该节点右孩子的左子树增加导致的不平衡，需要进行一次右旋和一次左旋（RL）

   z (node)                     z                            x
  / \                          / \                          /  \
T1   y   Right Rotate (y)    T1   x     Left Rotate(z)    z      y
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

function RL(node: TreeNode) {
  node.right = rightRotate(node.right);
  return leftRotate(node);
}

定义

AVL Tree 为了维护节点平衡性，需要进行4种旋转操作

Read Next

Binary Search Tree

Red-Black Tree