推 magic83v: 7.8我選AA 有t(node) 找中間相當於二分搜尋的速度01/29 17:35
→ magic83v: 旋轉可能會影響到整棵樹s.t 花O(n)調整應該合理01/29 17:36
→ magic83v: 想問1. 至少修改4個link 是哪4個01/29 17:40
→ magic83v: 17c也看不太懂意思 qq01/29 17:58
7我是想說他沒有說balance 所以worst case斜斜一條找中位數要O(n)
8是說整棵樹的s跟t都可能要改嗎，那可能是O(n)沒錯..
第1我記錯了 是插入才要改4個
17c是考union find吧 一個component當成一個集合
※ 編輯: ko330 (223.136.50.221), 01/29/2019 18:51:47
→ magic83v: 哦對 7A忘記skew的情況01/29 19:08
推 anonimo: 第7題 他說can be found 所以我覺得應該選最小O(logn)01/29 20:21
→ anonimo: 第8題應該不用整顆樹改 只要改做ratation的部分就好01/29 20:23
→ anonimo: *rotation01/29 20:24
第7我是覺得他想考的不是這個耶0.0
第8 rotation可能不只動三個點耶，下面subtree也全部會動到，你寫看看106的11題也是
這樣
※ 編輯: ko330 (114.137.158.87), 01/29/2019 21:55:19
→ anonimo: 不太懂你的意思 只要把rotation node間的data換過去不就 01/29 23:19
→ anonimo: 好了嗎 106那題不也是動abc 3點之間嗎？ 01/29 23:19
→ anonimo: 這題其實就是是CLRS第14章 可以去看看課本 01/29 23:20
感謝 剛剛去翻了一下課本有寫到紀錄size可以用來查是第幾個小的，插入一樣O(logn)
題目的s(node)原本以為旋過去之後要調底下每一點的height
但好像根本不用記錄在node上 我傻了，搜尋過程中每經過一點就+1就好
※ 編輯: ko330 (114.137.158.87), 01/30/2019 00:39:04
推 silenteve: 請問第19題怎麼算呢 01/30 15:18
推 ekids1234: 16應該沒有E 因為splay 可skew 供之後人參考 02/16 21:52