Why Red Black trees preferred over AVL trees for memory management in Linux?

Question

The vm_area_struct structure used to link various sections of a memory mapped executable file is stored as a red black tree. Now, as far as I know and the post here mentions too Difference between red-black trees and AVL trees AVL trees performs faster lookup than RB trees.

This tree is indexed by virtual addresses referred to by the process and is created when the process begins its execution. I expect this tree to be used vastly for lookup and at times for insertion and deletion. If, this is the case then why is AVL tree not preferred over RB tree as an implementation for the same.

Also, if my understanding is incorrect and that the tree involves a lot of insertions and deletions, as well, in comparison to lookup, please provide reference to support this claim.

I have seen some articles on tldp mentioning that earlier AVL tree was used for the same. Please explain on what grounds has this change been brought around?

Answer 1

This is addressed in the documentation directory in the kernel source repository.

Documentation/rbtree.txt

Red-black trees are similar to AVL trees, but provide faster realtime bounded worst case performance for insertion and deletion (at most two rotations and three rotations, respectively, to balance the tree), with slightly slower (but still O(log n)) lookup time.