教育行業(yè)A股IPO第一股（股票代碼 003032）

全國(guó)咨詢(xún)/投訴熱線：400-618-4000

樹(shù)化的意義是什么？【java面試題】

更新時(shí)間:2022年02月15日18時(shí)14分 來(lái)源:傳智教育 瀏覽次數(shù):

樹(shù)化的意義：

紅黑樹(shù)用來(lái)避免 DoS 攻擊，防止鏈表超長(zhǎng)時(shí)性能下降，樹(shù)化應(yīng)當(dāng)是偶然情況，是保底策略。

hash 表的查找，更新的時(shí)間復(fù)雜度是 $O(1)$，而紅黑樹(shù)的查找，更新的時(shí)間復(fù)雜度是 $O(log_2?n )$，TreeNode 占用空間也比普通 Node 的大，如非必要，盡量還是使用鏈表。

hash 值如果足夠隨機(jī)，則在 hash 表內(nèi)按泊松分布，在負(fù)載因子 0.75 的情況下，長(zhǎng)度超過(guò) 8 的鏈表出現(xiàn)概率是 0.00000006，樹(shù)化閾值選擇 8 就是為了讓樹(shù)化幾率足夠小。

樹(shù)化規(guī)則：

當(dāng)鏈表長(zhǎng)度超過(guò)樹(shù)化閾值 8 時(shí)，先嘗試擴(kuò)容來(lái)減少鏈表長(zhǎng)度，如果數(shù)組容量已經(jīng) >=64，才會(huì)進(jìn)行樹(shù)化。

退化規(guī)則：

情況1：在擴(kuò)容時(shí)如果拆分樹(shù)時(shí)，樹(shù)元素個(gè)數(shù) <= 6 則會(huì)退化鏈表。

情況2：remove 樹(shù)節(jié)點(diǎn)時(shí)，若 root、root.left、root.right、root.left.left 有一個(gè)為 null ，也會(huì)退化為鏈表。




猜你喜歡：

什么是冒泡排序？手寫(xiě)一段冒泡排序的代碼

Javascript猜數(shù)游戲怎么實(shí)現(xiàn)？【含游戲源碼】

lock和synchronized有什么區(qū)別？

Java線程優(yōu)先級(jí)：Thread類(lèi)的優(yōu)先級(jí)常量

傳智教育JAVA開(kāi)發(fā)工程師培訓(xùn)

0 分享到：
和我們?cè)诰€交談！