作者YOAOY (最强弱者)
看板Grad-ProbAsk
标题[理工] 100 台大电机 资结
时间Tue Sep 11 18:07:21 2018
https://i.imgur.com/jhukrZm.jpg
请问题目说随意binary tree
那我假设为BST
(1.)考虑left skewed BST (worst case)
插入新节点，必须插入在最後一个节点的左边
在利用in order 追踪
可得到时间复杂度为O(n)
所以选项选（A)
(2.)考虑 complete BST
假设best case
插入新节点，可得时间复杂度为O(logn)
这时後选项选(B)
最後解答给（A)
请问为什麽（B)选项不能选呢？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 115.82.178.189
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1536660444.A.D06.html
1F：推 wilson50101: 我觉得有可能会到O(h)的可能性09/11 19:12
2F：→ wilson50101: 所以选B不够严谨09/11 19:12
原来如此，我没考虑到严谨的问题，感谢！
※ 编辑: YOAOY (115.82.178.189), 09/11/2018 19:23:33