[問題] 97中正一題AVL tree的問題

看板Grad-ProbAsk作者GraffitiK (GraffitiK)時間16年前 (2009/03/25 16:00)推噓3(3推 0噓 3→)

留言6則, 3人參與討論串1/1

題目如下: 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

推

s987692

03/25 16:31, , 1^F

03/25 16:31, 1^F

→

GraffitiK

03/25 16:33, , 2^F

03/25 16:33, 2^F

推

s987692

03/25 16:56, , 3^F

03/25 16:56, 3^F