推 w181496: 主要是旋轉的部分要新增更新lsize的部分吧 不會影響原本 01/06 13:35
→ w181496: 複雜度 01/06 13:35
推 aa06697: 插入時往左走經過的點都+1 旋轉分四個case討論 把所有可 01/07 12:50
→ aa06697: 能列出來 01/07 12:50
Consider an AVL tree with n nodes,
(c) Now we add a field lsize to each node in the tree,
which records the number of nodes in its left subtree plus 1.
What is the time complexity to update such information during one insertion?
小弟有查到這是HorowitzC++聖經第二版 p. 578 7. 的習題
知道time complexity 是 O(log n) 但是不知道如何實作?
不知道有沒有大神願意分享自己的code
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.245.19
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483627972.A.43D.html