AVL Tree 实现：插入函数 - 参考被扭曲

Question

我在将13添加到树时遇到了错误，节点10的左右指针都引用回根，并创建循环引用。

我想是因为我理解Javascript语法错误。

code（打开控制台）

function rotLeft(node) {
  const parentNodeCopy = copyObj(node);
  const parentRightLeftChild =
    node.right.left !== null ? copyObj(node.right.left) : null;
  parentNodeCopy.right = parentRightLeftChild;

  node = node.right;
  node.left = parentNodeCopy;

  return node;
}

function rotRight(node) {
  const parentNodeCopy = copyObj(node);
  const parentLeftRightChild =
    node.left.right !== null ? copyObj(node.left.right) : null;
  parentNodeCopy.left = parentLeftRightChild;
  node = node.left;
  node.right = parentNodeCopy;

  return node;
}

function rebalance(node) {
  const bFact = threshold(node);

  if (bFact > 1) {
    if (threshold(node.left) < 0) node.left = rotLeft(node.left);
    node = rotRight(node);
  } else if (bFact < -1) {
    if (threshold(node.left) > 0) node.right = rotRight(node.right);
    node = rotLeft(node);
  }

  return node;
}

function insert(node, val) {
  if (node === null) return;

  if (val <= node.val) {
    if (node.left !== null) insert(node.left, val);
    else node.left = new TreeNode(val);
  } else {
    if (node.right !== null) insert(node.right, val);
    else node.right = new TreeNode(val);
  }

  return rebalance(node);
}

有什么建议吗？

Answer 1

问题是您没有使用 insert 的递归调用中的 returned 节点引用。 insert 可能 return 一个不同于它作为参数得到的节点的节点。通过不将其分配回 node.left 或 node.right，后者将保留对 non-cloned 节点的引用，从而为您提供不一致的树。

所以改变这个：

if (node.left !== null) insert(node.left, val);

对此：

if (node.left !== null) node.left = insert(node.left, val);

对镜像的情况做同样的事情。

其他备注

与您的问题无关：

应该没有必要创建节点的克隆。旋转可以通过改变现有节点来实现。
每次需要时动态检索高度会降低此实现的性能。最好将高度存储为节点的属性并保持更新。最好是存储平衡因子。通过一些巧妙的逻辑，您可以使平衡因子保持最新，而无需查询节点的高度。只需知道 children 的平衡因子以及正在执行的旋转即可。

AVL Tree 实现：插入函数 - 参考被扭曲

AVL Tree implementation: Insert function - Reference get twisted

javascript

algorithm

data-structures

其他备注