首頁技術(shù)文章正文

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

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

樹化的意義：

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

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

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

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

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

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

猜你喜歡：

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