Linux内核之于红黑树and AVL树

rgfwwq

为什么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树。