[問題] 用red-black tree解hash的collision
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間13年前 (2011/12/29 22:45)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/1
Assume that we have a hash table with collisions resolved by chaining.
Attempting to improve the performance of this implementation, we use a
red-black tree for each slot instead of an unsorted linked list,
resulting in a hash table with collisions resolved "by red-black trees".
Assume that a simple uniform hashing function is utilized and the load factor
of the hash table is α. What is the running time for unsuccessful searches
and insertions for our new implementation, respectively?
這是100台大資工所的題目
我自己的想法是都是O(lgn) 可是感覺沒那麼簡單..是不是要用到α?
請問有人對這題有什麼想法嗎?
謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.110.186
※ 編輯: mqazz1 來自: 140.118.110.186 (12/29 22:47)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
