algorithm - 您应该以什么顺序将一组已知键插入 B 树以获得最小高度？

Question

给定固定数量的键或值(存储在数组或某些数据结构中)和 b 树的顺序，我们能否确定插入键的顺序以生成节省空间的 b 树。

为了说明，考虑 3 阶 b 树。令键为 {1,2,3,4,5,6,7}。按以下顺序向树中插入元素

for(int i=1 ;i<8; ++i)
{
 tree.push(i);  
}

会像这样创建一棵树

        4
     2      6
   1  3   5   7

参见 http://en.wikipedia.org/wiki/B-tree

但是这样插入元素

flag = true;
for(int i=1,j=7; i<8; ++i,--j)
{
    if(flag)
    {
        tree.push(i);
        flag = false;
    }
    else
    {
        tree.push(j);
        flag = true;
    }   
}

像这样创建一棵树

    3 5
1 2  4  6 7

我们可以看到水平下降的地方。

那么有没有一种特定的方法来确定插入顺序以减少空间消耗？

Answer 1

假设要插入的数据是整数 1..n，以下技巧应该适用于大多数有序搜索树。

考虑整数键的二进制表示 - 对于 1..7(用点表示零)这是......

Bit : 210
  1 : ..1
  2 : .1.
  3 : .11
  4 : 1..
  5 : 1.1
  6 : 11.
  7 : 111

Bit 2 变化最少，Bit 0 变化最频繁。这与我们想要的相反，所以如果我们反转这些位的顺序，然后按照这个位反转值的顺序对我们的键进行排序......

Bit : 210    Rev
  4 : 1.. -> ..1 : 1
  ------------------
  2 : .1. -> .1. : 2
  6 : 11. -> .11 : 3
  ------------------
  1 : ..1 -> 1.. : 4
  5 : 1.1 -> 1.1 : 5
  3 : .11 -> 11. : 6
  7 : 111 -> 111 : 7

用不平衡的二叉搜索树来解释这一点是最简单的，它通过添加叶子来增长。第一项是死点——这正是我们想要的根项。然后我们添加下一层的键。最后，我们添加叶层。在每一步，树都是尽可能平衡的，所以即使你碰巧正在构建一个 AVL 或红黑平衡树，也不应该调用重新平衡逻辑。

[编辑 我刚刚意识到您不需要根据那些位反转值对数据进行排序以按该顺序访问 key 。这样做的诀窍是注意位反转是它自己的反转。除了将键映射到位置，它还将位置映射到键。因此，如果您从 1..n 开始循环，您可以使用这个位反转值来决定下一个要插入的项目 - 第一个插入使用第 4 个项目，第二个插入使用第二个项目，依此类推。一个并发症 - 你必须将 n 向上舍入到小于二的幂(7 是可以的，但使用 15 而不是 8)并且你必须边界检查位反转值。原因是位反转可以将一些入界位置移出界外，反之亦然。]

实际上，对于红黑树一些重新平衡逻辑将被调用，但它应该只是重新着色节点 - 而不是重新排列它们。但是，我没有仔细检查过，所以不要依赖这个说法。

对于B树来说，树的高度是通过增加一个新的根来增长的。因此，要证明它的有效性有点尴尬(而且它可能需要比 B 树通常需要更仔细的节点拆分)，但基本思想是相同的。尽管会发生重新平衡，但由于插入的顺序，它会以平衡的方式发生。

这可以推广到任何一组预先已知的键，因为一旦对键进行排序，您就可以根据该排序顺序分配合适的索引。

---

警告 - 这不是从已知的已排序数据构建完美平衡树的有效方法。

如果您的数据已经排序，并且知道它的大小，您可以在 O(n) 时间内构建一个完美平衡的树。这是一些伪代码...

if size is zero, return null
from the size, decide which index should be the (subtree) root
recurse for the left subtree, giving that index as the size (assuming 0 is a valid index)
take the next item to build the (subtree) root
recurse for the right subtree, giving (size - (index + 1)) as the size
add the left and right subtree results as the child pointers
return the new (subtree) root

基本上，这根据大小决定树的结构并遍历该结构，沿途构建实际节点。适应 B 树应该不会太难。