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

[niceperson (一條香蕉)]

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
推 jimmylin1024: Pop三次 stack 剩下a 接著再依序insert即可
→ jimmylin1024: Stack就會是 acbd 不過這個方法是假設暫存器超過3個
→ jimmylin1024: 以上 如果限定只有一個暫存器 那我覺得答案就會是E
→ jimmylin1024: 了
→ jimmylin1024: RB TREE的樹高會被bound在 lgn 到2 lgn 之間
→ jimmylin1024: AVL TREE則被bound 在1.44 lgn 左右
→ jimmylin1024: 所以RB TREE樹高不一定會比較小
→ jimmylin1024: 這題問的是樹高 應該不用考慮insert速度
推 alex391a: 他是說一樣的插入序列 結果的樹的長度 題目要看仔細XD
→ niceperson: 看懂了 謝謝樓上兩位 昨天在寫可能頭昏沒想清楚問的是
→ niceperson: 什麼