当前位置：首页 > JavaScript

js实现avl树

2026-03-01 12:54:45JavaScript

AVL树简介

AVL树是一种自平衡二叉搜索树，通过旋转操作保持左右子树高度差不超过1。其核心在于维护节点的平衡因子（左子树高度减右子树高度），并在插入或删除时通过四种旋转（左旋、右旋、左右旋、右左旋）恢复平衡。

节点类实现

class AVLNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1; // 初始高度为1
  }
}

平衡因子计算

通过左右子树高度差计算当前节点的平衡因子：

js实现avl树

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

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

旋转操作

右旋（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型不平衡）：

js实现avl树

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);

  // 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) {
    node.left = leftRotate(node.left);
    return rightRotate(node);
  }
  // RL型
  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;
}

完整示例

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

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

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