data-structures - 2-3 树中的最小和最大节点数

Question

我试图找出具有 n 个叶子的 2-3 树中的最小和最大节点数是多少。

我试过用 inf\sup 阻止它，但我不能更进一步，2-3 树中的节点数大于完整 AVL 树中的节点数。

提前致谢

Answer 1

在wikipedia上根据 2-3 树的定义进行操作：

在计算机科学中，2-3 树是一种数据结构，其中每个具有子节点（内部节点）的节点都有两个子节点（2 节点）和一个数据元素，或者三个子节点（3 节点）和两个数据元素。树外部的节点（叶节点）没有子节点和一两个数据元素。

在我看来，树中的最大节点数将是每个内部节点有 3 个子节点时。为了找到该树中的最大节点数，我们必须首先找到树的高度。

如果这 3 棵树中有n叶子，则树的高度为height = log3(n)(log base 3 of n)，因此最大项目数为3^height。

最小的树是具有最少元素数量的树，它将是具有单个节点的树。