红黑树/AVL

红黑树与AVL树对比分析

1. 性质分析

ALV树性质

• 一棵带有平衡功能的二叉搜索树【高度平衡二叉树】
• 带有平衡条件：每个结点的左右子树高度之差的绝对值（平衡因子）最多为1
• AVL查找、插入、删除平均和最坏的时间复杂度为O(logN),如果在插入与删除节点后，存在破坏AVL平衡条件【平衡因子大于1的】的情况，可能需要通过一次或多次树旋转来重新平衡此树。

红黑树性质

红黑树是每个结点带有颜色属性的二叉搜索树，颜色为红色或黑色。

• 节点为红色或黑色
• 根节点为黑色
• 叶子节点（空节点）为黑色
• 每个红色节点的两个自节点为黑色【从根节点到叶子节点的路径中，不能存在两个连续的红色节点】
• 每条路径都包含相同数目的黑节点

2. 应用分析

ALV树应用

• AVL在Windows NT内核中广泛存在。

红黑树应用

• C++ STL中的set，map中；
• Java集合中的TreeSet和TreeMap中；
• Nginx中用红黑树管理定时器【红黑树是有序的，可以很快的得到距离当前最小的定时器】;
• IO多路复用的epoll采用红黑树组织管理sockfd，以支持快速的增删改查;
• Linux虚拟内存的管理。

2. AVL与红黑树综合对比分析

AVL是高度平衡二叉树，红黑树是“弱平衡二叉树”

• 在相同节点情况下, AVL树高度 <= 红黑树高度；因此AVL的查找效率高于红黑树；
• 红黑树是部分要求到达平衡条件，降低了对旋转的要求，从而在插入、删除需要维持平衡的情况下，性能优于AVL树； 而且红黑树的涉及，任何的不平衡都可以在三次旋转之内解决;
  【插入节点导致树失衡， AVL树与红黑树都是最多两次树旋转事先复衡，旋转的量级是O(1); 删除节点导致失衡, AVL树需要维护从被删节点到根节点路径上所有的节点平衡，旋转的量级为O(logN)，红黑树嘴说只需要3次事先复衡，旋转的量级是O(1)。】
• 因此实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL树，如果搜索，插入删除次数几乎差不多，应该选择红黑树。

3. 总结AVL与红黑树对比分析

AVL树与红黑树对比分析图