如何构建一个树形数组,可以在其中拼接/从中拼接出哪些项目,从而仅允许包含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?

查看:46
本文介绍了如何构建一个树形数组,可以在其中拼接/从中拼接出哪些项目,从而仅允许包含1、2、4、8、16或32个项目的数组?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

对于类似问题,有一个非常优雅的答案.问题是要构建一个数组树,其中每个数组只有1、2、4、8、16或32个项目,而其中每个项目都处于相同的嵌套级别.我提出这个问题时并没有考虑到整个系统(我想进行快速原型制作),但是我认为当前的系统对于从数组中间删除项目 将项目添加到数组的中间.不幸的是.

我需要在数组中间添加/删除项目的能力,因为这将用于存储在桶中的哈希表中的数组,或者用于快速添加和删除项目的常规数组(例如管理内存块).因此,我在考虑如何与仅具有1、2、4、8、16或32个项目的内存块大小之间取得平衡.因此,这是一棵树,但我认为树的工作方式与 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、1617,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、1617,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32]] 

现在,我们在第16个位置添加项目 90 .我们应该以这个结尾,因为该数组的长度必须增长为4:

  [[1、2、3、4、5、6、7、8,9,10,11,12,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、1617,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、1617,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、1617,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32]] 

基本上,它使所做的更改最小化.要 getByIndex(index),它将像这样工作,并在数组上添加更多元数据:

  {大小:64,列表: [{大小:31,列表: [1,2,3,4,5,6,7,8,9、10、11、12、13、14、15、1617,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、1617,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32]}]} 

所以我的问题是,如何构建这样一个树,该树在每个级别上只有1、2、4、8、16或32个节点,从而允许在节点的任何位置插入或删除节点.整体概念上的数组",树中的叶节点不需要处于任何特定级别吗?如何实现 splice 方法?

对于这个问题,现在不用担心压缩,我将尝试看看是否可以自己解决.对于这个问题,请将垃圾和null保留在最终出现的位置,这不理想.我的意思是,如果您知道如何轻松地压缩内容,则一定要包含它,但我认为它将大大增加答案,因此默认设置应将其排除在答案之外:)

还请注意,应该将数组视为静态数组,即它们不能动态增长.

insertItemAt(index)的算法将像这样工作:

  • 找到合适的叶子阵列以放入该物品.(根据尺寸信息向下遍历).
  • 如果叶子中有一些空间(作为叶子数组末尾的空指针),则只需移动项目即可为其精确索引处的空间腾出空间.
  • 如果叶子太短,则用更长的叶子代替,然后将物品放在该叶子中.
  • 如果叶子是最大长度(32),则尝试添加另一个叶子同级.如果有32个同胞,就不能轻易地做到这一点……或者如果它更短,则还没有空同胞.
  • 如果叶子是最大长度,并且没有最大长度的同级,则检查是否有空的同级同级.如果没有更多的可用兄弟姐妹,则将具有空指针的兄弟姐妹数量加倍,并创建下一个数组并将其放在那里.
  • 如果叶子是最大长度,而兄弟姐妹是最大长度,而父级是最大长度,那么我很难想象在遵守这些约束的同时,算法应该如何精确执行才能增长为什么我在这里挣扎.

removeItemAt(index)( splice 的第二功能)的算法将执行以下操作:

  • 根据树中每个数组节点的索引和大小信息找到合适的项目.
  • 将其设置为null.
  • 如果在同一级别有多个空指针,则压缩周围的空指针.降低它们,使其等于1、2、4、8、16或32(可能因为我们正在删除,它永远不会等于32).但是算法的这一部分可以省去,除非您知道如何快速执行,否则我可能最终可以解决.

这是我到目前为止基本拥有的.

  const createTree =()=>createTreeLeaf()const createTreeContainer =()=>{返回 {类型:容器",列表: [],大小:0}}const createTreeLeaf =()=>{返回 {类型:叶",列表: [],大小:0}}const setItemAt =(树,项目,索引)=>{让节点= [树]让startSize = 0A:而(true){b:for(让i = 0,n = nodes.length; i< n; i ++){设节点=节点[i]让endSize = startSize + node.sizeif(startSize< = index&&< endSize){//它在这里.如果(node.type =='container'){节点= node.list打破b} 别的 {让relativeIndex =索引-startSize//如果小于最大则增长如果(relativeIndex> node.size-1){如果(node.size == 32){//以某种方式成长} 别的 {让newArray = new Array(node.size * 2)node.list.forEach((x,i)=> newArray [i] = x)node.list = newArray}}如果(node.list [relativeIndex] == null){node.size ++}node.list [relativeIndex] =项打破一个}}}}}const insertItemAt =(树,项目,索引)=>{让节点= [树]让startSize = 0A:而(true){b:for(让i = 0,n = nodes.length; i< n; i ++){设节点=节点[i]让endSize = startSize + node.sizeif(startSize< = index&&< endSize){//它在这里.如果(node.type =='container'){节点= node.list打破b} 别的 {让relativeIndex =索引-startSize//如果小于最大则增长如果(relativeIndex> node.size-1 || isPowerOfTwo(node.size)){如果(node.size == 32){//以某种方式成长} 别的 {让newArray = new Array(node.size * 2)node.list.forEach((x,i)=> newArray [i] = x)node.list = newArray}}//待办事项:将项目移开,以便为此项目腾出空间打破一个}}}}}const removeItemAt =(树,项目,索引)=>{}const appendItemToEndOfTree =(树,项目)=>{}const getLeafContainingIndex =(tree,index)=>{如果(索引> tree.size-1){返回{节点:空,索引:-1}}让节点= [树]让startSize = 0A:而(true){b:for(让i = 0,n = nodes.length; i< n; i ++){设节点=节点[i]让endSize = startSize + node.sizeif(startSize< = index&&< endSize){如果(node.type =='container'){节点= node.list打破b} 别的 {让relativeIndex =索引-startSize返回{节点,索引:relativeIndex}}} 别的 {startSize = endSize}}}}const getItemAt =(tree,getIndex)=>{const {node,index} = getLeafContainingIndex(tree,getIndex)如果(!node)返回null返回node.list [index]}const isPowerOfTwo =(x)=>{return(x!= 0)&&((x&(x-1))== 0)}const log = tree =>console.log(JSON.stringify(tree.list))//演示const tree = createTree()setItemAt(tree,{pos:'1st',try:1},0)日志(树)setItemAt(tree,{pos:'2nd',try:2},1)日志(树)setItemAt(tree,{pos:'2nd',try:3},1)日志(树)setItemAt(tree,{pos:'3rd',try:4},2)日志(树) 

以某种方式增长"我认为该部分的工作方式如下:

  • 保持数组相对于父级的索引.
  • 如果叶子长度为32,则需要在父级中创建更多空间.
  • 如果父数组的长度为32,则将父数组一分为二,因此有两个16项数组.然后将父节点包装在一个新的数组中(现在我们有一个2节点数组和2个16节点数组,这两个数组都符合约束).
  • 更改第二个数组上的索引.
  • 获取相对于父级的插入索引.
  • 根据插入节点的相对索引查找要选择的两个节点中的哪个.
  • 重复该过程(递归到父节点,然后尝试再次插入,因为它现在具有新结构了.)

注意:这应该像一个紧凑的列表一样工作.这意味着它里面永远不会有任何空格(尾随的null除外,后者不是数组中的空格,只是占位符根据1、2、4、8、16、32约束支持将来的插入).这意味着您只能(1)在两个现有对象之间挤压一个项目,(2)在一个项目之后追加,(3)在一个项目之前添加,以及(4)删除一个项目(只能通过移动叶子来填充空白空间左侧的项目).

解决方案

要求接近

  class节点{构造函数(容量){//模拟固定大小的数组(避免意外增大数组)this.children = Object.seal(Array(capacity).fill(null));this.childCount = 0;//子数组中已使用的插槽数this.treeSize = 0;//此子树中的值总数//保持反向链接至父级.this.parent = null;//在树中的每个级别上,维护一个双向链接列表this.prev = this.next = null;}setCapacity(capacity){如果(容量< 1)返回;//在这里我们创建一个新数组,并将数据复制到其中让孩子= Object.seal(Array(capacity).fill(null));for(let i = 0; i  this.children.length)this.setCapacity(this.children.length * 2);this.children.copyWithin(target + count,target,Math.max(target + count,this.childCount));this.childCount + =计数;if(neighbor!== null){//复制孩子for(让i = 0; i< count; i ++){this.children [target + i] = neighbor.children [start + i];}//删除原始引用neighbor.wipe(开始,开始+计数);} 别的 {this.children [target] =开始;//start是要插入的值}this.updateTreeSize(target,target + count,1);//设置父链接如果(!this.isLeaf()){for(让i = 0; i< count; i ++){this.children [target + i] .parent = this;}}}moveToNext(count){this.next.moveFrom(this,0,this.childCount-计数,计数);}moveFromNext(count){this.moveFrom(this.next,this.childCount,0,count);}basicRemove(index){如果(!this.isLeaf()){//将节点从关卡的链接列表中删除让prev = this.children [index] .prev;让next = this.children [index] .next;如果(上一个)prev.next =下一个;如果(下一个)next.prev = prev;}this.wipe(index,index + 1);}basicInsert(索引,值){this.moveFrom(null,index,value);if(Node的value instance){//将节点插入到关卡的链表中如果(索引> 0){value.prev = this.children [index-1];value.next = value.prev.next;}否则,如果(this.childCount> 1){value.next = this.children [1];value.prev = value.next.prev;}如果(value.prev)value.prev.next = value;如果(value.next)value.next.prev = value;}}pairWithSmallest(){返回this.prev&&(!this.next || this.next.childCount> this.prev.childCount)?[this.prev,this]:[this,this.next];}toString(){返回"[" + this.children.map(v => v ??-").join()+]";}}类Tree {构造函数(nodeCapacity = 32){this.nodeCapacity = nodeCapacity;this.root =新的Node(1);this.first = this.root;//底层双向链表的头}定位(偏移){让节点= this.root;//归一化参数偏移量=偏移量<0?Math.max(0,node.treeSize + offset):Math.min(offset,node.treeSize);while(!node.isLeaf()){令index = 0;让child = node.children [index];while(offset> child.treeSize || offset === child.treeSize& child.next){偏移量-= child.treeSize;child = node.children [++ index];}节点=子节点;}返回[节点,偏移量];}getItemAt(offset){让[节点,索引] = this.locate(offset);如果(index< node.childCount)返回node.children [index];}setItemAt(offset,value){让[节点,索引] = this.locate(offset);如果(index< node.childCount)node.children [index] =值;}removeItemAt(offset){让[节点,索引] = this.locate(offset);如果(index> = node.childCount)返回;而(true){console.assert(node.isLeaf()|| node.children [index] .treeSize === 0);node.basicRemove(index);//当节点的填充率合适时退出如果(!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;索引= right.index();}}insertItemAt(offset,value){让[节点,索引] = this.locate(offset);while(node.childCount === this.nodeCapacity){//这里没有空间if(索引=== 0&&&&&&&&&&&&&&"节点数量.返回node.prev.basicInsert(node.prev.childCount,value);}//检查是否可以重新分配(避免拆分)如果(节点!== this.root){让[左,右] = node.pairWithSmallest();让joinedIndex = left ===节点?index:left.childCount +索引;让sumCount = left.childCount + right.childCount + 1;if(sumCount< = 2 * this.nodeCapacity){//重新分配让childCount = sumCount>>1;if(node === right){//重新分配到左侧让insertInLeft = joinedIndex<childCount;left.moveFromNext(childCount-left.childCount-+ insertInLeft);} else {//重新分配到右边让insertInRight =索引> = sumCount-childCount;left.moveToNext(childCount-right.childCount-+ insertInRight);}如果(joinedIndex> left.childCount ||joinIndex === left.childCount&&left.childCount>right.childCount){right.basicInsert(joinedIndex-left.childCount,值);} 别的 {left.basicInsert(joinedIndex,value);}返回;}}//无法重新分配:拆分节点让childCount = node.childCount>>1;//创建一个新节点,该节点以后将成为该节点的右兄弟let sibling = new Node(childCount);//将一半节点的数据移到其中sibling.moveFrom(node,0,childCount,childCount);//将值插入当前节点或新节点如果(索引> node.childCount){sibling.basicInsert(index-node.childCount,value);} 别的 {node.basicInsert(索引,值);}//这是根吗?如果(!node.parent){//...然后首先创建一个父对象,这是新的根this.root =新的Node(2);this.root.basicInsert(0,节点);}//准备将同级节点插入树中索引= node.index()+1;节点= node.parent;值=同级;}node.basicInsert(索引,值);}/*在这一点上:这些方法是可选的*/* [Symbol.iterator](){//使树可迭代让我= 0;for(让node = this.first; node; node = node.next){for(让i = 0; i< node.childCount; i ++)产生node.children [i];}}打印() {console.log(this.root&& this.root.toString());}核实() {//当树违反必需的属性之一时引发错误如果(!this.root)返回;//可以使用一棵空树.如果(this.root.parent)抛出"root不应该有父母";//执行广度优先遍历令q = [this.root];而(q.length){如果(q [0] .isLeaf()&&this.first!== q [0])抛出"this.first没有指向第一片叶子";让水平= [];让last = null;为(让q的父代){如果(!(parent instanceof Node))抛出"parent不是Node的实例";如果(parent.children.length> this.nodeCapacity)抛出节点的子节点数组太大";如果(parent.childCount> 0&& parent.childCount * 2< = parent.children.length)抛出节点的填充率太低";for(让i = parent.childCount; i< parent.children.length; i ++){如果(parent.children [i]!== null)抛出"childCount以外的孩子应该为null,但不是";}让treeSize = parent.treeSize;如果(parent.isLeaf()){对于(让parent.children.slice(0,parent.childCount)的值){如果(value === null)抛出叶子的值为null";如果(节点的value instanceof)抛出叶子将节点作为值";}如果(parent.treeSize!== parent.childCount)抛出叶子的treeSize和childCount不匹配";} 别的 {for(让parent.children.slice(0,parent.childCount)的节点){如果(node === null)抛出内部节点的值为null";如果(!(node instanceof Node))抛出内部节点具有非节点作为值";如果(node.parent!==父级)抛出错误的父级";如果(node.prev!== last)抛出上一个链接不正确";如果(last&& last.next!==节点)抛出下一个链接不正确";if(last&& last.children.length + node.children.length< = this.nodeCapacity){抛出两个连续的兄弟姐妹的孩子总数太小";}如果(node.childCount * 2< this.nodeCapacity){抛出内部节点太小:" +节点;}level.push(node);last =节点;treeSize-= node.treeSize;}如果(treeSize)抛出内部节点treeSize总和不匹配";}}如果(last&& last.next)抛出级别中的最后一个节点具有下一个引用";q =级别;}}test(count = 100,option = 3){//选项://0 =始终插入&在左侧删除(偏移量0)//1 =始终插入&在右侧删除//2 =始终插入&在中间删除//3 =插入&随机偏移删除//创建数组以对其执行与在树上相同的操作让arr = [];//执行一系列插入for(让i = 0; i< count; i ++){//选择随机插入索引让index = Array.isArray(option)?option [i]:[0,i,i>1,Math.floor(Math.random()*(i + 1))] [选项];//在数组和树中执行相同的插入arr.splice(index,0,i);this.insertItemAt(index,i);//验证树的一致性和属性this.verify();//验证数组中值的顺序与树中的顺序相同如果(arr +"!== [... this] +")抛出i +:与数组不相同的树";}//执行一系列更新for(让i = 0; i< count; i ++){//选择随机更新索引让index = Math.floor(Math.random()* count);//在数组和树中执行相同的插入arr [index] + = count;this.setItemAt(index,this.getItemAt(index)+ count);//验证树的一致性和属性this.verify();//验证数组中值的顺序与树中的顺序相同如果(arr +"!== [... this] +")抛出树与数组不相同";}//执行一系列删除for(让i = arr.length-1; i> = 0; i--){//选择随机删除索引设索引= [0,i,i>1,Math.floor(Math.random()*(i + 1))] [选项];//在数组和树中执行相同的删除arr.splice(index,1);this.removeItemAt(index);//验证树的一致性和属性this.verify();//验证数组中值的顺序与树中的顺序相同如果(arr +"!== [... this] +")抛出树与数组不相同";}}}//在节点容量为8的树上执行1000次插入,1000次更新和1000次删除新Tree(8).test(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 null fillers)
  • All leaves, except the root, have at least 16 values (not counting the null fillers)
  • 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 with null. 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 that null can 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 intended null values.
  • 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 to childCount.
  • 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:

  • getItemAt
  • setItemAt
  • removeItemAt
  • insertItemAt

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 itself

  • verify: 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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆