当不平衡时，二进制的AVL旋转

Question

我正在尝试构建 avl tree ，但找不到很多代码例子，仅是理论。

我的代码具有所有旋转的实现，但是当树是1面时，我损失了一半的树。

这是我的代码：

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

正如您在运行片段时看到的那样，生成的树只有2个节点，而应该有6个节点。我在哪里出错了？

Answer 1

问题在于this.add方法。

它调用avl忽略该调用返回的节点。该返回的节点应替换作为参数传递的节点。由于您不知道该返回的节点应附加到哪儿处理此“返回”功能的功能。

这是可以改编的方法：

this.add = function(data, parent=root) {
    if (!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);
}

请注意，我在此处将分配删除到root。我建议将其移至您将初始调用到this.add的地方：

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

现在它将起作用。

重新设计

为JavaScript自2015年以来的JavaScript已成为类语法，我实际上会使用它，并创建tree> tree和node class。可以使用＃语法创建私有成员。

同样，计算节点的每时每刻都需要计算节点的平衡因子的高度。 AVL树的好处是，当您知道要旋转的节点的平衡因素时，您可以从它们的新平衡因素中得出 - 而无需实际高度。

这是所有这些都放在代码中，并附加一个输入框，您可以将节点添加到树上。该树以简单的凹痕格式显示（左侧的根）。

class Tree {
    #root = null;
    static #config = { 
        "2": { "0": [ 1, -1], "1": [ 0,  0], "2": [-1,  0] },
       "-2": { "0": [-1,  1],"-1": [ 0,  0],"-2": [ 1,  0] },
        "1": {"-1": [ 0, -2], "0": [ 0, -1], "1": [-1, -1] },
       "-1": { "1": [ 0,  2], "0": [ 0,  1],"-1": [ 1,  1] },
    };
    
    static #Node = class {
        constructor(data) {
            this.data = data;
            this.left = this.right = null;
            this.balance = 0;
        }

        add(data) {
            const side = data < this.data ? "left" : "right";
            let delta = data < this.data ? -1 : 1;
            if (!this[side]) {
                this[side] = new Tree.#Node(data);
            } else {
                let balance = Math.abs(this[side].balance);
                this[side] = this[side].add(data);
                if (balance || !this[side].balance) delta = 0;
            }
            this.balance += delta;
            return this.avl();
        }

        avl() {
            const balanced = this.balance;
            if (-2 === balanced) {
                if (0 < this.left.balance) {
                    this.left = this.left.rotateLeft();
                }
                return this.rotateRight(); 
            } else if (2 === balanced) {
                if (0 > this.right.balance) {
                    this.right = this.right.rotateRight();
                }
                return this.rotateLeft(); 
            }
            return this;
        }
        
        rotateRight() {
            return this.rotate("left", "right");
        }
        
        rotateLeft() {
            return this.rotate("right", "left");
        }

        rotate(inputSide, targetSide) {
            const target = this[inputSide];
            const child = target[targetSide];
            target[targetSide] = this;
            this[inputSide] = child;
            // Use a lookup table to determine how the balance is impacted by rotation
            [this.balance, target.balance] = Tree.#config[this.balance][target.balance];
            return target;
        }

        toString(indent="\n") {
            return   (this.right?.toString(indent + "  ") ?? "")
                   + indent + this.data
                   + (this.left?.toString(indent + "  ") ?? "");
        }
    }

    constructor(...values) {
        this.add(...values);
    }
    
    add(...values) {
        for (const data of values) {
            this.#root = this.#root?.add(data) ?? new Tree.#Node(data);
        }
    }
      
    toString() {
        return this.#root?.toString() ?? "<empty>";
    }    
}

const tree = new Tree;

// I/O handling
document.querySelector("button").addEventListener("click", () => {
    const input = document.querySelector("input");
    tree.add(+input.value);
    input.value = "";
    input.focus();
    document.querySelector("pre").textContent = tree;
});

<input type="number"><button>Add</button><br>
<pre></pre>