作者niceperson (一条香蕉)
看板Grad-ProbAsk
标题[理工] 105台大电机丙资结
时间Fri Dec 11 23:39:08 2020
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1607701151.A.A23.html
※ 编辑: niceperson (27.52.222.14 台湾), 12/11/2020 23:51:16
1F：推 jimmylin1024: Pop三次 stack 剩下a 接着再依序insert即可 12/12 06:40
2F：→ jimmylin1024: Stack就会是 acbd 不过这个方法是假设暂存器超过3个 12/12 06:40
3F：→ jimmylin1024: 以上 如果限定只有一个暂存器 那我觉得答案就会是E 12/12 06:40
4F：→ jimmylin1024: 了 12/12 06:40
5F：→ jimmylin1024: RB TREE的树高会被bound在 lgn 到2 lgn 之间 12/12 06:40
6F：→ jimmylin1024: AVL TREE则被bound 在1.44 lgn 左右 12/12 06:40
7F：→ jimmylin1024: 所以RB TREE树高不一定会比较小 12/12 06:40
8F：→ jimmylin1024: 这题问的是树高 应该不用考虑insert速度 12/12 06:40
9F：推 alex391a: 他是说一样的插入序列 结果的树的长度 题目要看仔细XD 12/12 11:19
10F：→ niceperson: 看懂了 谢谢楼上两位 昨天在写可能头昏没想清楚问的是 12/12 15:47
11F：→ niceperson: 什麽 12/12 15:47