不平衡时二叉树的AVL旋转

Question

我正在尝试构建一个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())

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

Answer 1

问题出在

this.add

方法上。

它调用

avl

，忽略该调用返回的节点。此返回的节点应替换作为参数传递的节点。由于您不知道这个返回的节点应该附加到哪里，因此您应该将其return作为

this.add

的返回值，这意味着您应该重新设计整个函数来处理这个“返回”功能。

以下是如何调整：

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 进行

initial

调用的位置：

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

现在就可以了。

重新设计

自 ECMAScript 2015 起，JavaScript 就使用了

class

语法，我实际上会利用它，并创建一个

Tree

和

Node

类。可以使用

#

语法创建私有成员。

而且，每次需要计算节点的平衡因子时都计算节点的高度，效率不高。 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>