想問以下資結數題
https://i.imgur.com/nzxdF6e.jpg
21 22，想問關於splay tree 的splay operation跟delete operation的時間複雜度
演算法的課本提到splay tree operation的amortized cost是O(lgn) 但網路上的筆記寫調整最差的過程是O(n) , 然後21題問的是worst case想確認這兩題答案
23，紅黑樹,如果一條path經過三個紅點,那這顆樹至少會有多少個黑點？該怎麼畫呢？
25 26 binomial heap
25從一個unordered array建heap的時間複雜度？我的想法是Insert O(lgn) 做n次insert建立O(nlgn)?
26 原本想法是2019/32的商 但畫出來好像不太對
27 30 fibonacci heap
27 課本寫n個node的fibonacci heap 任一點的degree會小於等於 n取log以golden ratio為底 所以最大degree是D?
30 沒有想法
31 32 disjoint-set
想問這題要寫AA還是BB比較好 課本寫的worst case時間複雜度是O(m a(n)) , a(n)在可以想到的情況是小於等於4的
謝謝