作者GraffitiK (GraffitiK)
看板Grad-ProbAsk
標題[問題] 97中正一題AVL tree的問題
時間Wed Mar 25 16:00:06 2009
題目如下:
http://img207.imageshack.us/img207/7647/questionb.jpg
(a)小題我做出來是這樣:
http://img207.imageshack.us/img207/2903/36404634.jpg
想請問(b)小題, 刪去20後是像binary search tree的做法, 從左子樹最大者或右子樹最
小者上來頂替刪掉的node, 所以有兩種結果嗎?
http://img207.imageshack.us/img207/7677/43447802.jpg
那像上面第一種在node 8發生不平衡, 是屬於哪種不平衡? 8-35-28的RL不平衡還是
8-35-40的RR不平衡?
另外, (c)小題的時間複雜度, insert和delete都是O(log n)嗎?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.121.164.62
1F：推 s987692:a.跟你一樣 b.應該有兩種結果 c.logn 03/25 16:31
2F：→ GraffitiK:那請問(b)小題發生的不平衡該如何調整呢? 03/25 16:33
3F：推 s987692:我怎麼覺得都可以 = = 03/25 16:56
4F：推 greedbo:印象中AVL tree畫法很多種,除非題目要求作平衡才需要標平 03/25 17:18
5F：→ greedbo:衡係數 找最小值 03/25 17:18
6F：→ greedbo:最平衡 03/25 17:19