首页 > 代码库 > Linux内核之于红黑树and AVL树

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树。

Linux内核之于红黑树and AVL树