# AVL VS 红黑树

“AVL trees are actually easier to implement than RB trees because there are fewer cases. And AVL trees require $O(1)$ rotations on an insertion, whereas red-black trees require$O(lg n)$.

In practice, the speed of AVL trees versus red-black trees will depend on the data that you're inserting. If your data is well distributed, so that an unbalanced binary tree would generally be acceptable (i.e. roughly in random order), but you want to handle bad cases anyway, then red-black trees will be faster because they do less unnecessary rebalancing of already acceptable data.On the other hand, if a pathological(病态的) insertion order (e.g. increasing order of key) is common, then AVL trees will be faster, because the stricter balancing rule will reduce the tree's height.

Splay trees might be even faster than either RB or AVL trees,depending on your data access distribution. And if you can use a hash instead of a tree, then that'll be fastest of all. ”

AVL树的最大高度是1.44 * log(N+2) - 1.328，红黑树的最大高度是2.00* log(N+1)。与红黑树相比，AVL树的插入删除操作更慢一些，但是查询操作更快

32位Windows系统中，进程在用户态可用的地址空间范围是低2G（x64下是低8192G）。随着进程不断的申请和释放内存，这个2G的地址空间，有的地址范围是保留状态(reserved)，有的地址范围是提交状态（映射到了物理页面，committed），有的地址范围是空闲的。Windows采用平衡二叉树把这些离散的地址范围管理起来。（想必对进程地址空间的查询操作更频繁一些，所以AVL得以入选。）

Linux内核进程调度使用红黑树进行管理。

1）http://www.linuxidc.com/Linux/2014-04/99736.htm