[理工] 105台大電機丙資結

看板Grad-ProbAsk作者 (一條香蕉)時間5年前 (2020/12/11 23:39), 5年前編輯推噓2(2推 0噓 9→)
留言11則, 3人參與, 5年前最新討論串1/1
https://i.imgur.com/6E7I7NM.jpg
想請問這題的解法 我爬文看之前有兩位大大說是C 但我不知道這個要怎麼去做出dbca的順序 麻煩各位大大解惑 還有是非第一題 題目說rb tree is always shorter than or equal to avl tree with the same insertion sequence 這題爬文大家也寫是false 但我google看別人的討論是 搜尋時avl tree會比rb tree快（因為樹高） 但插入時 rb tree會比 avl tree快 （因為調整頻率） 這樣這題應該是true才對吧！？ ----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.222.14 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1607701151.A.A23.html ※ 編輯: niceperson (27.52.222.14 臺灣), 12/11/2020 23:51:16
推
12/12 06:40, 5年前 , 1F
Pop三次 stack 剩下a 接著再依序insert即可
12/12 06:40, 1F
→
12/12 06:40, 5年前 , 2F
Stack就會是 acbd 不過這個方法是假設暫存器超過3個
12/12 06:40, 2F
→
12/12 06:40, 5年前 , 3F
以上 如果限定只有一個暫存器 那我覺得答案就會是E
12/12 06:40, 3F
→
12/12 06:40, 5年前 , 4F
了
12/12 06:40, 4F
→
12/12 06:40, 5年前 , 5F
RB TREE的樹高會被bound在 lgn 到2 lgn 之間
12/12 06:40, 5F
→
12/12 06:40, 5年前 , 6F
AVL TREE則被bound 在1.44 lgn 左右
12/12 06:40, 6F
→
12/12 06:40, 5年前 , 7F
所以RB TREE樹高不一定會比較小
12/12 06:40, 7F
→
12/12 06:40, 5年前 , 8F
這題問的是樹高 應該不用考慮insert速度
12/12 06:40, 8F
推
12/12 11:19, 5年前 , 9F
他是說一樣的插入序列 結果的樹的長度 題目要看仔細XD
12/12 11:19, 9F
→
12/12 15:47, 5年前 , 10F
看懂了 謝謝樓上兩位 昨天在寫可能頭昏沒想清楚問的是
12/12 15:47, 10F
→
12/12 15:47, 5年前 , 11F
什麼
12/12 15:47, 11F
‣ 更多 niceperson 的文章
文章代碼(AID): #1VqvAVeZ (Grad-ProbAsk)