当前位置：首页 > JavaScript

js实现avl树

2026-01-30 21:49:05JavaScript

AVL树的基本概念

AVL树是一种自平衡二叉搜索树，通过旋转操作保持树的平衡。每个节点的平衡因子（左子树高度减右子树高度）绝对值不超过1。插入或删除节点后，若平衡被破坏，需通过旋转恢复平衡。

节点结构

AVL树的节点需存储值、左右子节点指针和高度。以下为节点类的实现：

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

平衡因子计算

通过左右子树高度差计算平衡因子：

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

节点高度更新

节点高度需动态更新，确保反映子树变化：

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

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 insert(node, value) {
  if (!node) return new AVLNode(value);

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

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

  // LL型
  if (balanceFactor > 1 && value < node.left.value) {
    return rightRotate(node);
  }
  // RR型
  if (balanceFactor < -1 && value > node.right.value) {
    return leftRotate(node);
  }
  // LR型
  if (balanceFactor > 1 && value > node.left.value) {
    return leftRightRotate(node);
  }
  // RL型
  if (balanceFactor < -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) {
      const temp = node.left || node.right;
      node = temp || null;
    } else {
      const temp = findMin(node.right);
      node.value = temp.value;
      node.right = deleteNode(node.right, temp.value);
    }
  }

  if (!node) return null;

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

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

  return node;
}

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

完整示例

以下为AVL树的完整使用示例：

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

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

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

// 使用示例
const tree = new AVLTree();
tree.insert(10);
tree.insert(20);
tree.insert(30); // 自动平衡
tree.delete(20); // 删除后仍保持平衡