data-structures - N 元树数据结构

<分区>

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

最佳答案

一般来说，制作 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$ 和 $log n$ 对于任何其他基数，渐近等价(增长率速率对于大 $n$ 是相同的)。即 $\mathcal O \left(log_i \ n\right)$ 相当于 $\mathcal O \left(log_j \ n\right)$ 对于任何 $i$ 和 $j$ .因此， $\mathcal O \left(k\cdot log_k \ n\right) =\ $\mathcal O \left(log \ n\right)$ .

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

关于data-structures - N 元树数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12269700/

上一篇：sql-server-2008 - 我们可以在 sql server 中使用动态 group by 子句吗？

下一篇：ruby-on-rails-3 - Rails 3 Rspec 2 问题与 :locale and RESTfull path

相关文章：

c - 简单和双指针公式

c - 从 C 二叉树中删除节点而不弄乱它

c - 为什么我的数据结构堆排序会在 5761 个数字处中断进行排序？

c++ - 范围最小值/最大值查询

algorithm - 检查是否可以快速用给定的字母组成单词

algorithm - 解释为什么插入(以及不同的情况)不会改变红黑树的黑色高度

c++ - 需要通过函数指针访问类对象 - 二叉搜索树类创建相关

algorithm - 桶的索引计数

python - 用于存储排序字段以有效允许修改的数据结构

java - 如何遍历二叉树？