我们能在没有递归关系公式的情况下找到计算AVL树中最小节点数的广义公式吗?因为当我们必须在高度为1000的AVL树上找到最小节点数时,它会失败,因为在纸上求解需要很长时间?
这是一个绘制图片和寻找图案的好地方。
以下是高度为0和1的最小AVL树:
*
*
|
*
高度为2的最小AVL树将通过使用高度为0和1的树来制作(如果使用高度为1和1,则可以通过使用高度0和1来提高节点数量(,最小的选项是
*
/
* *
|
*
然后,高度为3的最小树将使用高度为1和2的树,看起来如下:
*
/
* *
| /
* * *
|
*
更一般地说,高度为k的最小树,其中k≥2是通过取高度为k-1和k-2的两个最小树并将它们与根处的新节点连接在一起而给出的。
这给出了一个递推关系:
T(n(=T(n-1(+T(n-2(+1
T(0(=1
T(1(=2
迭代此重复出现以下模式:
h = 0 1 2 3 4 5 6 7 8
1 2 4 7 12 20 33 54 88
接下来你可以做几件事:
- 你能写一些代码来评估n值越来越大的递归关系吗?这可能会给你一个直接计算你需要的数字的函数
- 递推T(n(=T(n-2(+T(n-1(+1看起来是一个批次,类似于Fibonacci递推F(n(=F(n-2。你看到T(n(数和斐波那契序列之间有什么关系吗?这可能会让你直接计算出答案
希望这能有所帮助!