2

我正在查看大量的树数据结构，这确实令人困惑。就像我了解基本的二叉树（还有它的众多实现，如 BST 红黑树等）但我真正需要的是一些关于 N'ary 树的信息。我需要研究各种类型的 N'ary 树以及它们的性能比较。到目前为止，我看到的唯一 N' ary 树是 B+ 树。我需要知道哪个是最快的 N'Ary 树。即最优化的时间复杂度，空间复杂度不是问题。

4

1 回答 1

7

通常，将某事物制作为K -ary树$k > 2$不会比二叉树( $k=2$) 提供任何渐近优势。例如，搜索平衡的二叉树可以及时完成$\mathcal O \left(log_2 \ n\right)$。搜索一个平衡的k-ary树，会给你$\mathcal O \left(k\cdot log_k \ n\right)$。假设$k$是一个常数，$log_k n$并且$日志n$对于任何其他基数，都渐近等效（对于 large ，增长率将是相同的$n$）。即，$\mathcal O \left(log_i \ n\right)$等价$\mathcal O \left(log_j \ n\right)$于任何$i$and $j$。因此，$\mathcal O \left(k\cdot log_k \ n\right) =\ $\mathcal O \left(log \ n\right)$。

然而，实际上，k-ary 树可能会导致更好的内存访问模式，因为每个节点都包含彼此相邻$k$的节点，这意味着树的高度更短（维基百科给出$h$了完整k-ary 树的高度 ,为$h=\left\lceil\log_k (k - 1) + \log_k (n) - 1\right\rceil$，这对于任何常数都是渐近相同的$k$），并且遍历也可能跳得更少，因为叶节点可以包含多个有序键。

于 2012-09-09T09:19:13.153 回答