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

全國咨詢/投訴熱線：400-618-4000

樹化的意義是什么？【java面試題】

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

樹化的意義：

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

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

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

樹化規(guī)則：

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

退化規(guī)則：

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

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




猜你喜歡：

什么是冒泡排序？手寫一段冒泡排序的代碼

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

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

Java線程優(yōu)先級：Thread類的優(yōu)先級常量

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

0 分享到：
和我們在線交談！