当树节点具有子树大小时，如何按索引返回树节点? [英] How to return the tree node by index when tree nodes have subtree size?

问题描述

说我有一段演示数据:

{
  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,3,4,5,6,7,8,9,10,11,12,13,14,15]
        },
        {
          size: 25,
          type: 'leaf',
          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]
        }
      ]
    },
    {
      size: 50,
      type: 'container',
      list: [
        {
          size: 20,
          type: 'leaf',
          list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
        },
        {
          size: 25,
          type: 'leaf',
          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]
        },
        {
          size: 25,
          type: 'leaf',
          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]
        }
        ,
        {
          size: 30,
          type: 'leaf',
          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]
        }
      ]
    },
    {
      size: 20,
      type: 'container',
      list: [
        {
          size: 5,
          type: 'leaf',
          list: [1,2,3,4,5]
        },
        {
          size: 15,
          type: 'leaf',
          list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
        }
      ]
    }
  ]
}

请注意，我只是填写了所谓的叶子"具有整数的节点以显示其数组位置.但是它们可以填充任何JavaScript对象(数组，对象，字符串，数字等).叶子节点最多可以包含32个项目，但是对于这个问题，我认为这并不重要.容器节点也只能有32个直接子节点.

怎么说" getLeafContaining(tree，index)"，它将在其中返回在全局 index 处具有该项的叶子以及相对索引.我说的是全球索引"因为如果您将所有叶子节点作为顺序节点，则这是叶子节点的索引.

How do you say getLeafContaining(tree, index), where it will return you the leaf which has the item at the global index, as well as the relative index. I say "global index" because this is the index of the leaf node if you were to take all of the leaf nodes as sequential.

到目前为止，我所做的是:

What I have done so far is this:

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
      }
    }
  }
}

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,3,4,5,6,7,8,9,10,11,12,13,14,15]
        },
        {
          size: 25,
          type: 'leaf',
          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]
        }
      ]
    },
    {
      size: 50,
      type: 'container',
      list: [
        {
          size: 20,
          type: 'leaf',
          list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
        },
        {
          size: 25,
          type: 'leaf',
          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]
        },
        {
          size: 25,
          type: 'leaf',
          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]
        }
        ,
        {
          size: 30,
          type: 'leaf',
          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]
        }
      ]
    },
    {
      size: 20,
      type: 'container',
      list: [
        {
          size: 5,
          type: 'leaf',
          list: [1,2,3,4,5]
        },
        {
          size: 15,
          type: 'leaf',
          list: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
        }
      ]
    }
  ]
}

console.log(getLeafContaining(tree, 22))

这似乎是正确的，但我无法确定.您如何稳健地实现这一目标?

It seems to be correct but I can't tell. How to you robustly implement this?

推荐答案

不，这是不正确的， index< = endSize 应该是 index<endSize .在最坏的情况下，这将导致一个空节点上的无限循环.

No, it's incorrect, index <= endSize should be index < endSize. In the worst case this would lead to an infinite loop on an empty node.

此外，递归解决方案比迭代版本要简单得多:

Also a recursive solution would have been much simpler than the iterative version:

const getLeafContaining = (tree, index) => {
  if (index < tree.size) {
    if (node.type == 'leaf') {
      return { node, index };
    } else if (node.type == 'container') {
      let before = 0
      for (const node of nodes) {
        const after = before + node.size;
        if (index < after) {
          return getLeafContaining(node, index - before);
        }
        before = after;
      }
    }
  }
  return { node: null, index: -1 }
}

之前总和的替代方法是减小 index :

An alternative to the accumulating before sum would be to decrement index:

      for (const node of nodes) {
        if (index < node.size) {
          return getLeafContaining(node, index);
        }
        index -= node.size;
      }

这篇关于当树节点具有子树大小时，如何按索引返回树节点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！