[理工] 95中正资结 TampaBayRays PTT批踢踢实业坊

楼主: TampaBayRays (光芒今年拿冠军) 2017-07-23 22:06:48

http://i.imgur.com/joHuaMF.jpg
binary tree的search 感觉应该是(1+2+...+n)/n=O(n)?
解答的说法应该是binary search tree?
感谢各位大大回答！

作者: brilliantl (brilliant) 2017-07-23 22:43:00

楼主: TampaBayRays (光芒今年拿冠军) 2017-07-23 22:46:00

感谢楼上，不过这个是binaray search tree，题目说search in a binary tree应该是指在binary tree搜寻而不是在binary search tree搜寻？

作者: sarsman (DeNT15T♠) 2017-07-23 22:54:00

感觉是少打Search

楼主: TampaBayRays (光芒今年拿冠军) 2017-07-23 23:22:00

不过我刚刚有去查考古题，真的是写binary tree，所以是中正教授打错吗XD

作者: hodo (hodo) 2017-07-24 09:26:00

高度平衡下就等于在算2T(n/2)+1吧？

楼主: TampaBayRays (光芒今年拿冠军) 2017-07-24 20:58:00

楼上你说的是binary search tree 吧？

作者: brilliantl (brilliant) 2017-07-25 10:50:00

Binary tree 有分好几种，search最慢的情况是每个node都找过一次，最快的是complete BT那种只要O(lgn)就可以找到

楼主: TampaBayRays (光芒今年拿冠军) 2017-07-25 12:08:00

继续阅读