javascript - 如何构建一个树形数组，其中/哪些项可以拼接，只允许 1、2、4、8、16 或 32 个项的数组？
问题描述
所以对于类似的问题有一个非常优雅的答案。问题在于构建一个数组树，其中每个数组只有 1、2、4、8、16 或 32 个项目，并且每个项目都处于相同的嵌套级别。我在没有考虑整个系统的情况下制定了这个问题（我猜是在做快速原型设计），但是我认为当前的系统不会真正适用于从数组中间删除项目，或者将项目添加到数组中间. 很遗憾。
我需要在数组中间添加/删除项目的能力，因为这将用于分桶哈希表中的数组，或快速添加和删除项目的通用数组（如管理内存块）。因此，我正在考虑如何平衡这与希望内存块大小仅为 1、2、4、8、16 或 32 个项目的愿望。因此树，但我认为树需要与该问题中提出的问题略有不同。
我在想的是有一个如下的系统。嵌套数组树中的每个数组可以有 1、2、4、8、16 或 32 个项目，但这些项目不需要位于同一级别。将项目放在同一级别的原因是因为有一个非常有效的算法来getItemAt(index)判断它们是否处于同一级别。但它存在不允许有效插入/删除的问题。但我认为这可以通过让每个父数组“容器”跟踪它有多少深度嵌套的子元素来解决数组中的项目处于不同级别的问题。它基本上会跟踪子树的大小。然后要找到带有 的项目getItemAt(index)，您将遍历树的顶层，计算顶层树的大小，然后像这样缩小树的搜索范围。
此外，叶数组（每个数组有 1、2、4、8、16 或 32 个项目）可以删除项目，然后您只需调整该短数组项目的位置。所以你会从这个开始：
[1, 2, 3, 4, 5, 6, 7, 8]
...删除6，并得到这个（在哪里-）null：
[1, 2, 3, 4, 5, 7, 8, -]
然后，如果您9在说位置 3 添加一个项目，它将导致：
[1, 2, 9, 3, 4, 5, 7, 8]
这很好，因为假设您有一百万个项目数组。您现在只需调整最多包含 32 个项目的单个数组，而不是移动一百万个项目。
但是，当你在“这个树数组的中间”添加一个项目时，它会变得有点复杂，但是在一个 32 项目数组的末尾。您首先会认为您必须移动每个后续数组。但是有一种方法可以做到这一点，所以你不必做这种转变！这是一个案例。
我们从这里开始：
[
[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
9 , 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32],
[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
9 , 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32]
]
现在我们90在第 16 位添加一个项目。我们应该这样结束，因为这个数组的长度必须增长到 4：
[
[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
9 , 10, 11, 12, 13, 14, 15, 90,
16, 17, 18, 19, 20, 21, 22, 23,
24, 25, 26, 27, 28, 29, 30, 21],
[32],
-,
[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
9 , 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32]
]如果我们90现在删除，我们将以此结束：
[
[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
9 , 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, - ],
[32],
-,
[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
9 , 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32]
]
基本上，它正在最大限度地减少所做的更改。getByIndex(index)它会像这样工作，在数组上有更多元数据：
{
size: 64,
list: [
{
size: 31,
list: [
1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
9 , 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, - ] },
{
size: 1,
list: [32] },
null,
{
size: 32,
list: [
1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
9 , 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32] }
]
}
所以我的问题是，如何构建这样一个在每个级别只有 1、2、4、8、16 或 32 个节点的树，它允许在整个概念“数组”中的任何位置插入或删除节点，树中的叶节点不需要处于任何特定级别？如何实现该splice方法？
对于这个问题，暂时不要担心压缩，我会先尝试看看我是否可以自己解决这个问题。对于这个问题，只要在它们最终出现的地方留下垃圾和空值，这不太理想。我的意思是，如果您知道如何轻松压缩事物，那么一定要包括它，但我认为它会大大增加答案，所以默认应该将它排除在答案之外:)
另请注意，应将数组视为静态数组，即它们的大小不能动态增长。
的算法insertItemAt(index)将像这样工作：
- 找到合适的叶子数组来放置项目。（通过根据大小信息向下遍历）。
- 如果叶子中有一些空间（作为叶子数组末尾的空指针），那么只需移动项目以在其确切索引处为项目腾出空间。
- 如果叶子太短，用更长的替换它，然后将物品放在那片叶子上。
- 如果叶子是最大长度 (32)，则尝试添加另一个叶子兄弟。如果有 32 个兄弟姐妹，就不能轻易做到这一点......或者如果它更短，则还没有空的兄弟姐妹。
- 如果叶子是最大长度并且没有最大长度的兄弟姐妹，那么检查一个空闲的空兄弟姐妹。如果没有更多空闲的兄弟姐妹，则将具有空指针的兄弟姐妹的数量加倍，并创建下一个数组并将其放在那里。
- 如果叶子是最大长度，兄弟是最大长度，而父是最大长度，我很难想象算法应该做什么才能在遵守这些约束的同时增长，这就是我在这里挣扎的原因。
removeItemAt(index)（的第二个功能）的算法splice会做这样的事情：
- 根据树中每个数组节点的索引和大小信息找到合适的项。
- 将其设置为空。
- 如果在同一级别有多个空指针，则压缩周围的空指针。将它们降低，使它们等于 1、2、4、8、16 或 32（可能因为我们要删除它，所以它们永远不会等于 32）。但是这部分算法可以省略，我可能最终会弄清楚，除非你知道如何快速完成。
这是我到目前为止所拥有的。
const createTree = () => createTreeLeaf()
const createTreeContainer = () => {
return {
type: 'container',
list: [],
size: 0
}
}
const createTreeLeaf = () => {
return {
type: 'leaf',
list: [],
size: 0
}
}
const setItemAt = (tree, item, index) => {
let nodes = [tree]
let startSize = 0
a:
while (true) {
b:
for (let i = 0, n = nodes.length; i < n; i++) {
let node = nodes[i]
let endSize = startSize + node.size
if (startSize <= index && index < endSize) {
// it's within here.
if (node.type == 'container') {
nodes = node.list
break b
} else {
let relativeIndex = index - startSize
// grow if less than max
if (relativeIndex > node.size - 1) {
if (node.size == 32) {
// grow somehow
} else {
let newArray = new Array(node.size * 2)
node.list.forEach((x, i) => newArray[i] = x)
node.list = newArray
}
}
if (node.list[relativeIndex] == null) {
node.size++
}
node.list[relativeIndex] = item
break a
}
}
}
}
}
const insertItemAt = (tree, item, index) => {
let nodes = [tree]
let startSize = 0
a:
while (true) {
b:
for (let i = 0, n = nodes.length; i < n; i++) {
let node = nodes[i]
let endSize = startSize + node.size
if (startSize <= index && index < endSize) {
// it's within here.
if (node.type == 'container') {
nodes = node.list
break b
} else {
let relativeIndex = index - startSize
// grow if less than max
if (relativeIndex > node.size - 1 || isPowerOfTwo(node.size)) {
if (node.size == 32) {
// grow somehow
} else {
let newArray = new Array(node.size * 2)
node.list.forEach((x, i) => newArray[i] = x)
node.list = newArray
}
}
// todo: shift the items over to make room for this item
break a
}
}
}
}
}
const removeItemAt = (tree, item, index) => {
}
const appendItemToEndOfTree = (tree, item) => {
}
const getLeafContainingIndex = (tree, index) => {
if (index > tree.size - 1) {
return { node: null, index: -1 }
}
let nodes = [tree]
let startSize = 0
a:
while (true) {
b:
for (let i = 0, n = nodes.length; i < n; i++) {
let node = nodes[i]
let endSize = startSize + node.size
if (startSize <= index && index < endSize) {
if (node.type == 'container') {
nodes = node.list
break b
} else {
let relativeIndex = index - startSize
return { node, index: relativeIndex }
}
} else {
startSize = endSize
}
}
}
}
const getItemAt = (tree, getIndex) => {
const { node, index } = getLeafContainingIndex(tree, getIndex)
if (!node) return null
return node.list[index]
}
const isPowerOfTwo = (x) => {
return (x != 0) && ((x & (x - 1)) == 0)
}
const log = tree => console.log(JSON.stringify(tree.list))
// demo
const tree = createTree()
setItemAt(tree, { pos: '1st', attempt: 1 }, 0)
log(tree)
setItemAt(tree, { pos: '2nd', attempt: 2 }, 1)
log(tree)
setItemAt(tree, { pos: '2nd', attempt: 3 }, 1)
log(tree)
setItemAt(tree, { pos: '3rd', attempt: 4 }, 2)
log(tree)我认为“以某种方式成长”部分会像这样工作......
- 保持数组的索引相对于父级。
- 如果叶子长度为 32，那么您需要在父节点中创建更多空间。
- 如果父数组长度为 32，则将父数组一分为二，因此有两个 16 项数组。然后将父节点包装在一个新数组中（现在我们有一个 2 节点数组和 2 个 16 节点数组，它们都符合约束条件）。
- 更改第二个数组的索引。
- 获取相对于父级的插入索引。
- 根据插入节点的相对索引查找要选择两个节点中的哪一个。
- 重复这个过程（递归到父节点并再次尝试插入，因为它现在有一个新结构）。
注意：这应该像一个紧凑的列表一样工作。这意味着它内部永远不会有任何空格（除了尾随的空值，它们不是数组中的空格，只是根据 1、2、4、8、16、32 约束支持未来插入的占位符）。这意味着您只能 (1) 在两个现有项目之间挤压一个项目，(2) 在一个项目之后追加，(3) 在一个项目之前添加，以及 (4) 删除一个项目（只有通过移动叶子来填充空白空间左侧的项目）。
解决方案
要求接近B+ 树提供的要求。一个 32 元 B+ 树将提供以下属性：
- 树的叶子都在同一水平线上
- 实际数据仅存储在叶子中
- 除根外的所有内部节点至少有 16 个子节点（不包括
null填充节点） - 除根外的所有叶子至少有 16 个值（不包括
null填充物） - 如果根不是叶子，那么它至少有 2 个孩子
此外，它还有这个有用的功能：
- 叶节点通常维护在一个链表中，因此该链表的迭代将按其预期顺序访问数据
B+ 树是搜索树，这是一个不符合您要求的功能。这意味着这里不需要存储在 B+ 树内部节点中的典型键。
另一方面，您要求可以通过索引标识元素。正如您已经建议的那样，您可以使用一个属性扩展每个节点，该属性提供存储在以该节点为根的子树的叶子中的数据值的总数。这将允许在对数时间内按索引查找数据值。
动态节点大小
至于节点大小应为 2 到 32 的幂的要求：B+ 树不提供可变节点大小。但请注意，此 B+ 树中的所有节点都保证至少有 16 个已使用条目。唯一的例外是根，它可以有任意数量的已使用条目。
所以在我回答的第一个版本中，我并没有过多关注这个要求：实现它意味着有时你可以通过将非根节点的大小限制为 16 而不是 32 来节省非根节点的一些空间。但是下一个插入在该节点中将需要它（再次）扩展到 32 的大小。所以我认为这可能不值得付出努力。调整根的记录大小也不会带来太多收益，因为它仅适用于该单个节点。
在对此发表评论后，我调整了实现，因此每个节点将尽快/需要将其大小减小或扩展为 2 的上一个/下一个幂。这意味着非根节点有时可能会将其大小减少到 16（而它们有 16 个项目/子节点），并且根节点可以具有任何可能的权力（1、2、4、8、16 或 32），如尺寸。
其他实现选择
根据您的偏好，我避免使用递归。
我选择在每个节点中包含以下属性：
children：这是子节点或（在叶子的情况下）数据值的列表。此列表是一个包含 1、2、4、8、16 或 32 个插槽的数组，其中未使用的插槽用 填充null。这非常不像 JavaScript，但我知道您实际上是针对不同的语言，所以我选择了它。childCount：这表示上述数组中实际使用了多少个插槽。如果我们可以假设它null永远不能用作数据，我们可以不这样做，并且发生将表明真实内容的结束。但无论如何，我去了这家酒店。所以理论上，内容现在实际上可以包含预期null值。treeSize. 这是以该节点为根的子树的叶子中的数据项总数。如果这本身就是一个叶节点，那么它将始终等于childCount。parent. B+ 树实际上并不需要从子级到父级的反向引用，但我在此实现中采用了它，还因为它使提供基于非递归的实现变得更加容易（您似乎更喜欢）。prev,next: 这些属性引用兄弟节点（在同一级别），因此树的每一级都有其节点在一个双向链表中。B+ 树通常仅在底层具有此功能，但在其他级别也很方便。
B+ 树算法
插入
您已经草拟了一个插入算法。它确实会这样：
- 找到应该插入值的叶子
- 如果该叶子有空间，则在此处插入值并更新 treeSize（您将其称为大小），将增加的值在树中向上传播到根。
- 否则，检查节点是否有一个可以将一些项目转移到的邻居，以便为新值腾出空间。如果是这样，那就去做，然后停下来。
- 否则，创建一个新叶，并将节点的一半值移入其中。然后有空间插入值。根据索引，它将在旧节点或新节点中
- 现在的任务是将新节点作为兄弟节点插入父节点。使用相同的算法来执行该操作，但在上面的级别。
如果根需要拆分，则创建一个新的根节点，它将两个拆分节点作为其子节点。
在这个算法的执行过程中，受影响节点的属性当然应该得到很好的维护。
删除
- 找到应该删除值的叶子。
- 从该叶子中删除值，并更新 treeSize 属性，并在树中向上直到根。
- 如果该节点是根节点，或者该节点有超过 16 个已用插槽，则停止。
- 该节点的值太少，因此请查看邻居以查看它是否可以与该节点合并，或者以其他方式共享其某些条目以进行重新分配。
- 如果所选邻居中的项目和这个项目不能放在一个节点中，则重新分配这些项目，因此每个项目仍然至少有 16 个，然后停止。有一个边界情况，节点有 16 个项目，但邻居有 17 个。在这种情况下，重新分配值没有优势。然后也停下来。
- 否则将来自所选邻居的项目合并到当前节点中。
- 重复此算法以从上面的级别删除现在为空的邻居。
如果根最终只有一个子节点，则使根成为单个子节点，删除顶层。
执行
下面你会发现一个Tree类的实现。它包括您要求的方法：
getItemAtsetItemAtremoveItemAtinsertItemAt
它还包括一些额外的方法：
Symbol.iterator：这使得树实例可迭代。这允许使用树底层的链表轻松迭代值。print: 自己说话verify：这会以广度优先遍历的方式访问树的每个节点，检查是否满足所有条件，并且不存在不一致。在许多其他测试中，它还验证每个节点的填充因子是否超过 50%，或者换句话说：数组大小是承载内容的最小可能的 2 次方。如果测试失败，将抛出一个简单的异常。我没有付出任何努力为错误提供上下文：它们不应该发生。
片段
运行下面的代码片段将创建一个树实例，并执行 1000 次插入、1000 次更新/检索和 1000 次删除。并行地，相同的操作在一维数组上完成，使用splice. 在每一步之后，将树迭代的值与数组进行比较，并验证树的一致性。测试是在最大节点容量为 8（而不是 32）的情况下执行的，因此树垂直增长得更快，并且需要进行更多的移动、拆分和合并。
class Node {
constructor(capacity) {
// Mimic fixed-size array (avoid accidentally growing it)
this.children = Object.seal(Array(capacity).fill(null));
this.childCount = 0; // Number of used slots in children array
this.treeSize = 0; // Total number of values in this subtree
// Maintain back-link to parent.
this.parent = null;
// Per level in the tree, maintain a doubly linked list
this.prev = this.next = null;
}
setCapacity(capacity) {
if (capacity < 1) return;
// Here we make a new array, and copy the data into it
let children = Object.seal(Array(capacity).fill(null));
for (let i = 0; i < this.childCount; i++) children[i] = this.children[i];
this.children = children;
}
isLeaf() {
return !(this.children[0] instanceof Node);
}
index() {
return this.parent.children.indexOf(this);
}
updateTreeSize(start, end, sign=1) {
let sum = 0;
if (this.isLeaf()) {
sum = end - start;
} else {
for (let i = start; i < end; i++) sum += this.children[i].treeSize;
}
if (!sum) return;
sum *= sign;
// Apply the sum change to this node and all its ancestors
for (let node = this; node; node = node.parent) {
node.treeSize += sum;
}
}
wipe(start, end) {
this.updateTreeSize(start, end, -1);
this.children.copyWithin(start, end, this.childCount);
for (let i = this.childCount - end + start; i < this.childCount; i++) {
this.children[i] = null;
}
this.childCount -= end - start;
// Reduce allocated size if possible
if (this.childCount * 2 <= this.children.length) this.setCapacity(this.children.length / 2);
}
moveFrom(neighbor, target, start, count=1) {
// Note: `start` can have two meanings:
// if neighbor is null, it is the value/Node to move to the target
// if neighbor is a Node, it is the index from where value(s) have to be moved to the target
// Make room in target node
if (this.childCount + count > this.children.length) this.setCapacity(this.children.length * 2);
this.children.copyWithin(target + count, target, Math.max(target + count, this.childCount));
this.childCount += count;
if (neighbor !== null) {
// Copy the children
for (let i = 0; i < count; i++) {
this.children[target + i] = neighbor.children[start + i];
}
// Remove the original references
neighbor.wipe(start, start + count);
} else {
this.children[target] = start; // start is value to insert
}
this.updateTreeSize(target, target + count, 1);
// Set parent link(s)
if (!this.isLeaf()) {
for (let i = 0; i < count; i++) {
this.children[target + i].parent = this;
}
}
}
moveToNext(count) {
this.next.moveFrom(this, 0, this.childCount - count, count);
}
moveFromNext(count) {
this.moveFrom(this.next, this.childCount, 0, count);
}
basicRemove(index) {
if (!this.isLeaf()) {
// Take node out of the level's linked list
let prev = this.children[index].prev;
let next = this.children[index].next;
if (prev) prev.next = next;
if (next) next.prev = prev;
}
this.wipe(index, index + 1);
}
basicInsert(index, value) {
this.moveFrom(null, index, value);
if (value instanceof Node) {
// Insert node in the level's linked list
if (index > 0) {
value.prev = this.children[index-1];
value.next = value.prev.next;
} else if (this.childCount > 1) {
value.next = this.children[1];
value.prev = value.next.prev;
}
if (value.prev) value.prev.next = value;
if (value.next) value.next.prev = value;
}
}
pairWithSmallest() {
return this.prev && (!this.next || this.next.childCount > this.prev.childCount)
? [this.prev, this] : [this, this.next];
}
toString() {
return "[" + this.children.map(v => v??"-").join() + "]";
}
}
class Tree {
constructor(nodeCapacity=32) {
this.nodeCapacity = nodeCapacity;
this.root = new Node(1);
this.first = this.root; // Head of doubly linked list at bottom level
}
locate(offset) {
let node = this.root;
// Normalise argument
offset = offset < 0 ? Math.max(0, node.treeSize + offset) : Math.min(offset, node.treeSize);
while (!node.isLeaf()) {
let index = 0;
let child = node.children[index];
while (offset > child.treeSize || offset === child.treeSize && child.next) {
offset -= child.treeSize;
child = node.children[++index];
}
node = child;
}
return [node, offset];
}
getItemAt(offset) {
let [node, index] = this.locate(offset);
if (index < node.childCount) return node.children[index];
}
setItemAt(offset, value) {
let [node, index] = this.locate(offset);
if (index < node.childCount) node.children[index] = value;
}
removeItemAt(offset) {
let [node, index] = this.locate(offset);
if (index >= node.childCount) return;
while (true) {
console.assert(node.isLeaf() || node.children[index].treeSize === 0);
node.basicRemove(index);
// Exit when node's fill ratio is fine
if (!node.parent || node.childCount * 2 > this.nodeCapacity) return;
// Node has potentially too few children, we should either merge or redistribute
let [left, right] = node.pairWithSmallest();
if (!left || !right) { // A node with no siblings? Must become the root!
this.root = node;
node.parent = null;
return;
}
let sumCount = left.childCount + right.childCount;
let childCount = sumCount >> 1;
// Check whether to merge or to redistribute
if (sumCount > this.nodeCapacity) { // redistribute
// Move some data from the bigger to the smaller node
let shift = childCount - node.childCount;
if (!shift) { // Boundary case: when a redistribution would bring no improvement
console.assert(node.childCount * 2 === this.nodeCapacity && sumCount === this.nodeCapacity + 1);
return;
}
if (node === left) { // move some children from right to left
left.moveFromNext(shift);
} else { // move some children from left to right
left.moveToNext(shift);
}
return;
}
// Merge:
// Move all data from the right to the left
left.moveFromNext(right.childCount);
// Prepare to delete right node
node = right.parent;
index = right.index();
}
}
insertItemAt(offset, value) {
let [node, index] = this.locate(offset);
while (node.childCount === this.nodeCapacity) { // No room here
if (index === 0 && node.prev && node.prev.childCount < this.nodeCapacity) {
return node.prev.basicInsert(node.prev.childCount, value);
}
// Check whether we can redistribute (to avoid a split)
if (node !== this.root) {
let [left, right] = node.pairWithSmallest();
let joinedIndex = left === node ? index : left.childCount + index;
let sumCount = left.childCount + right.childCount + 1;
if (sumCount <= 2 * this.nodeCapacity) { // redistribute
let childCount = sumCount >> 1;
if (node === right) { // redistribute to the left
let insertInLeft = joinedIndex < childCount;
left.moveFromNext(childCount - left.childCount - +insertInLeft);
} else { // redistribute to the right
let insertInRight = index >= sumCount - childCount;
left.moveToNext(childCount - right.childCount - +insertInRight);
}
if (joinedIndex > left.childCount ||
joinedIndex === left.childCount && left.childCount > right.childCount) {
right.basicInsert(joinedIndex - left.childCount, value);
} else {
left.basicInsert(joinedIndex, value);
}
return;
}
}
// Cannot redistribute: split node
let childCount = node.childCount >> 1;
// Create a new node that will later become the right sibling of this node
let sibling = new Node(childCount);
// Move half of node node's data to it
sibling.moveFrom(node, 0, childCount, childCount);
// Insert the value in either the current node or the new one
if (index > node.childCount) {
sibling.basicInsert(index - node.childCount, value);
} else {
node.basicInsert(index, value);
}
// Is this the root?
if (!node.parent) {
// ...then first create a parent, which is the new root
this.root = new Node(2);
this.root.basicInsert(0, node);
}
// Prepare for inserting the sibling node into the tree
index = node.index() + 1;
node = node.parent;
value = sibling;
}
node.basicInsert(index, value);
}
/* Below this point: these methods are optional */
* [Symbol.iterator]() { // Make tree iterable
let i = 0;
for (let node = this.first; node; node = node.next) {
for (let i = 0; i < node.childCount; i++) yield node.children[i];
}
}
print() {
console.log(this.root && this.root.toString());
}
verify() {
// Raise an error when the tree violates one of the required properties
if (!this.root) return; // An empty tree is fine.
if (this.root.parent) throw "root should not have a parent";
// Perform a breadth first traversal
let q = [this.root];
while (q.length) {
if (q[0].isLeaf() && this.first !== q[0]) throw "this.first is not pointing to first leaf";
let level = [];
let last = null;
for (let parent of q) {
if (!(parent instanceof Node)) throw "parent is not instance of Node";
if (parent.children.length > this.nodeCapacity) throw "node's children array is too large";
if (parent.childCount > 0 && parent.childCount * 2 <= parent.children.length) throw "node's fill ratio is too low";
for (let i = parent.childCount; i < parent.children.length; i++) {
if (parent.children[i] !== null) throw "child beyond childCount should be null but is not";
}
let treeSize = parent.treeSize;
if (parent.isLeaf()) {
for (let value of parent.children.slice(0, parent.childCount)) {
if (value === null) throw "leaf has a null as value";
if (value instanceof Node) throw "leaf has a Node as value";
}
if (parent.treeSize !== parent.childCount) throw "leaf has mismatch in treeSize and childCount";
} else {
for (let node of parent.children.slice(0, parent.childCount)) {
if (node === null) throw "internal node has a null as value";
if (!(node instanceof Node)) throw "internal node has a non-Node as value";
if (node.parent !== parent) throw "wrong parent";
if (node.prev !== last) throw "prev link incorrect";
if (last && last.next !== node) throw "next link incorrect";
if (last && last.children.length + node.children.length <= this.nodeCapacity) {
throw "two consecutive siblings have a total number of children that is too small";
}
if (node.childCount * 2 < this.nodeCapacity) {
throw "internal node is too small: " + node;
}
level.push(node);
last = node;
treeSize -= node.treeSize;
}
if (treeSize) throw "internal node treeSize sum mismatches";
}
}
if (last && last.next) throw "last node in level has a next reference";
q = level;
}
}
test(count=100, option=3) {
// option:
// 0 = always insert & delete at left side (offset 0)
// 1 = always insert & delete at right side
// 2 = always insert & delete at middle
// 3 = insert & delete at random offsets
// Create array to perform the same operations on it as on the tree
let arr = [];
// Perform a series of insertions
for (let i = 0; i < count; i++) {
// Choose random insertion index
let index = Array.isArray(option) ? option[i] : [0, i, i >> 1, Math.floor(Math.random() * (i+1))][option];
// Perform same insertion in array and tree
arr.splice(index, 0, i);
this.insertItemAt(index, i);
// Verify tree consistency and properties
this.verify();
// Verify the order of values in the array is the same as in the tree
if (arr+"" !== [...this]+"") throw i + ": tree not same as array";
}
// Perform a series of updates
for (let i = 0; i < count; i++) {
// Choose random update index
let index = Math.floor(Math.random() * count);
// Perform same insertion in array and tree
arr[index] += count;
this.setItemAt(index, this.getItemAt(index) + count);
// Verify tree consistency and properties
this.verify();
// Verify the order of values in the array is the same as in the tree
if (arr+"" !== [...this]+"") throw "tree not same as array";
}
// Perform a series of deletions
for (let i = arr.length - 1; i >= 0; i--) {
// Choose random deletion index
let index = [0, i, i >> 1, Math.floor(Math.random() * (i+1))][option];
// Perform same deletion in array and tree
arr.splice(index, 1);
this.removeItemAt(index);
// Verify tree consistency and properties
this.verify();
// Verify the order of values in the array is the same as in the tree
if (arr+"" !== [...this]+"") throw "tree not same as array";
}
}
}
// Perform 1000 insertions, 1000 updates, and 1000 deletions on a tree with node capacity of 8
new Tree(8).test(1000);
console.log("all tests completed");推荐阅读
- java - 如何从泛型类访问类的方法？
- python - 使用firebase ID将json文件导入firebase
- javascript - 使用 JavaScript 显示的未定义元素
- android - 在 Google Android Mobile Vision API 中启用 Flash
- arrays - 在 Mongo 后端使用 findOne() 检索后，在对象数组上运行 forEach()
- ios - Safari 网络检查器无法在 iOS12 和 mac OS Mojave 中使用 cordova
- c# - web api - 从存储库层返回复杂的域对象
- c# - IInputStream.ReadAsync() 和 DataReader.LoadAsync() 仅适用于固定长度读取 (UWP C#)
- mysql - MYSQL 存储过程 - 在 MYSQL 中编写此存储过程的正确方法是什么 - 我收到 1064 错误
- laravel - Laravel 无法访问子域中间件中的用户