JavaScript实现AVL树旋转时失衡树节点丢失问题排查

算力阿峰

2026-8-28

问题描述

我正在尝试构建AVL树，但目前可找到的相关资料大多仅讲解理论内容，缺少足够的代码实现示例可供参考。

我已在代码中实现了全部旋转逻辑，但在构建单侧倾斜的失衡树时，会出现半数节点丢失的问题。

以下是我的实现代码：

function buildTree(dataSet) {
  let root = null
  
  function rotateRight(node) {
    return rotate(node, true)
  }

  function rotateLeft(node) {
    return rotate(node, false)
  }

  function rotate(node, right) {
    const inputNodeSide = right ? "left" : "right"
    const targetNodeSide = right ? "right" : "left"
    const targetNode = node[inputNodeSide]
    const targetNodeChild = targetNode[targetNodeSide]
    
    targetNode[targetNodeSide] = node
    node[inputNodeSide] = targetNodeChild
    return targetNode // as this is at the top
  }

  function createNode(data) {
    return {
      data,
      left: null,
      right: null,
      get balance() {
        return workOutHeight(this.left) -
          workOutHeight(this.right)
      },
      get height() {
        return workOutHeight(this)
      },
    }
  } // END createNode

  function workOutHeight(node) {
    if (null === node) {
      return -1
    }
    return Math.max(workOutHeight(node.left),
      workOutHeight(node.right)) + 1
  }

  function avl(node) {
    const balanced = node.balance
    if (2 === balanced) {
      if (0 > node.left.balance) {
        node.left = rotateLeft(node.left);
      }
      return rotateRight(node);
    } else if (-2 === balanced) {
      if (0 < node.right.balance) {
        node.right = rotateRight(node.right);
      }
      return rotateLeft(node);
    }
    return node
  }

  this.add = function(data, parent) {
    parent = parent || root;
    if (null === parent) {
      return root = createNode(data);
    } else if (data < parent.data) {
      if (null === parent.left) {
        return parent.left = createNode(data);
      }
      this.add(data, parent.left)
      avl(parent)
    } else if (data > parent.data) {
      if (null === parent.right) {
        return parent.right = createNode(data);
      }
      this.add(data, parent.right)
      avl(parent)
    }
  } // END addData

  this.tree = function() {
    return JSON.parse(JSON.stringify(root))
  }

  if (Array.isArray(dataSet)) {
    dataSet.forEach(val => this.add(val))
  }

} // END buildTree

console.log(new buildTree([2, 6, 9, 4, 7, 0]).tree())

运行上述代码片段可以发现，输入6个节点构建AVL树，最终输出的树结构仅包含2个节点，与预期的6个节点不符。

问题原因

核心错误是旋转后没有更新树的节点指针链接：

你的avl函数执行旋转后会返回当前子树调整后的新根节点，但在add方法的递归回溯逻辑中，你只是调用了avl(parent)，没有接收返回值，也没有把父节点的左/右子指针指向调整后的新根节点。
如果旋转发生在整棵树的根节点位置，你也没有更新全局存储的root变量，直接导致旋转后被抬升的节点和原有树结构断开连接，最终大量节点丢失。

举个实际运行的例子：插入第三个节点9时，初始根节点2出现右右失衡，左旋后6应该成为新的整树根，但代码中root变量仍然指向节点2，而节点2的右指针在旋转后已经被修改，后续插入的节点全部无法从根节点遍历到，自然出现节点丢失的问题。

修复方案

修改add方法的递归逻辑，每一层递归插入完成后，都接收平衡调整返回的新子树根，正确挂载到当前节点的左/右子指针上，最顶层同步更新全局根节点即可。修复后的add方法代码如下：

this.add = function(data, parent) {
  // 首次调用从根节点开始，接住返回值更新全局根
  if (parent === undefined) {
    root = this.add(data, root)
    return
  }
  // 遍历到空位置直接创建新节点返回
  if (null === parent) {
    return createNode(data);
  } else if (data < parent.data) {
    // 递归插入左子树，接住返回的调整后左子树根
    parent.left = this.add(data, parent.left)
  } else if (data > parent.data) {
    // 递归插入右子树，接住返回的调整后右子树根
    parent.right = this.add(data, parent.right)
  }
  // 对当前节点做平衡调整，返回调整后的当前子树根供上层挂载
  return avl(parent)
}

替换原有add方法后重新运行，即可得到包含全部6个节点的正确AVL树结构。

内容的提问来源于stack exchange，提问作者Brian