当前位置：首页 > JavaScript

js实现平衡二叉树

2026-04-05 04:01:10JavaScript

平衡二叉树实现

平衡二叉树（AVL树）是一种自平衡二叉搜索树，通过旋转操作确保左右子树高度差不超过1。以下是JavaScript实现的关键步骤：

节点结构

定义树节点，包含值、左右子节点和高度属性：

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

高度计算

获取节点高度，处理空节点情况：

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

平衡因子

计算左右子树高度差：

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

旋转操作

四种旋转情况处理不平衡：

右旋（LL型）

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

  x.right = y;
  y.left = T2;

  y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
  x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

  return x;
}

左旋（RR型）

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

  y.left = x;
  x.right = T2;

  x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
  y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;

  return y;
}

插入节点

递归插入后平衡树：

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; // 重复值不插入
  }

  node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
  const balance = getBalanceFactor(node);

  // 左子树高且新节点在左子树的左侧
  if (balance > 1 && value < node.left.value) {
    return rightRotate(node);
  }

  // 右子树高且新节点在右子树的右侧
  if (balance < -1 && value > node.right.value) {
    return leftRotate(node);
  }

  // 左子树高但新节点在左子树的右侧
  if (balance > 1 && value > node.left.value) {
    node.left = leftRotate(node.left);
    return rightRotate(node);
  }

  // 右子树高但新节点在右子树的左侧
  if (balance < -1 && value < node.right.value) {
    node.right = rightRotate(node.right);
    return leftRotate(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) {
      const temp = node.left || node.right;
      node = temp || null;
    } else {
      const temp = findMinNode(node.right);
      node.value = temp.value;
      node.right = deleteNode(node.right, temp.value);
    }
  }

  if (!node) return null;

  node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
  const balance = getBalanceFactor(node);

  // 平衡处理与插入相同
  // ...（此处省略旋转逻辑，与插入部分一致）

  return node;
}

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

使用示例

创建AVL树并测试操作：

js实现平衡二叉树

class AVLTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    this.root = insertNode(this.root, value);
  }

  delete(value) {
    this.root = deleteNode(this.root, value);
  }
}

// 测试
const tree = new AVLTree();
tree.insert(10);
tree.insert(20);
tree.insert(30); // 自动触发旋转平衡