1
「高度爲h的avl樹的最小節點數」的公式爲遞歸： n（0）= 1，n（1）= 2 n（h） = 1 + N（H-1）+ N（H-2）將N個元素添加到空AVL樹中的運行時間
在另一方面，我發現這在互聯網用於添加N元素到一個空的AVL樹的複雜性的解釋：
Well, imagine the tree being built.
One by one, the elements go through the tree nodes, and chose their abode by taking either a left or a right. The tree balances itself every time the heights are too skewed.
Of course, the cost of balancing the tree is an O(1) operation, so I do not consider that in the complexity analysis.
Complexity: log(1)+log(2)+log(3)+....+log(n)
=log(n!)
=O(nlogn-n+O(log(n)))
=O(nlogn)
但這裏是我不明白，爲什麼計算日誌（n！）如果不是每次我添加一個元素的高度增加？因爲提出的遞歸公式適用於一個大的N，只有在很多元素之後，avl的高度纔會增加，所以漸近地說它不應該好於log（n！）？
另外，這是什麼情況呢？在這種複雜情況下是否有更糟的情況和最好的情況？例如，假設我添加了特定的N個元素，對於不同的運行可以有更好的運行時間嗎？或者我可以說，從高級知道哪些元素將被添加，因此運行時間是有限的？