跳到主要内容

插入删除与再平衡

插入后如何恢复平衡？​

  • 步骤: 先按二叉搜索树插入, 再沿插入路径自底向上回溯, 对遇到的第一个失衡节点旋转;
  • 只需一次: 插入只会让路径上出现第一个需要修复的节点, 修好它整棵树即恢复平衡;
const rebalance = (node) => {
  if (balanceFactor(node) > 1) {
    if (balanceFactor(node.left) < 0) node.left = leftRotate(node.left);
    return rightRotate(node);
  }
  if (balanceFactor(node) < -1) {
    if (balanceFactor(node.right) > 0) node.right = rightRotate(node.right);
    return leftRotate(node);
  }
  return node;
};

const insert = (node, value) => {
  if (node == null) return new AVLNode(value);
  if (value < node.val) node.left = insert(node.left, value);
  else if (value > node.val) node.right = insert(node.right, value);
  else return node;
  return rebalance(node);
};

删除后为什么要一路再平衡？​

  • 差异: 删除可能让多个祖先依次失衡, 修好一个可能让上层继续失衡;
  • 做法: 删完节点后沿整条路径自底向上, 对每个节点调用 rebalance;
  • 返回: 删除同样返回新的子树根, 由父节点重新挂接;
const remove = (node, value) => {
  if (node == null) return null;
  if (value < node.val) node.left = remove(node.left, value);
  else if (value > node.val) node.right = remove(node.right, value);
  else {
    if (node.left == null || node.right == null) {
      return rebalance(node.left != null ? node.left : node.right);
    }
    let min = node.right;
    while (min.left != null) min = min.left;
    node.val = min.val;
    node.right = remove(node.right, min.val);
  }
  return rebalance(node);
};

查找操作需要额外处理吗？​

  • 不需要: AVL 树的查找与普通二叉搜索树完全一致, 平衡性只影响树高;
  • 复杂度: 树高为 O(log n), 因此查找、插入、删除都是 O(log n);