在 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

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

Answer 2

我认为你的结果是正确的。稀疏的原因是这是 array-based 二叉树支持结构的典型特征。如果树不完整，则由于空元素表示未填充的子树，因此存在浪费的条目。由于 BST 通常需要 balancing 来保持最佳时间复杂度，链接 node-based 方法是典型的解决方案，它使旋转和平衡更容易。

通常，数组后备结构用于 binary heaps，这受益于数组在 heap-allocated 节点和指针上的内存布局和速度；堆操作不允许稀疏性，并且很容易使用您在此处使用的相同 parent-child 关系在线性结构中进行推理。

话虽如此，您可以大大简化代码：

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

在 Javascript 中实现由 Array 支持的 BST

Implementing BST backed up by Array in Javascript

javascript

algorithm

binary-search-tree