国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業(yè)教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 為什么STL和linux都使用紅黑樹作為平衡樹的實?

為什么STL和linux都使用紅黑樹作為平衡樹的實?

來源:千鋒教育
發(fā)布人:xqq
時間: 2023-10-11 02:49:15 1696963755

一、為什么STL和linux都使用紅黑樹作為平衡樹的實現

選擇紅黑樹作為底層實現紅黑樹是一種類平衡樹, 但它不是高度的平衡樹, 但平衡的效果已經很好了。STL map , nginx,linux 虛擬內存管理,他們都有紅黑樹的應用。

1. 如果插入一個node引起了樹的不平衡,AVL和RB-Tree都是非常多只需要2次旋轉操作,即兩者都是O(1);但是在刪除node引起樹的不平衡時,最壞情況下,AVL需要維護從被刪node到root這條路徑上所有node的平衡性,因此需要旋轉的量級O(logN),而RB-Tree非常多只需3次旋轉,只需要O(1)的復雜度。

2. 其次,AVL的結構相較RB-Tree來說更為平衡,在插入和刪除node更容易引起Tree的unbalance,因此在大量數據需要插入或者刪除時,AVL需要rebalance的頻率會更高。因此,RB-Tree在需要大量插入和刪除node的場景下,效率更高。自然,由于AVL高度平衡,因此AVL的search效率更高。

3. map的實現只是折衷了兩者在search、insert以及delete下的效率。總體來說,RB-tree的統(tǒng)計性能是高于AVL的。

延伸閱讀

二、AVL樹(平衡二叉樹)

AVL樹是帶有平衡條件的二叉查找樹,一般是用平衡因子差值判斷是否平衡并通過旋轉來實現平衡,左右子樹的高度差不超過1,和紅黑樹相比,AVL樹是嚴格的平衡二叉樹,平衡條件必須滿足(所有節(jié)點的左右子樹高度差的絕對值不超過1。不管我們是執(zhí)行插入還是刪除操作,只要不滿足上面的條件,就要通過旋轉來保持平衡,而旋轉是非常耗時的,由此我們可以知道AVL樹適合用于插入與刪除次數比較少,但查找多的情況。:

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業(yè)內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT