2-3树的最小和最大节点数
2-3树的最小和最大节点数
提问于 2014-05-06 19:53:50
我试图找出有n个叶子的2-3棵树的最小和最大节点数是多少。
我尝试过用inf\sup来阻止它，但是我不能更进一步，即2-3树中的节点数比全AVL树中的节点数要大。
提前感谢
回答 1
Stack Overflow用户
发布于 2014-05-06 20:05:12
在维基百科中根据2-3树的定义进行操作。
在计算机科学中，2-3树是一种数据结构，每一个有子节点(内部节点)的节点都有两个子节点(两个节点)和一个数据元素，或者有三个子节点(三个节点)和两个数据元素。树外部的节点(叶节点)没有子节点和一个或两个数据元素。
在我看来，树中的最大节点数将是当每个内部节点有3个子节点时。为了找到树中的最大节点数，我们必须首先找到树的高度。
如果这3棵树中有n叶，那么树的高度是height = log3(n) (LogBase3ofn)，所以最大的条目数是3^height。
最小的树是一个元素数最少的树，它是一个有一个节点的树。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/23503750
复制相关文章
相似问题
腾讯云开发者
