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

Question

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

我试着用inf \ sup阻止它，但是我不能再走得更远了，那么2-3树中的节点数量就会大于完整AVL树中的节点数量。

预先感谢

Answer 1

在wikipedia 2-3树的定义下操作：

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

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

如果在这棵树上有n树叶，那么树的高度为height = log3(n)（n的对数基数为3），因此最大物品数量为3^height。

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