N'Ary树数据结构

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

来源

2012-09-04 mihirk

作为一棵具有给定数量的子节点（> 1）的节点本身没有多大意义。从这个角度来看，真的很少有人能分辨出一棵树。时间复杂度主要取决于您在其上运行的算法以及施加于树上的不变量，然后可以由算法利用这些不变量。对于自平衡树木，B +树木和所有其他树木而言，情况确实如此。请澄清你的问题，因为它对我来说毫无意义。 – delnan

一般来说，做的东西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$ 相同）。也就是说，对于任何 $i$ 和 $j$ ， $\mathcal O \left(log_i \ n\right)$ 相当于 $\mathcal O \left(log_j \ n\right)$ 。因此， $\mathcal O \left(k\cdot log_k \ n\right) =\ $\mathcal O \left(log \ n\right)$ 。

然而，实际上，一个k元树可能导致更好的存储器访问模式，因为每个节点包含 $k$ 节点旁边的海誓山盟，这意味着树的高度更短（维基百科给出了高度， $h$ ，对于完整的k叉树为 $h=\left\lceil\log_k (k - 1) + \log_k (n) - 1\right\rceil$ ，对于任何常量 $k$ ，它渐近地相同），并且遍历可能跳得更少，因为叶节点可以包含多个有序键。

来源

2012-09-09 09:19:13

N'Ary树数据结构

回答

相关问题