N'Ary树数据结构

Question

N'Ary树数据结构

我正在寻找大量的树数据结构,这真的令人困惑.就像我理解基本的二进制树(也是它的众多实现,如BST红黑树等)但我真正需要的是关于N'ary树的一些信息.我需要研究各种类型的N'ary树以及它们的性能比较.我见过的唯一N'ary树是B +树.我需要知道哪棵是最快的N'Ary树.即最明智的时间复杂度,空间复杂性是没有问题的.

Answer 1

Rea*_*law 6

一般来说,做一些K-ary树, $ k> 2 $ ,没有给出二叉树的任何渐近优势( $ K = 2 $ ).例如,搜索AA平衡二叉树可以完成 $\mathcal O\left(log_2 \n\right)$ 时间.搜索平衡的k-ary树,会给你 $\mathcal O\left(k\cdot log_k \n\right)$ .假设 $ķ$ 是一个常数, $ 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-ary树可能会产生更好的内存访问模式,因为每个节点都包含 $ķ$ 彼此相邻的节点,这意味着树的高度更短(维基百科给出了高度, $ H $ ,一个完整的k元树作为 $h =\left\lceil\log_k(k - 1)+\log_k(n) - 1\right\rceil$ ,对于任何常数渐近相同 $ķ$ 因为叶子节点可以包含多个有序键,因此遍历可能会跳得更少.

归档时间：	13 年，2 月前
查看次数：	3917 次
最近记录：	13 年，1 月前