javascript - 如何使用树旋转防止 n 叉树的深分支？

问题描述

我试图想象一个树型系统，其中你有树节点，它可以有 2 个节点的权力，每个节点最多 32 个节点。数据存储在“叶子”中，叶子同样被捆绑成 2 到 32 个节点的幂。我在想的是insert，如果叶节点是 32 个节点，那么你将它分成两半，将这两半添加到新的父节点，然后将其添加到树中。问题是，如果你继续在同一个地方插入，我会看到这种树出现，它一遍又一遍地分裂同一个地方，导致一个很深的分支，因为每个叶子达到 32 个项目。

如果每个叶子节点每个代表最多 32 个项目，并且每个内部容器节点最多可以包含 32 个子容器/叶子，我该如何使用旋转来平衡这棵树？问题是我不知道最终的树会是什么样子，所以我不知道旋转应该如何工作。我试着想象它，但没有到达那里。

动画树旋转都是非常基本的，并没有展示如何在非二叉树上进行。

由于节点最多可以有 32 个节点，一个深度嵌套的树最终应该看起来像这样（比如说第一层我实际上画了 32 个节点，所以它是满的）：

我不确定它应该是什么样子，这就是这个问题的原因。但是当您在树中插入节点时，事物应该以某种方式旋转，因此它不会像上面那样得到长分支，但是每个节点最多可以有 32 个子节点（如果它们是叶子类型，则可以有对象/项目）。这是可能吗？如果是这样，如何实现旋转以像 BST 一样保持这个 n 叉树“平衡”的一些 JavaScript 是什么？

边注。我正在尝试修改轮换方案，但并没有走得太远。

// split()
// rotate() // shift

const createTree = () => createTreeLeaf()

const createTreeContainer = () => {
  return {
    type: 'container',
    list: [],
    size: 0
  }
}

const createTreeLeaf = () => {
  return {
    type: 'leaf',
    list: [],
    size: 0
  }
}

const insertAt = (tree, index, item) => {
  if (tree.size == 0) {
    tree.list.push(item)
    tree.size++
    return tree
  }
  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 (node.size == 32) {
            const firstHalf = node.list.splice(0, 16)
            const secondHalf = node.list.splice(-16)
            const container = createTreeContainer()
            const aNode = createTreeLeaf()
            aNode.list.push(...firstHalf)
            aNode.size = 16
            const bNode = createTreeLeaf()
            bNode.list.push(...secondHalf)
            bNode.size = 16
            container.list.push(aNode, bNode)
            container.size = 32
            container.parent = node.parent
            node.type = container.type
            node.list = container.list
            node.size = container.size
            i--
            continue
          } else if (node.size && relativeIndex > node.size - 1) {
            let newArray = new Array(node.size * 2)
            node.list.forEach((x, i) => newArray[i] = x)
            node.list = newArray
          }
          let j = node.size
          while (j > relativeIndex) {
            node.list[j] = node.list[j - 1]
            j--
          }
          node.list[relativeIndex] = item
          node.size++
          break a
        }
      }
    }
  }
}

let tree = createTree()

for (let i = 1, n = 2000; i <= n; i++) {
  insertAt(tree, 0, i)
}
console.log(JSON.stringify(tree))

目前以一棵深树结束，不确定如何实现这种旋转。

如果还有使用旋转的替代方法可以创建平衡树，那也是一个合适的答案。

标签： javascriptarraysalgorithmtreebinary-search-tree

解决方案

您尝试做的与自平衡二叉搜索树相同，但不仅限于最多 2 个孩子。您可以直接从B-Tree或B+ Tree获取帮助。

B树插入说

所有插入都从叶节点开始。要插入新元素，请搜索树以找到应添加新元素的叶节点。使用以下步骤将新元素插入该节点：

如果节点包含的元素少于允许的最大数量，则有空间容纳新元素。在节点中插入新元素，保持节点的元素有序。

否则节点已满，将其平均分成两个节点，因此：

从叶子的元素和新元素中选择一个中值。

小于中值的值被放入新的左节点，大于中值的值被放入新的右节点，中值作为分隔值。

分隔值插入到节点的父节点中，这可能导致它被拆分，等等。如果节点没有父节点（即该节点是根节点），则在该节点之上创建一个新根节点（增加树的高度）。

这显示了如何拆分而不是旋转树。

上面与 B-Tree 插入相关的摘录是算法中的一种伪代码/广泛的步骤。与其添加更多的伪代码，不如让我从这里进行一个模拟来解释插入操作。同样的链接也有代码。

让我们用一个最多有 3 个子节点的示例树来理解该算法，并且同一个节点可以保存 5 个键。考虑一个初始为空的 B 树中的整数序列 10、20、30、40、50、60、70、80 和 90。

最初根为 NULL。让我们先插入 10。