Linux核心之于紅黑樹and AVL樹

為什麼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樹。

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1668766