如何构建一个树数组可以拼接到哪些项目中，只允许1、2、4、8、16或32个项目的数组? [英] How to build a tree array into which / out of which items can be spliced, which only allows arrays of 1, 2, 4, 8, 16, or 32 items?
问题描述
因此，对于类似的问题，有一个非常优雅的答案.问题是构建一个数组树，其中每个数组只有 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, -]然后，如果您在位置 3 添加一个 9 项，则会导致:
[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]]现在我们在第 16 个位置添加一个项目 90.我们应该这样结束，因为这个数组的长度必须增长到 4:
如果我们现在删除90，我们会以这样的方式结束:
基本上，它是最小化所做的更改.对于 getByIndex(index) 它将像这样工作，在数组上有更多元数据:
<代码>{尺寸:64，列表: [{尺寸:31，列表: [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, - ] },{尺寸:1，列表:[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、4、8、16 或 32 个节点，从而允许在任何位置插入或删除节点?整体概念数组"，树中的叶节点不需要处于任何特定级别?如何实现splice方法?
对于这个问题，暂时不要担心压缩，我会先尝试看看我是否可以自己解决这个问题.对于这个问题，只需将垃圾和空值留在它们最终出现的地方，这不太理想.我的意思是，如果你知道如何轻松地压缩事物，那么无论如何都要包括它，但我认为它会显着增加答案，所以默认应该是将它排除在答案之外:)
另请注意，应将数组视为静态数组，即它们的大小不能动态增长.
insertItemAt(index) 的算法会像这样工作:
- 找到合适的叶子数组来放置项目.(根据大小信息向下遍历).
- 如果叶子中有一些空间(作为叶子数组末尾的空指针)，则只需移动项目以为其确切索引处的项目腾出空间.
- 如果叶子太短，用更长的替换它，然后将物品放在那片叶子中.
- 如果叶子是最大长度 (32)，则尝试添加另一个叶子兄弟.如果有 32 个兄弟姐妹，就不能简单地做到这一点......或者如果它更短的话，如果没有空兄弟姐妹.
- 如果叶子是最大长度并且没有最大长度的兄弟姐妹，那么检查一个空闲的空兄弟姐妹.如果没有更多的空闲兄弟节点，则将具有空指针的兄弟节点的数量加倍，然后创建下一个数组并将其放在那里.
- 如果叶子是最大长度，兄弟姐妹是最大长度，而父是最大长度，我很难想象算法应该做什么才能在遵守这些约束的同时增长，这是为什么我在这里挣扎.
removeItemAt(index)(splice 的第二个功能)的算法会做这样的事情:
- 根据树中每个数组节点的索引和大小信息找到合适的项目.
- 将其设置为 null.
- 如果在同一级别有多个空指针，则压缩周围的空指针.将它们降下来，使它们等于 1、2、4、8、16 或 32(可能因为我们要删除它永远不会等于 32).但是这部分算法可以省略，我可能最终会弄清楚这一点，除非您知道如何快速完成.
这是我到目前为止的基本内容.
const createTree = () =>创建树叶()const createTreeContainer = () =>{返回 {类型:'容器'，列表: []，尺寸:0}}const createTreeLeaf = () =>{返回 {类型:'叶'，列表: []，尺寸:0}}const setItemAt = (tree, item, index) =>{让节点 = [树]让开始大小 = 0A:而(真){乙:for (let i = 0, n = nodes.length; i node.size - 1) {如果(节点大小== 32){//以某种方式增长} 别的 {让 newArray = new Array(node.size * 2)node.list.forEach((x, i) => newArray[i] = x)node.list = newArray}}if (node.list[relativeIndex] == null) {节点大小++}node.list[relativeIndex] = 项目打破一个}}}}}const insertItemAt = (tree, item, index) =>{让节点 = [树]让开始大小 = 0A:而(真){乙:for (let i = 0, n = nodes.length; i node.size - 1 || isPowerOfTwo(node.size)) {如果(节点大小== 32){//以某种方式增长} 别的 {让 newArray = new Array(node.size * 2)node.list.forEach((x, i) => newArray[i] = x)node.list = newArray}}//待办事项:将项目移过来为该项目腾出空间打破一个}}}}}const removeItemAt = (tree, item, index) =>{}const appendItemToEndOfTree = (tree, item) =>{}const getLeafContainingIndex = (tree, index) =>{如果(索引> tree.size - 1){返回{节点:空，索引:-1}}让节点 = [树]让开始大小 = 0A:而(真){乙:for (let i = 0, n = nodes.length; i {const { 节点，索引 } = getLeafContainingIndex(tree, getIndex)如果(！节点)返回空返回 node.list[index]}const isPowerOfTwo = (x) =>{返回 (x != 0) &&((x & (x - 1)) == 0)}const log = 树 =>console.log(JSON.stringify(tree.list))//演示const 树 = createTree()setItemAt(tree, { pos: '1st', 尝试: 1 }, 0)日志(树)setItemAt(tree, { pos: '2nd', 尝试: 2 }, 1)日志(树)setItemAt(tree, { pos: '2nd', 尝试: 3 }, 1)日志(树)setItemAt(tree, { pos: '3rd', 尝试: 4 }, 2)日志(树) 以某种方式成长"我认为部分会像这样工作......
- 保持数组的索引相对于父级.
- 如果叶子长度为 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.父.B+ 树并不真正需要从子级到父级的反向引用，但我在此实现中采用了它，也是因为它使提供基于非递归的实现(您似乎更喜欢)更容易一些.prev、next:这些属性引用同级节点(在同一级别)，因此树的每一级都有其节点在一个双向链表中.B+ 树通常仅在底层具有此功能，但在其他级别具有此功能也很方便.
B+树算法
插入
您已经草拟了一个插入算法.确实会是这样:
- 找到应该插入值的叶子
- 如果那片叶子有空间，就在那里插入值并更新 treeSize(你称之为 size)，在树中向上传播到根部.
- 否则，检查节点是否有一个邻居，它可以转移一些项目，以便为新值腾出空间.如果是这样，那就去做，然后停下来.
- 否则，创建一个新叶，并将节点值的一半移入其中.然后有空间插入值.根据索引，它将在旧节点或新节点中
- 现在的任务是将新节点作为兄弟节点插入到父节点中.使用相同的算法来执行该操作，但在上述级别上.
如果根需要分裂，则创建一个新的根节点，将两个分裂节点作为其子节点.
在该算法的执行过程中，受影响节点的属性当然应该得到很好的维护.
删除
- 找到应该删除值的叶子.
- 从该叶子中移除值，并更新 treeSize 属性，并在树中向上直到根.
- 如果节点是根节点，或者节点有超过 16 个已用槽，则停止.
- 该节点的值太少，因此请查看邻居以查看它是否可以与此节点合并，或者以其他方式共享其某些条目以进行重新分配.
- 如果所选邻居中的项目不能放入一个节点，则重新分配这些项目，使每个项目仍然至少有 16 个，然后停止.有一个边界情况，节点有 16 个项目，但邻居有 17 个.在这种情况下，重新分配值没有优势.然后也停下来.
- 否则将来自所选邻居的项目合并到当前节点中.
- 重复此算法以从上层删除现在为空的邻居.
如果根最终只有一个子节点，则使根成为该单个子节点，移除顶层.
实施
下面是一个 Tree 类的实现.它包括您要求的方法:
getItemAtsetItemAtremoveItemAtinsertItemAt
它还包括一些额外的方法:
Symbol.iterator:这使得树实例可迭代.这允许使用树底层的链表轻松迭代值.print:不言自明verify:这会在广度优先遍历中访问树的每个节点，检查是否满足所有条件，并且不存在不一致.在许多其他测试中，它还验证每个节点的填充因子是否超过 50%，或者说:数组大小是承载内容的 2 的最小幂.如果测试失败，将抛出一个简单的异常.我没有努力提供错误的上下文:它们不应该发生.
片段
运行下面的代码片段将创建一个树实例，并执行 1000 次插入、1000 次更新/检索和 1000 次删除.同时，使用 splice 对一维数组执行相同的操作.每一步之后，将树迭代的值与数组进行比较，并验证树的一致性.测试是在最大节点容量为 8 个(而不是 32 个)的情况下进行的，因此树在垂直方向上的增长速度更快，并且需要进行更多的移位、分裂和合并.
class Node {构造函数(容量){//模拟固定大小的数组(避免意外增长)this.children = Object.seal(Array(capacity).fill(null));this.childCount = 0;//子数组中使用的插槽数this.treeSize = 0;//此子树中值的总数//维护到父级的反向链接.this.parent = null;//树中的每一层，维护一个双向链表this.prev = this.next = null;}setCapacity(容量){如果(容量＜1)返回；//这里我们创建一个新数组，并将数据复制到其中让孩子 = Object.seal(Array(capacity).fill(null));for (let i = 0; i < this.childCount; i++) children[i] = this.children[i];this.children = 儿童；}isLeaf() {返回 !(this.children[0] instanceof Node);}指数() {返回 this.parent.children.indexOf(this);}更新树大小(开始，结束，符号=1){让总和 = 0;如果 (this.isLeaf()) {总和 = 结束 - 开始；} 别的 {for (let i = start; i this.children.length) this.setCapacity(this.children.length * 2);this.children.copyWithin(target + count, target, Math.max(target + count, this.childCount));this.childCount += 计数；如果(邻居！== 空){//复制孩子for (let i = 0; i < count; i++) {this.children[target + i] = neighbor.children[start + i];}//删除原始引用邻居.wipe(开始，开始+计数)；} 别的 {this.children[目标] = 开始；//start 是要插入的值}this.updateTreeSize(target, target + count, 1);//设置父链接如果 (!this.isLeaf()) {for (let i = 0; i < count; i++) {this.children[target + i].parent = this;}}}moveToNext(计数){this.next.moveFrom(this, 0, this.childCount - 计数, 计数);}moveFromNext(计数){this.moveFrom(this.next, this.childCount, 0, count);}基本删除(索引){如果 (!this.isLeaf()) {//从关卡链表中取出节点让 prev = this.children[index].prev;让下一个 = this.children[index].next;if (prev) prev.next = next;如果(下一个)next.prev = prev;}this.wipe(index, index + 1);}基本插入(索引，值){this.moveFrom(null, index, value);如果(节点的值实例){//在层的链表中插入节点如果(索引> 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() {返回 this.prev &&(!this.next || this.next.childCount > this.prev.childCount)?[this.prev, this] : [this, this.next];}toString() {return "[" + this.children.map(v => v??"-").join() + "]";}}类树{构造函数(节点容量 = 32){this.nodeCapacity = nodeCapacity;this.root = 新节点(1);this.first = this.root;//底层双向链表的头部}定位(偏移){让节点 = this.root;//规范化参数偏移量 = 偏移量 <0 ?Math.max(0, node.treeSize + offset) : Math.min(offset, node.treeSize);而 (!node.isLeaf()) {让索引 = 0;让孩子 = node.children[index];while (offset > child.treeSize || offset === child.treeSize && child.next) {偏移量 -= child.treeSize;child = node.children[++index];}节点 = 孩子；}返回[节点，偏移量]；}getItemAt(偏移量){让 [节点，索引] = this.locate(offset);if (index < node.childCount) return node.children[index];}setItemAt(offset, value) {让 [节点，索引] = this.locate(offset);if (index < node.childCount) node.children[index] = value;}removeItemAt(偏移量){让 [节点，索引] = this.locate(offset);if (index >= node.childCount) 返回；而(真){console.assert(node.isLeaf() || node.children[index].treeSize === 0);node.basicRemove(索引)；//当节点的填充率很好时退出if (!node.parent || node.childCount * 2 > this.nodeCapacity) 返回；//节点的子节点可能太少，我们应该合并或重新分配让 [左，右] = node.pairWithSmallest();if (!left || !right) {//没有兄弟节点的节点?必须成根！this.root = 节点；node.parent = null;返回;}让 sumCount = left.childCount + right.childCount;让 childCount = sumCount >>1;//检查是合并还是重新分配if (sumCount > this.nodeCapacity) {//重新分配//将一些数据从较大的节点移到较小的节点让 shift = childCount - node.childCount;if (!shift) {//边界情况:当重新分配不会带来任何改进时console.assert(node.childCount * 2 === this.nodeCapacity && sumCount === this.nodeCapacity + 1);返回;}if (node === left) {//从右向左移动一些孩子left.moveFromNext(shift);} else {//从左到右移动一些孩子left.moveToNext(shift);}返回;}//合并://从右向左移动所有数据left.moveFromNext(right.childCount);//准备删除右节点节点 = right.parent;index = right.index();}}insertItemAt(偏移量，值){让 [节点，索引] = this.locate(offset);while (node.childCount === this.nodeCapacity) {//这里没有空间if (index === 0 && node.prev && node.prev.childCount < this.nodeCapacity) {返回 node.prev.basicInsert(node.prev.childCount, value);}//检查我们是否可以重新分配(以避免分裂)如果(节点！== this.root){让 [左，右] = node.pairWithSmallest();让joinedIndex = left === 节点?索引:left.childCount + 索引；让 sumCount = left.childCount + right.childCount + 1;if (sumCount <= 2 * this.nodeCapacity) {//重新分配让 childCount = sumCount >>1;if (node === right) {//重新分配到左边让 insertInLeft = joinIndex left.childCount ||joinIndex === left.childCount &&left.childCount >right.childCount) {right.basicInsert(joinedIndex - left.childCount, value);} 别的 {left.basicInsert(joinedIndex, value);}返回;}}//不能重新分配:分裂节点让 childCount = node.childCount >>1;//创建一个新节点，该节点稍后将成为该节点的右兄弟节点让兄弟=新节点(childCount)；//将节点节点数据的一半移动到它兄弟.moveFrom(节点，0，childCount，childCount)；//在当前节点或新节点中插入值如果(索引> node.childCount){Brother.basicInsert(index - node.childCount, value);} 别的 {node.basicInsert(索引，值)；}//这是根吗?如果(！节点.父){//...然后首先创建一个父级，即新的根this.root = 新节点(2);this.root.basicInsert(0, 节点);}//准备将兄弟节点插入树中index = node.index() + 1;节点 = node.parent;值 = 兄弟；}node.basicInsert(索引，值)；}/* 在这一点之下:这些方法是可选的 */* [Symbol.iterator]() {//使树可迭代让我 = 0;for (let node = this.first; node; node = node.next) {for (let i = 0; i this.nodeCapacity) 抛出节点的子数组太大"；if (parent.childCount > 0 && parent.childCount * 2 <= parent.children.length) 抛出节点的填充率太低"；for (let i = parent.childCount; i < parent.children.length; i++) {if (parent.children[i] !== null) 抛出childCount 之外的孩子应该为空但不是"；}让 treeSize = parent.treeSize;如果 (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";} 别的 {for (let node of parent.children.slice(0, parent.childCount)) {if (node === null) throw "内部节点有一个空值";if (!(node instanceof Node)) 抛出内部节点有一个非节点作为值"；if (node.parent !== parent) 抛出错误的父级"；if (node.prev !== last) 抛出上一个链接不正确"；if (last && last.next !== node) 抛出下一个链接不正确"；if (last && last.children.length + node.children.length <= this.nodeCapacity) {抛出连续两个兄弟姐妹的孩子总数太小"；}if (node.childCount * 2 < this.nodeCapacity) {抛出内部节点太小:"+节点；}水平推(节点)；最后=节点；treeSize -= node.treeSize;}if (treeSize) 抛出内部节点 treeSize 总和不匹配"；}}if (last && last.next) 抛出关卡中的最后一个节点有下一个引用"；q = 水平；}}测试(计数=100，选项=3){//选项://0 = 总是插入 &在左侧删除(偏移量 0)//1 = 总是插入 &在右侧删除//2 = 总是插入 &在中间删除//3 = 插入 &以随机偏移量删除//创建数组以对其执行与树相同的操作让 arr = [];//执行一系列插入for (let i = 0; i < count; i++) {//选择随机插入索引让索引 = Array.isArray(option) ?选项[i] : [0, i, i >>1、Math.floor(Math.random() * (i+1))][option];//在数组和树中执行相同的插入arr.splice(index, 0, i);this.insertItemAt(index, i);//验证树的一致性和属性this.verify();//验证数组中值的顺序与树中的顺序相同if (arr+"" !== [...this]+"") throw i + ": tree not same as array";}//执行一系列更新for (let i = 0; i < count; i++) {//选择随机更新索引让 index = Math.floor(Math.random() * count);//在数组和树中执行相同的插入arr[索引] += 计数；this.setItemAt(index, this.getItemAt(index) + count);//验证树的一致性和属性this.verify();//验证数组中值的顺序与树中的顺序相同if (arr+"" !== [...this]+"") 抛出树与数组不同"；}//执行一系列删除for (let i = arr.length - 1; i >= 0; i--) {//选择随机删除索引让索引 = [0, i, i >>1、Math.floor(Math.random() * (i+1))][option];//在数组和树中执行相同的删除arr.splice(index, 1);this.removeItemAt(index);//验证树的一致性和属性this.verify();//验证数组中值的顺序与树中的顺序相同if (arr+"" !== [...this]+"") 抛出树与数组不同"；}}}//在节点容量为 8 的树上执行 1000 次插入、1000 次更新和 1000 次删除新树(8).测试(1000)；console.log("所有测试已完成"); So there is a very elegant answer to a similar problem. The problem there was to build an array tree where every array had only 1, 2, 4, 8, 16, or 32 items, and where every item was at the same nesting level. I formulated this problem without having the entire system in mind (doing rapid prototyping I guess), but the current system I don't think will really work for deleting items from the middle of the array, or adding items into the middle of the array. Unfortunately.
I need the ability to add/remove items in the middle of the array because this will be used for arrays in bucketed hash tables, or general arrays which items are rapidly added and removed (like managing memory blocks). So I am thinking how to balance that with the desire to have memory block sizes of 1, 2, 4, 8, 16, or 32 items only. Hence the tree, but I think the tree needs to work slightly differently from the problem posed in that question.
What I'm thinking is having a system like follows. Each array in the nested array tree can have 1, 2, 4, 8, 16, or 32 items, but the items don't need to sit at the same level. The reason for putting items at the same level is because there is a very efficient algorithm for getItemAt(index) if they are at the same level. But it has the problem of not allowing efficient inserts/deletes. But I think this can be solved where items in an array are at different levels by having each parent array "container" keep track of how many deeply nested children it has. It would essentially keep track of the size of the subtree. Then to find the item with getItemAt(index), you would traverse the top level of the tree, count the top-level tree sizes, and then narrow your search down the tree like that.
In addition, the leaf arrays (which have 1, 2, 4, 8, 16, or 32 items each) can have items removed, and then you only have to adjust that short array item's positions. So you'd go from this:
[1, 2, 3, 4, 5, 6, 7, 8]
...delete 6, and get this (where - is null):
[1, 2, 3, 4, 5, 7, 8, -]
Then if you add an item 9 at say position 3, it would result in:
[1, 2, 9, 3, 4, 5, 7, 8]
This is nice because say you have a million items array. You now only have to adjust a single array with up to 32 items, rather than shifting a million items.
BUT, it gets a bit complicated when you add an item in the "middle of this tree array", but at the end of a 32-item array. You would first think you would have to shift every single subsequent array. But there is a way to make it so you don't have to do this shifting! Here is one case.
We start here:
[
[ 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]
]
Now we add an item 90 at the 16th position. We should end up with this, since this array must grow to be 4 in length:
[
[ 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]
]If we delete 90 now, we would end with this:
[
[ 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]
]
Basically, it is minimizing the changes that are made. To getByIndex(index) it would work like this, with more metadata on the arrays:
{
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] }
]
}
So my question is, how can you build such a tree that only has 1, 2, 4, 8, 16, or 32 nodes at each level, which allows for inserting or removing nodes at any place in the overall conceptual "array", where the leaf nodes in the tree don't need to be at any specific level? How to implement the splice method?
For this question, don't worry about compactification just yet, I will try and see if I can figure that out on my own first. For this question, just leave junk and nulls around wherever they end up being, which is less than ideal. I mean, if you know how to compactify things easily, then by all means include it, but I think it will add significantly to the answer, so the default should be to leave it out of the answer :)
Also note, the arrays should be treated as if they are static arrays, i.e. they can't dynamically grow in size.
The algorithm for insertItemAt(index) would work something like this:
- Find the appropriate leaf array to put the item in. (By traversing down based on size information).
- If the leaf has some room in it (as null pointers at the end of the leaf array), then just shift the items to make room for the item at its exact index.
- If the leaf is too short, replace it with a longer one, and place the item in that leaf.
- If the leaf is max length (32), then attempt to add another leaf sibling. Can't just easily do that if there are 32 siblings... Or if there are not already null siblings in place if it's shorter.
- If the leaf is max length and there aren't max length siblings, then check for a free null sibling. If there are no more free siblings, then double the number of siblings with null pointers, and create the next array and put it there.
- If the leaf is max length and the siblings are max length, and the parent is max length, I have a hard time imagining what the algorithm should do exactly in order to grow while adhering to these constraints, which is why I struggle here.
The algorithm for removeItemAt(index) (the second piece of functionality of splice) would do something like this:
- Find the appropriate item based on index and size information of each array node in the tree.
- Set it to null.
- Compactify surrounding null pointers if there are multiple of them at the same level. Bring them down so they equal 1, 2, 4, 8, 16, or 32 (probably since we're deleting it will never equal 32). But this portion of the algorithm can be left out, I can probably eventually figure this out, unless you know how to do it quickly.
Here is what I have basically so far.
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)
The "grow somehow" section would work sort of like this I think...
- Keep index of array relative to parent.
- If the leaf length is 32, then you need to create more room in the parent.
- If parent array is length 32, divide the parent array in half, so there are two 16 item arrays. Then wrap the parent nodes in a new array (now we have a 2-node array and 2 16-node arrays, which both fit the constraints).
- Change the indexes on the second array.
- Get index of insertion relative to parent.
- Find which of the two nodes to select based on the relative index for the insertion node.
- Repeat the process (recurse into the parent node and try again to insert, since it has a new structure now).
NOTE: This should work like a compact list. This means it never has any blank spaces inside of it (except the trailing nulls, which aren't spaces in the array, only placeholders to support future inserts according to the 1, 2, 4, 8, 16, 32 constraints). This means you can only (1) squeeze an item in between two existing, (2) append after an item, (3) prepend before an item, and (4) delete an item (only having the empty space filled by shifting the leaf items to the left).
The requirements are close to what a B+ tree offers. A 32-ary B+ tree would provide these properties:
- The leaves of the tree are all at the same level
- The actual data is stored only in the leaves
- All internal nodes, except the root, have at least 16 children (not counting the
nullfillers) - All leaves, except the root, have at least 16 values (not counting the
nullfillers) - If the root is not a leaf, then it will have at least 2 children
In addition it has this useful feature:
- Leaf nodes are commonly maintained in a linked list, so that iteration of that list will visit the data in its intended order
B+ trees are search trees, which is a feature that does not match your requirements. So that means the typical keys, that are stored in the internal nodes of a B+ tree, are not needed here.
On the other hand, you require that elements can be identified by index. As you already suggested, you can extend each node with a property that provides the total count of data values that are stored in the leaves of the subtree rooted in that node. This will allow to find a data value by index in logarithmic time.
Dynamic node sizes
As to the requirement that node sizes should be powers of 2 up to 32: B+ trees do not provide variable node sizes. But note that all nodes in this B+ tree are guaranteed to have at least 16 used entries. The only exception is the root, which could have any number of used entries.
So in a first version of my answer I did not focus too much on this requirement: implementing it would mean that sometimes you could save some space in an non-root node by limiting its size to 16 instead of 32. But the very next insertion in that node would require it to extend (again) to a size of 32. So I considered it might not be worth the effort. Adapting the record size for the root would also not contribute much gain as it just applies to that single node.
After a comment about this, I adapted the implementation, so each node will reduce or extend its size to the previous/next power of 2 as soon as possible/needed. This means that non-root nodes may sometimes get their size reduced to 16 (while they have 16 items/children), and the root can have any of the possible powers (1, 2, 4, 8, 16, or 32) as size.
Other implementation choices
In line with your preference I avoided the use of recursion.
I opted to include the following properties in each node:
children: this is the list of either child nodes or (in case of a leaf) of data values. This list is an array with 1, 2, 4, 8, 16 or 32 slots, where the non-used slots are filled withnull. This is very un-JavaScript like, but I understand you are actually targeting a different language, so I went with it.childCount: this indicates how many slots in the above array are actually used. We could do without this, if we could assume thatnullcan never be used as data, and an occurrence would indicate the end of the real content. But anyway, I went for this property. So in theory, the content could now actually include intendednullvalues.treeSize. this is the total number of data items that are in the leaves of the subtree that is rooted in this node. If this is itself a leaf node, then it will always be equal tochildCount.parent. B+ trees don't really need a back reference from a child to a parent, but I went with it for this implementation, also because it makes it somewhat easier to provide a non-recursion based implementation (which you seem to prefer).prev,next: these properties reference sibling nodes (in the same level), so that each level of the tree has its nodes in one, doubly linked list. B+ trees commonly have this at the bottom level only, but it is also handy to have at the other levels.
B+ Tree Algorithm
Insertion
You already sketched an algorithm for insertion. It would indeed go like this:
- Locate the leaf where the value should be inserted
- If that leaf has room for it, insert the value there and update the treeSize (you called it size), propagating that increase upward in the tree up to the root.
- Otherwise, check if the node has a neighbor to which it could shift some items, so to make room for the new value. If so, go do it, and stop.
- Otherwise, create a new leaf, and move half of the node's values into it. Then there is room to insert the value. Depending on the index, it will be in the old or new node
- Now the task is to insert the new node as sibling in the parent node. Use the same algorithm to perform that action, but on the level above.
If the root needs to split, then create a new root node that will have the two split nodes as its children.
During the execution of this algorithm, the properties of the impacted nodes should of course be well maintained.
Deletion
- Locate the leaf where the value should be deleted.
- Remove the value from that leaf, and update the treeSize property, and also upward in the tree up to the root.
- If the node is the root, or the node has more than 16 used slots, then stop.
- The node has too few values, so look at a neighbor to see whether it could merge with this one, or otherwise share some of its entries for redistribution.
- If the items in the chosen neighbor and this one could not fit in one node, then redistribute those items, so each still has at least 16 of them, and stop. There is a boundary case where the node has 16 items, but the neighbor has 17. In that case there is no advantage in redistributing values. Then also stop.
- Otherwise merge the items from the chosen neighbor into the current node.
- Repeat this algorithm for deleting the now empty neighbor from the level above.
If the root ends up with just one child node, then make the root to be that single child node, removing the top level.
Implementation
Below you'll find an implementation of a Tree class. It includes the methods you were asking for:
getItemAtsetItemAtremoveItemAtinsertItemAt
It also includes some extra methods:
Symbol.iterator: this makes the tree instance iterable. This allows for easy iteration of values, using the linked list of the bottom level of the tree.print: speaks for itselfverify: this visits every node of the tree in a breadth-first traversal, checking that all conditions are met, and no inconsistencies exist. Among many other tests, it also verifies that each node has a fill factor of more than 50%, or otherwise put: that the array size is the least possible power of two to host the content. If a test fails, a simple exception will be thrown. I didn't put any effort in providing context to the error: they should not ever occur.
Snippet
Running the snippet below will create one tree instance, and perform 1000 insertions, 1000 update/retrievals, and 1000 deletions. In parallel the same actions are done on a 1-dimensional array, using splice. After each step, the values from the tree iteration are compared with the array, and the consistency of the tree is verified. The test is performed with a maximum node capacity of 8 (instead of 32), so the tree grows faster vertically, and a lot more shifting, splitting and merging needs to happen.
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");
这篇关于如何构建一个树数组可以拼接到哪些项目中，只允许1、2、4、8、16或32个项目的数组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
