鉴于键或值（存储一些数据结构或者在阵列或在），并顺序b树的固定数目，我们能确定插入钥匙，将产生一个空间高效B树的序列。

要说明这一点，考虑顺序3.让键为{1,2,3,4,5,6,7} b树。插入元素树依照以下的顺序

 的for（int i = 1; I＆LT; 8; ++ I）
{
 tree.push（ⅰ）;
}
 

将创建一个这样的树

  4
     2 6
   1 3 5 7
 

看 http://en.wikipedia.org/wiki/B-tree

但这种方式插入元素

 标志= TRUE;
的for（int i = 1，J = 7; I＆LT; 8; ++我， -  J）
{
    如果（旗）
    {
        tree.push（ⅰ）;
        标志= FALSE;
    }
    其他
    {
        tree.push（J）;
        标志=真正的;
    }
}
 

创建一个像这样的树

  3 5
1 2 4 6 7
 

在这里我们可以看到有下降的水平。

那么，有没有一种特定的方式来确定插入序列将减少空间占用？

下面的技巧应该适用于大多数下令查找树，假设数据插入都是整数 1..1 。

考虑您的整数键的二重presentation - 为1..7（用点的零），这是......

 位：210
  1：..1
  2：0.1。
  3：0.11
  4：1 ..
  5：1.1
  6：11。
  7：111
 

2位的变化最少的方式，位0的变化最多。这就是我们所希望的相反的，所以如果我们扭转这些位的顺序，那么我们的钥匙，以便该位反转值排序...

 位：210启
  4：1。 - ＆GT; ..1：1
  ------------------
  2：0.1。 - ＆GT; 0.1。 ：2
  6：11  - ＆GT; 0.11：3
  ------------------
  1：..1  - ＆GT; 1 ..：4
  5：1.1  - ＆GT; 1.1：5
  3：0.11  - ＆GT; 11：6
  7：111  - ＆GT; 111：7
 

这是最简单的解释在不平衡的二叉搜索树而言，通过添加叶子增长。第一项是死点 - 这正是我们想要的根目录下的项目。然后，我们对下一层添加的键。最后，我们添加了叶层。在每一步，树是平衡，因为它可以，所以即使你碰巧要建立一个AVL或红黑树的平衡，再平衡的逻辑永远不应该被调用。

[修改我才意识到，你不需要为了获得钥匙的顺序根据这些位反转值对数据进行排序。的诀窍是，以通知该位反转是它自己的倒数。除了映射键的位置，将其映射持仓键。所以，如果你从1..N遍历，您可以使用该位反转值来决定下一个要插入的项目 - 首插入使用第4项，第二插入使用第二个项目，依此类推。一个复杂 - 你必须到n向上舍一小于二的幂（7是确定的，但使用15而不是8），你必须边界检查位反转值。其原因是位反转可以将部分在界位置外的界限，反之亦然。]

其实，对于红黑树的部分的再平衡逻辑将被调用，但它应该只是重新着色节点 - 而不是重新排列。但是，我还没有仔细检查了，所以不要依赖这一说法。

对于B树，树的高度增加，加入一个新的根。证明这一点的工作，因此，有些别扭（它可能需要更仔细的节点分离比B +树通常需要），但其基本思想是一致的。虽然再平衡发生​​时，它发生在一种平衡的方式，因为刀片的顺序的

这可以概括为任何一组已知的前移键，因为一旦密钥被排序，你可以基于该排序顺序分配合适的索引。

警告 - 这是不是从已知的已排序的数据构建一个完美的平衡树的有效途径

如果你有你的数据已经排序，并知道它的大小，你可以建立在O（n）时间完全平衡树。下面是一些伪code ...

 如果大小是零，则返回null
从尺寸，决定哪些指标应该是（子树）根
递归为左子树，赋予该指数随大小（假设0是有效的索引）
采取的下一个项目建（子树）根
递归为右子树，得到（大小 - （索引+ 1））作为大小
添加左和右子树结果作为孩子指针
返回的新（子树）根
 

基本上，此决定基于所述大小的树的结构和穿过该结构，建筑沿途的实际节点。它不应该太硬去适应它对于B-树。

Given a fixed number of keys or values(stored either in array or in some data structure) and order of b-tree, can we determine the sequence of inserting keys that would generate a space efficient b-tree.

To illustrate, consider b-tree of order 3. Let the keys be {1,2,3,4,5,6,7}. Inserting elements into tree in the following order

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

would create a tree like this

        4
     2      6
   1  3   5   7

see http://en.wikipedia.org/wiki/B-tree

But inserting elements in this way

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

creates a tree like this

    3 5
1 2  4  6 7

where we can see there is decrease in level.

So is there a particular way to determine sequence of insertion which would reduce space consumption?

The following trick should work for most ordered search trees, assuming the data to insert are the integers 1..n.

Consider the binary representation of your integer keys - for 1..7 (with dots for zeros) that's...

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

Bit 2 changes least often, Bit 0 changes most often. That's the opposite of what we want, so what if we reverse the order of those bits, then sort our keys in order of this bit-reversed value...

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

It's easiest to explain this in terms of an unbalanced binary search tree, growing by adding leaves. The first item is dead centre - it's exactly the item we want for the root. Then we add the keys for the next layer down. Finally, we add the leaf layer. At every step, the tree is as balanced as it can be, so even if you happen to be building an AVL or red-black balanced tree, the rebalancing logic should never be invoked.

[EDIT I just realised you don't need to sort the data based on those bit-reversed values in order to access the keys in that order. The trick to that is to notice that bit-reversing is its own inverse. As well as mapping keys to positions, it maps positions to keys. So if you loop through from 1..n, you can use this bit-reversed value to decide which item to insert next - for the first insert use the 4th item, for the second insert use the second item and so on. One complication - you have to round n upwards to one less than a power of two (7 is OK, but use 15 instead of 8) and you have to bounds-check the bit-reversed values. The reason is that bit-reversing can move some in-bounds positions out-of-bounds and visa versa.]

Actually, for a red-black tree some rebalancing logic will be invoked, but it should just be re-colouring nodes - not rearranging them. However, I haven't double checked, so don't rely on this claim.

For a B tree, the height of the tree grows by adding a new root. Proving this works is, therefore, a little awkward (and it may require a more careful node-splitting than a B tree normally requires) but the basic idea is the same. Although rebalancing occurs, it occurs in a balanced way because of the order of inserts.

This can be generalised for any set of known-in-advance keys because, once the keys are sorted, you can assign suitable indexes based on that sorted order.

WARNING - This isn't an efficient way to construct a perfectly balanced tree from known already-sorted data.

If you have your data already sorted, and know it's size, you can build a perfectly balanced tree in O(n) time. Here's some pseudocode...

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

Basically, this decides the structure of the tree based on the size and traverses that structure, building the actual nodes along the way. It shouldn't be too hard to adapt it for B Trees.