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

Question

我是 trying to imagine a ，您的树节点可以具有 2 个节点的幂，每个节点最多 32 个节点。数据存储在“叶子”中，叶子同样被捆绑成 2 的幂，最多 32 个节点。我在想的是，在 insert 上，如果叶节点是 32 个节点，那么你 将它分成两半 ，将这两半添加到一个新的 parent，并将其添加到树中。问题是，如果你一直在同一个地方插入，我可以看到这种树出现，它一遍又一遍地分裂同一个地方，导致一个深分支，因为每个叶子达到 32 个项目。

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

动画树旋转都是非常基本的，没有显示如何在 non-binary 树上进行旋转。

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

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

旁注。我正在尝试修改轮换方案，但没有取得太大进展。

// 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))

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

如果除了使用旋转之外还有其他方法可以创建平衡树，那也是一个合适的答案。

Answer 1

您要执行的操作与 self-balancing binary search trees but not limited to just max 2 children. You can directly take help from B-Tree or B+ Tree 相同。

B-Tree Insertion 说

All insertions start at a leaf node. To insert a new element, search the tree to find the leaf node where the new element should be added. Insert the new element into that node with the following steps:

If the node contains fewer than the maximum allowed number of elements, then there is room for the new element. Insert the new element in the node, keeping the node's elements ordered.

Otherwise the node is full, evenly split it into two nodes so:

A single median is chosen from among the leaf's elements and the new element.

Values less than the median are put in the new left node and values greater than the median are put in the new right node, with the median acting as a separation value.

The separation value is inserted in the node's parent, which may cause it to be split, and so on. If the node has no parent (i.e., the node was the root), create a new root above this node (increasing the height of the tree).

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

以上与 B-Tree 插入相关的摘录是算法中的一种 pseudo-code/broad 步骤。我不再添加更多 pseudo-code，而是从 here 中进行模拟来解释插入操作。同样link也有代码

让我们用一个最多有 3 children 并且同一个节点可以容纳 5 个键的示例树来理解该算法。考虑初始为空的 B-Tree.

中的整数序列 10、20、30、40、50、60、70、80 和 90

初始根为空。让我们先插入 10.

现在让我们插入20、30、40和50。它们都会被插入到root中，因为一个节点最多可以容纳5个键。

我们现在插入60，因为根节点已经满了，所以会先分裂成两个，然后把60插入到合适的child.

现在让我们插入 70 和 80。这些新键将被插入到适当的叶子中，而不进行任何拆分。

现在让我们插入90。这个插入会导致分裂。中间的键会上升到 parent.

希望对您有所帮助！

随时play around with this B-Tree Visualization!

更不用说，您总能在互联网上找到 javascript B-Tree 的实现，例如this one.

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

How to prevent deep branch of an n-ary tree using tree rotation?

javascript

arrays

algorithm

tree

binary-search-tree