為什麼Linux早先使用AVL樹而後來傾向於紅黑樹？
實際上這是由紅黑樹的實用主義特質導致的結果，本短文依然是形而上的觀點。紅黑樹可以直接由2-3樹導出，我們可以不再提紅黑樹，而只提2-3樹，因為2-3樹的操作太簡單。另外，任何紅黑樹的操作和特性都可以映射到2-3樹中。因此紅黑樹和AVL樹的比較就成了2-3樹和AVL樹的比較。
它們倆的區別在哪？2-3樹的平衡是完美平衡的，但是樹杈數量卻可以是3個，而AVL樹差一點點就完美平衡的標准二叉樹，它只允許子樹的高度差最多為1。可見這麼看來，2-3樹比AVL樹更加平衡，但是2-3樹轉換為二叉樹，即紅黑樹的時候，它就不再能保持完美平衡了，因為三叉節點要分割出來一個紅色節點，使得子樹高度加1，這麼看來，紅黑樹在嚴格意義上完全沒有AVL樹平衡！
AVL樹在每一次插入刪除時都要保持它那“差一點點的平衡”，而紅黑樹則只需要不擾動黑色節點即可，以2-3樹來講，它畢竟是犧牲了二叉樹的標准特性變成三叉樹保持平衡的。可見，紅黑樹的插入/刪除開銷遠小於AVL樹，對於查詢開銷，理論上，更加平衡的AVL樹要比紅黑樹好(因為對於2-3樹，遇到三叉節點，你需要比較2次)，但是，紅黑樹的2倍樹高的不平衡狀態是一個小概率事件！因此對於正常情況，你可以認為AVL樹和紅黑樹的查詢開銷是一樣的，總之，常規情況下，紅黑樹要好於AVL樹。
AVL樹太理想了，而Linux內核中的數據結構，特別是虛擬內存管理模塊，尤其是CFS調度器的task對列，它們是會被頻繁插入刪除的，因此選擇了紅黑樹而不是AVL樹。
