为什么红色黑树比AVL树更适合Linux中的内存管理？

Question

用于链接存储器映射的可执行文件的各个部分的vm_area_struct结构存储为红黑树.现在,据我所知和这里的帖子提到太红黑树和AVL树之间的区别 AVL树比RB树执行更快的查找.

此树由进程引用的虚拟地址编制索引,并在进程开始执行时创建.我希望这棵树可以用于查找,有时也可以用于插入和删除.如果是这种情况,那么为什么AVL树不优于RB树作为相同的实现.

此外,如果我的理解不正确并且树涉及大量插入和删除,与查找相比,请提供参考以支持此声明.

我已经看到一些关于tldp的文章提到早期的AVL树也被用于相同的文章.请解释这种变化带来的原因是什么？

Answer 1

这在内核源代码存储库的文档目录中得到解决。

文档/rbtree.txt

红黑树与 AVL 树类似，但为插入和删除提供更快的实时有界最坏情况性能（最多分别旋转两次和三次，以平衡树），速度稍慢（但仍然是 O(log n) ）查找时间。