JavaScript带子树大小的树结构:如何通过全局索引返回叶子节点及相对索引
嵌套树结构全局索引查找实现
基础说明
树节点分为两种类型,每个节点都带有size属性,表示该节点覆盖的全局条目总数:
container:容器节点,list属性存储子节点列表,size等于所有子孙leaf节点的条目总和leaf:叶子节点,list属性存储实际的内容数组,size等于自身数组的长度
演示用树结构数据如下:
const tree = { size: 100, type: 'container', list: [ { size: 30, type: 'container', list: [ { size: 10, type: 'leaf', list: [1,2,3,4,5,6,7,8,9,10] }, { size: 15, type: 'leaf', list: [1,2,...,15] }, { size: 25, type: 'leaf', list: [1,2,...,25] } ] }, { size: 50, type: 'container', list: [ { size: 20, type: 'leaf', list: [1,2,...,20] }, { size: 25, type: 'leaf', list: [1,2,...,25] }, { size: 25, type: 'leaf', list: [1,2,...,25] }, { size: 30, type: 'leaf', list: [1,2,...,30] } ] }, { size: 20, type: 'container', list: [ { size: 5, type: 'leaf', list: [1,2,3,4,5] }, { size: 15, type: 'leaf', list: [1,2,...,15] } ] } ] }
注意:leaf节点最多存储32个条目,container节点最多有32个直接子节点,实际leaf的内容可以是任意JavaScript值。
需求
实现getLeafContaining(tree, index)方法:
- 输入为根节点
tree,以及全局索引(所有leaf节点的内容按顺序拼接为一维序列后的统一索引) - 返回值包含两个部分:匹配的leaf节点,以及该条目在leaf节点内部的相对索引
- 全局索引超出合法范围时,返回
{ node: null, index: -1 }
原实现的问题
原作者写的初始代码如下:
const getLeafContaining = (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 } } } }
该实现存在三处问题:
- 入参校验缺失:仅判断了索引超过树总大小的情况,没有处理索引为负数的非法场景
- 区间判断错误:采用闭区间
startSize <= index && index <= endSize判断索引归属,实际节点对应的全局索引范围是左闭右开的[startSize, startSize + node.size)(节点最后一个全局索引为endSize - 1),会导致索引刚好等于下一个节点起始位置时,被错误归属到前一个节点,返回的相对索引超出leaf的实际长度范围 - 可读性差:使用命名循环标签
a/b控制流程,逻辑绕,不利于后续维护
稳健实现方案
优化后的代码采用逐层遍历、线性累加偏移量的逻辑,完全规避上述问题:
const getLeafContaining = (tree, index) => { // 全场景入参边界校验 if (index < 0 || index >= tree.size) { return { node: null, index: -1 } } // 初始化当前遍历层级的节点列表,以及层级第一个节点的全局起始偏移量 let currentNodes = [tree] let levelStartOffset = 0 while (true) { for (const node of currentNodes) { const nodeEnd = levelStartOffset + node.size // 左闭右开区间判断,精准匹配数组索引逻辑 if (index < nodeEnd) { if (node.type === 'leaf') { // 计算leaf内部相对索引并返回 return { node, index: index - levelStartOffset } } // 容器节点则下沉到下一层级遍历 currentNodes = node.list break } // 目标索引在当前节点后方,累加偏移量继续遍历 levelStartOffset += node.size } } }
实现特性
- 覆盖负数、超出总长度的非法索引校验,边界判断严谨
- 左闭右开的区间计算和数组索引规则完全一致,不会出现归属错误
- 无复杂标签控制逻辑,流程清晰易读
- 迭代实现无递归栈溢出风险,适配container/leaf最多32个子节点的约束,性能开销极低
内容的提问来源于stack exchange,提问作者Lance Pollard
相关产品推荐
相关产品推荐

