查找具有n个节点的可能AVL树的数量的公式 [英] Formula for finding number of possible AVL trees with n nodes

问题描述

让节点数为3。


如果a，b，c ..按c> a> b的顺序排列，则可能的avl树为：
n = 1表示1，n = 2表示2 ..（查看图片）

对于BST，我们知道它是2n C n /（n + 1）。
有人试图推导一个公式，该公式可以找到avl树的数量。给出了个节点。

示例问题：具有11个节点的可能的avl树的数量是多少？

As we know for a BST it is 2n C n/ (n+1).
Have anyone tried to deduce a formula that can find the number of avl trees when the number of nodes are given.
example question:what is the number of possible avl trees with 11 nodes?

推荐答案

我怀疑存在简单的公式。但是您可以通过动态编程找到2个可能的AVL树，填充2D表，其中n是节点数，h是树高，然后将所有非零n节点项求和：

I doubt that simple formula exists. But you can find number of possible AVL trees with dynamic programming, filling 2D table, where n is number of nodes, h is tree height, then sum all non-zero n-nodes entries:

F(n, h) = Sum[by all possible i]{F(i,h-1)*F(n-1-i,h-1)} + 
          Sum[by all possible j]{F(j,h-1)*F(n-1-j,h-2)} + 
          Sum[by all possible k]{F(k,h-2)*F(n-1-k,h-1)} 

说明：我们可以制作n个节点的h-高度AVL树，将根节点与两个相同高度的有效树（h-1）或（h-1）和（h-2）树或（h- 2）和（h-1）树。

Explanation: we can make n-nodes h-height AVL tree, connecting root node with two valid trees of equal height (h-1), or with (h-1) and (h-2) trees, or with (h-2) and (h-1) trees.

这篇关于查找具有n个节点的可能AVL树的数量的公式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！