该书说，插入二叉搜索树的最差运行时间是n ^ 2
我真的不明白 .
我的意思是如果你有1,2,3,4,5,6,7,8,9
这是最坏的情况，是不是最坏的情况下运行时间是O（n）？
（如果值<node.data，则转到左侧，如果> node.data右转）
谁能解释一下？我真的很感激！
我想我现在得到了答案！因为您需要返回以查找新数字从一开始是更大还是更小 .
但是现在我还有另一个问题，那就是构建AVL树的最坏情况？
这本书说二元搜索树的构建和排序是n（log n）
AVL树的最差深度是log n
它从未说过整个AVL树的插入时间是什么 .
有谁知道？
2 回答
它不是
O(n)，因为在每次插入时，您需要遍历整个树以找到放置新节点的合适位置 .例如，首先在节点的头部放置1 . 然后，要放置2，您需要查看头部的1并决定将2添加到头部右侧 . 然后，当添加3时，您需要再次查看该1，然后决定向右移动，然后查看2并将3放在2的右侧节点上 .
所以基本上，每个最坏情况插入都是
O(k)（其中k是树中已有的数字元素） . 要构建树，您需要进行n次插入，因此整个操作需要1+2+3+4+5+6...+n操作O(n^2/2)- >O(n^2).首先，AVL树的深度：
设N（h）表示否 . 高度为h的AVL树中的节点数 .
N（h）> = 1 N（h-1）N（h-2），这来自AVL树的定义 .
N（h）> = F（h）-1，其中F（h）是Fibonacci no .
N（h）> = {（1 sqrt（5）/ 2} ^ h，
因此h <= log（基数=（1 sqrt（5））/ 2）n .
所以h <= c logn . 基= 2;`
现在看看上面的输入我们要插入1,2,3，...，n .
现在轮换将在恒定的时间内进行 .
每插入两个元素后，就会发生一次旋转 . 所以没有旋转= n / 2 .
每次我们需要进行logm比较，其中logm是当前的高度 .
因此总操作= c（log 1 log 2 log 3 log 4 .... log n-1）n / 2
它等于c（log（n-1）！）n / 2
<= c（nlogn）n / 2，这只是O（nlogn） .
PS：logn意味着2的基数 .