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

Question

给定固定数量的键或值(存储在数组或某些数据结构中)和b-tree的顺序,我们可以确定插入键的顺序,这将生成一个节省空间的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

位2最不经常更改,位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或红黑平衡树,也不应该调用重新平衡逻辑.

[ 编辑我刚刚意识到您不需要根据这些位反转值对数据进行排序,以便按顺序访问密钥.诀窍就是注意到位反转是它自己的反转.除了将键映射到位置之外,它还将位置映射到键.因此,如果从1..n循环,则可以使用此位反转值来决定下一个要插入的项目 - 对于第一个插入使用第4个项目,对于第二个插入使用第二个项目,依此类推.一个复杂因素 - 你必须将n向上舍入到小于2的幂(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树进行调整应该不会太难.

Answer 2

这就是我将元素添加到b-tree的方法.

感谢Steve314,给我一个二进制表示的开头,

给定n个元素按顺序添加.我们必须将它添加到m阶b树.取他们的索引(1 ... n)并将其转换为基数m.这种插入的主要思想是插入当前具有最高m-radix位的数字,并将其保持在树中添加的较小m-radix数之上,尽管节点分裂.

1,2,3 ..是索引,所以你实际插入他们指向的数字.

For example, order-4 tree
      4       8         12           highest radix bit numbers
1,2,3   5,6,7   9,10,11    13,14,15  

现在取决于订单中位数可以是:

• 顺序是 - >键的数量是奇数 - >中位数是中间(中位数)
• 顺序是奇数 - >键数是偶数 - >左中位数或右中位数

要提升的中位数(左/右)的选择将决定我应该插入元素的顺序.必须为b树修复此问题.

我在桶中添加元素到树.首先,我按顺序添加桶元素然后在完成下一个桶.如果中位数已知,铲斗尺寸为m级,则可以轻松创建铲斗.

I take left median for promotion. Choosing bucket for insertion.
    |  4     |  8      |   12       |    
1,2,|3   5,6,|7   9,10,|11    13,14,|15  
        3       2          1             Order to insert buckets.

• 对于左中位选择,我从右侧开始向树插入桶,对于右侧中间选择,我从左侧插入桶.选择左中位数我们首先插入中位数,然后首先插入左边的元素,然后插入数据库中剩余的数字.

例

Bucket median first
12,
Add elements to left
11,12,
Then after all elements inserted it looks like,
|   12       | 
|11    13,14,| 
Then I choose the bucket left to it. And repeat the same process.
Median
     12        
8,11    13,14, 
Add elements to left first
       12        
7,8,11    13,14, 
Adding rest
  8      |   12        
7   9,10,|11    13,14, 
Similarly keep adding all the numbers,
  4     |  8      |   12        
3   5,6,|7   9,10,|11    13,14, 
At the end add numbers left out from buckets.
    |  4     |  8      |   12       |   
1,2,|3   5,6,|7   9,10,|11    13,14,|15 

• 对于中间中位数(甚至是订单b树),您只需插入中位数,然后插入桶中的所有数字.

• 对于右中位数,我从左边添加桶.对于存储桶中的元素,我首先插入中位数然后插入右元素,然后插入左元素.

这里我们添加了最高的m-radix数,并且在此过程中我添加了具有直接较小的m-radix位的数字,确保最高的m-radix数保持在最高位置.这里我只有两个级别,对于更多级别,我按照基数位的降序重复相同的过程.

最后一种情况是当剩余的元素具有相同的基数位并且没有具有较小基数位的数字时,则只需插入它们并完成该过程.

我会给出一个3级的例子,但它显示的时间太长了.所以请尝试使用其他参数并告诉它是否有效.

Answer 3

不幸的是，所有树都会表现出最坏情况下的运行时间，并且当数据按这样的递增顺序输入时需要严格的平衡技术。二叉树很快就会变成链表等。

对于典型的 B 树用例（数据库、文件系统等），您通常可以指望数据自然地更加分布，从而生成更像第二个示例的树。

不过，如果这确实是一个问题，您可以对每个键进行哈希处理，以保证更广泛的值分布。

for( i=1; i<8; ++i )
    tree.push(hash(i));