js实现avl树

AVL树的实现（JavaScript）

AVL树是一种自平衡二叉搜索树，通过旋转操作保持树的平衡。以下是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);
}

旋转操作

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

1. 左旋（右右情况）

   
   function leftRotate(node) {
   const newRoot = node.right;
   node.right = newRoot.left;
   newRoot.left = node;

node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1; newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1; return newRoot; }

2. 右旋（左左情况）
```javascript
function rightRotate(node) {
  const newRoot = node.left;
  node.left = newRoot.right;
  newRoot.right = node;

  node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
  newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;
  return newRoot;
}

1. 左右旋（左右情况）

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

2. 右左旋（右左情况）

   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; // 不允许重复值
  }

  node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
  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) {
    return leftRightRotate(node);
  }
  // 右左情况
  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) {
      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 node;

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

  // 平衡调整（与插入相同逻辑）
  if (balance > 1 && getBalanceFactor(node.left) >= 0) {
    return rightRotate(node);
  }
  if (balance > 1 && getBalanceFactor(node.left) < 0) {
    return leftRightRotate(node);
  }
  if (balance < -1 && getBalanceFactor(node.right) <= 0) {
    return leftRotate(node);
  }
  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 = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30); // 自动触发左旋
root = deleteNode(root, 20);

复杂度分析

• 插入/删除操作：O(log n) 时间
• 旋转操作：O(1) 时间
• 空间复杂度：O(n) 存储所有节点

实现时需注意边界条件处理，特别是删除操作可能引发多次旋转。可通过中序遍历验证树的正确性：

function inOrderTraversal(node) {
  if (node) {
    inOrderTraversal(node.left);
    console.log(node.value);
    inOrderTraversal(node.right);
  }
}