[理工] [DS]-資料結構演算法幾個小問題

[assassin88 (AI)]

一、寫題目碰到"Loading density"是指？
    洪逸跟解答定義不同，解答是寫n/t(這是洪逸定義的identifier density)，
    洪逸定義為n/b*s，他應該是照恐龍翻的，所以是解答寫錯嗎？
    註：n為identifier使用個數，t為hash table所有的identifier個數，
        b為bucket個數，s為bucket中slot個數。
        可是這樣照字面意思，又好像解答是對的= ="

二、Merging two AVL trees of n-node each can be done in O(n) time in the worst
    case？
    不知道答案為何，不過感覺是false，覺得是O(nlogn)..不知道對嗎？

三、關於hashing的題目，如果沒註明n次overflow(指：超過他給定的f(x)都還是溢位)，
    接著該怎麼安插位置？是直接作linear probing嗎？

問題有點多..請多指教~~~

--
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 編輯: assassin88      來自: 140.135.167.46       (12/29 15:08)
推 FRAXIS:第二題 先把兩個tree轉成ordered array
→ FRAXIS:然後merge成一個新的ordered array
→ FRAXIS:再從新的ordered array 建立一個平衡的二元樹即可
→ assassin88:按照你的說法那應該是nlogn沒錯~感謝
→ FRAXIS:按照我的說法應該是 O(n)..
→ assassin88:先轉兩個tree不就是O(n)，再建立AVL~O(logn)？
推 FRAXIS:建立應該只要O(n)  遞迴去建..
→ assassin88:回家看了答案..是false耶XD