问

基数树的空间复杂度是多少？

平凡小迪发布于 2023-02-10 15:41

linux

tree

搜索

byte

我一直关注基数树的空间使用,但我没有找到任何有用的讨论.

现在假设我们有一个与linux radix-tree.c相同的基数树实现,它接受一个整数并使用每6位来索引树中的下一个位置.我可以很容易地想到基数树的空间使用远远超过二叉搜索树的情况.如果我错了,请纠正我:

使用案例:(0,1,1,1,1),(1,1,1,1,1),(2,1,1,1,1),......(63,1,1,1) ,1).

这里只是为了方便起见,我使用(a,b,c,d,e)来表示一个30位整数键,每个元素代表一个6位值.a是MSB,e是LSB.

基数树:

对于这个用例,基数树的高度为5,每个密钥将占用4个独立的节点,因为它们位于根的不同子树上.所以会有((5-1)*64 + 1)= 257个节点.

每个节点包含2 ^ 6 = 64个指针,因此它将使用257*64*4Byte = 65KB

二叉搜索树

我们只关心有多少钥匙.在这种情况下,它有64个键.

假设每个BST节点每个节点使用3个指针,它将使用64*3*4Byte = 768字节.

对照

看起来基数树空间效率很低.在给定相同数量的节点的情况下,它比二叉搜索树使用~100倍的空间!我不明白为什么它甚至在linux内核中使用.

我错过了什么吗？谢谢.

1 个回答

你要求空间复杂性,所以让我们解决它.

如果我们认为叶子上的非空指针是感兴趣的值,那么通过矛盾证明最坏的情况是完全填充的树,每个叶节点具有一个值,这并不难.

如果分支是N路(在您的用例64中)并且高度是H(在您的用例5中),则此树中存在N ^(H-1)个叶节点,存储相同数量的值.节点总数是
```
1 + N + N^2 + ... N^(H-1) = (N^H - 1) / (N-1)
```
因此,用指针测量的存储要求是此数量的N倍.
```
(N^H - 1)  [N / (N-1)]  
```
这产生了存储效率
```
(N^H - 1)  [N / (N-1)]  
--------------------
       N^(H-1)
```
这是指针的总数除以有效数据指针的数量.

随着N变大,这接近N.在您的示例用例中,它实际上是65.01(对于N = 64).所以我们可以说存储复杂度是O(NV),其中V是要存储的数据值的数量.

虽然我们在这里进行了第一原理分析,但它完全有道理.整个树的叶级存储占据了其余部分的近N倍.该存储的大小是NV.

当然,像这样具有巨大分支因子的树(例如数据库中的B树)的优点是需要更少的节点遍历才能到达正确的叶子.

此外,当每个遍历是基数树中的单个数组查找时,您无法获得更快的速度.

在您的使用案例中,一个完美平衡的二进制搜索树需要最多30次比较,并伴随分支刷新管道.与5个数组索引操作相比,这可能要慢得多.数组索引往往比比较快,因为它是非分支代码.但即使它们是相同的,二叉树也只需要2 ^ 5 = 32个元素来引起与包含2 ^ 30个元素的基数树相同数量的索引工作.

为了概括这一点,如果密钥比较和数组索引操作具有相同的成本,则2 ^ H元素的二叉树将需要与能够保持N ^(H-1)元素的索引树相同的查找工作量.

正如其他人所说,如果树的顶层的索引位倾向于几个公共前缀(即它们是相同VM空间的地址的顶部位),则不会发生基数树的最坏情况存储行为.
2023-02-10 15:42 回答

花谢五月天

撰写答案

今天，你开发时遇到什么问题呢？

立即提问

热门标签