js实现平衡二叉树

平衡二叉树的概念

平衡二叉树（AVL树）是一种自平衡二叉搜索树，确保任何节点的左右子树高度差不超过1。通过旋转操作（左旋、右旋、左右旋、右左旋）维持平衡，保证查找、插入、删除操作的时间复杂度为O(log n)。

节点结构定义

使用JavaScript类定义AVL树的节点，包含值、左子树、右子树和高度属性：

class AVLNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

计算节点高度

通过递归获取子树高度，用于平衡因子计算：

function getHeight(node) {
  return node ? node.height : 0;
}

计算平衡因子

平衡因子为左子树高度减去右子树高度，绝对值超过1时需旋转：

function getBalanceFactor(node) {
  return getHeight(node.left) - getHeight(node.right);
}

更新节点高度

插入或删除后更新节点高度，基于子树高度：

function updateHeight(node) {
  node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}

旋转操作

右旋（LL型不平衡）
当左子树高度较高且左子树的左子树导致不平衡：

function rightRotate(y) {
  const x = y.left;
  const T2 = x.right;
  x.right = y;
  y.left = T2;
  updateHeight(y);
  updateHeight(x);
  return x;
}

左旋（RR型不平衡）
当右子树高度较高且右子树的右子树导致不平衡：

function leftRotate(x) {
  const y = x.right;
  const T2 = y.left;
  y.left = x;
  x.right = T2;
  updateHeight(x);
  updateHeight(y);
  return y;
}

左右旋（LR型不平衡）
先对左子树左旋，再对当前节点右旋：

function leftRightRotate(node) {
  node.left = leftRotate(node.left);
  return rightRotate(node);
}

右左旋（RL型不平衡）
先对右子树右旋，再对当前节点左旋：

function rightLeftRotate(node) {
  node.right = rightRotate(node.right);
  return leftRotate(node);
}

插入节点

递归插入后检查平衡因子，根据情况旋转：

function insertNode(node, value) {
  if (!node) return new AVLNode(value);
  if (value < node.value) {
    node.left = insertNode(node.left, value);
  } else if (value > node.value) {
    node.right = insertNode(node.right, value);
  } else {
    return node; // 重复值不插入
  }

  updateHeight(node);
  const balance = getBalanceFactor(node);

  // LL型
  if (balance > 1 && value < node.left.value) {
    return rightRotate(node);
  }
  // RR型
  if (balance < -1 && value > node.right.value) {
    return leftRotate(node);
  }
  // LR型
  if (balance > 1 && value > node.left.value) {
    return leftRightRotate(node);
  }
  // RL型
  if (balance < -1 && value < node.right.value) {
    return rightLeftRotate(node);
  }

  return node;
}

删除节点

递归删除后检查平衡，类似插入逻辑：

function deleteNode(node, value) {
  if (!node) return null;
  if (value < node.value) {
    node.left = deleteNode(node.left, value);
  } else if (value > node.value) {
    node.right = deleteNode(node.right, value);
  } else {
    if (!node.left || !node.right) {
      node = node.left || node.right;
    } else {
      const minRight = findMin(node.right);
      node.value = minRight.value;
      node.right = deleteNode(node.right, minRight.value);
    }
  }

  if (!node) return null;
  updateHeight(node);
  const balance = getBalanceFactor(node);

  // LL型
  if (balance > 1 && getBalanceFactor(node.left) >= 0) {
    return rightRotate(node);
  }
  // LR型
  if (balance > 1 && getBalanceFactor(node.left) < 0) {
    return leftRightRotate(node);
  }
  // RR型
  if (balance < -1 && getBalanceFactor(node.right) <= 0) {
    return leftRotate(node);
  }
  // RL型
  if (balance < -1 && getBalanceFactor(node.right) > 0) {
    return rightLeftRotate(node);
  }

  return node;
}

function findMin(node) {
  while (node.left) node = node.left;
  return node;
}

使用示例

let root = null;
root = insertNode(root, 10);
root = insertNode(root, 20);
root = insertNode(root, 30); // 自动触发左旋
root = insertNode(root, 5);
root = deleteNode(root, 20); // 删除后自动平衡

通过上述代码可实现AVL树的基本操作，确保动态维护平衡性。