一、為什么STL和linux都使用紅黑樹作為平衡樹的實(shí)現(xiàn)

選擇紅黑樹作為底層實(shí)現(xiàn)紅黑樹是一種類平衡樹, 但它不是高度的平衡樹, 但平衡的效果已經(jīng)很好了。STL map , nginx，linux 虛擬內(nèi)存管理，他們都有紅黑樹的應(yīng)用。

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

2. 其次，AVL的結(jié)構(gòu)相較RB-Tree來說更為平衡，在插入和刪除node更容易引起Tree的unbalance，因此在大量數(shù)據(jù)需要插入或者刪除時(shí)，AVL需要rebalance的頻率會(huì)更高。因此，RB-Tree在需要大量插入和刪除node的場(chǎng)景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。

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

延伸閱讀

二、AVL樹（平衡二叉樹）

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