AVL与红黑树的区别

---

AVL

1.简介

AVL树是最先发明的自平衡二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，每个节点的左右子树高度差不超过1，和红黑树相比，AVL树是严格的平衡二叉树，平衡条件必须满足(所有结点的左右子树高度差不超过1)。如图所示：

2.局限性

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树，而因为旋转非常耗时，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。
注意：查找、插入和删除在平均和最坏情况下都是O(log n)。

3.应用

Windows NT内核中广泛存在。

红黑树

1.简介

一种二叉查找树，但在每个节点增加一个存储位表示结点的颜色，可以是红或黑(非红即黑)。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因此红黑树是一中弱平衡二叉树(由于是弱平衡，可以看到，在相同的节点情况下，AVL树的高度低于红黑树)，相对于要求严格的AVL树来说，它的旋转次数少，插入最多两次旋转，删除最多三次旋转，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树。

2.性质

• 每个节点或者是红色的，或者是黑色的。
• 根节点是黑色的。
• 每个叶子节点（NIL）是黑色的。
• 如果一个节点是红色的，则它的两个儿子都是黑色的。
• 对每个节点，从该节点到子孙节点的所有路径上包含相同数目的黑节点。
  注意：包含n结点的红黑树简单操作的运行时间为O(log n)。

3.应用

map和set底层都是用红黑树实现的。

---

第一次记录自己的学习笔记，如果您发现问题，欢迎指点。