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

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/3c45caf08e9bca8360b4e7136ec22a64.html