在 Javascript 中实现由 Array 备份的 BST

Question

我正在尝试使用数组实现 bst，但没有成功：

class BST {

  constructor() {

    this.array =[]

    this.rootSet = false;

    this.index = 0

  }

  getLeft(index) {

    return (2 * index) + 1

  }

  getRight(index) {

    return 2 * (index + 1)

  }

  getParent(index) {

    return index >>> 1

  }

  insert(value) {

    if (!this.rootSet) {

      this.rootSet = true

      this.array = [value]

      this.index++;

    } else {

      // inserts recursively.

      this.insertHelper(this.getParent(0), value);

    }

  }

  

  // helper function to insert recursively.

  insertHelper(index, value) {

    if (value < this.array[index] && this.array[this.getLeft(index)] === undefined) {

      this.array[this.getLeft(index)] = value

    } else if (value >= this.array[index] && this.array[this.getRight(index)] === undefined) {

      this.array[this.getRight(index)] = value

    } else {

      if (value < this.array[index]) {

        this.insertHelper(this.getLeft(index), value);

      } else {

        this.insertHelper(this.getRight(index), value);

      }

    }

  }

}

我尝试了以下内容：

a.insert(2)

a.insert(0)

a.insert(3)

a.insert(10)

a.insert(30)

a.array // [2, 0, 3, empty × 3, 10, empty × 7, 30]

a.array看起来不正确。不知道我在哪里犯了错误。

Answer 1

你的结果对我来说是正确的。稀疏性的原因是这是二叉树基于数组的支持结构的典型特征。如果树不完整，则由于空元素表示未填充的子树，因此存在浪费的条目。由于 BST 通常需要平衡以保持最佳时间复杂度，因此基于链接节点的方法是典型的解决方案，它使旋转和平衡更容易。通常，数组支持结构用于二进制堆，它受益于数组在堆分配节点和指针上的内存布局和速度；堆操作不允许稀疏性，并且很容易使用您在此处使用的相同父子关系在线性结构中进行推理。话虽如此，您可以大大简化代码：class BST {  constructor() {    this.array = [];  }  insert(value, ix=0) {    if (this.array[ix] === undefined) {      this.array[ix] = value;    }    else if (value < this.array[ix]) {      this.insert(value, ix * 2 + 1);    }    else {      this.insert(value, ix * 2 + 2);    }  }}/*    2   / \  0   3       \        10         \          30*/const bst = new BST();[2, 0, 3, 10, 30].forEach(e => bst.insert(e));console.log(bst.array);

Answer 2

我没有检查代码，但结果对我来说是正确的。数组中的第一项是根。然后接下来的两个是等级 1 节点然后接下来的 4 个是等级 2 节点。那么接下来的 8 个是 rank 4 节点 你的结果应该是