红黑树

名称 : 红黑树

优点 :

相较AVL树来说, 平衡条件宽松, 减少了很多因插入删除节点导致的调整. 适合于插入删除频繁的情况.

AVL树适合于插入删除较少, 搜索较多的情况.

平衡条件 :

1. 每个节点非黑即红
2. 根节点是黑色
3. 叶节点(NIL)是黑色 NIL : 虚拟空节点
4. 如果一个节点是红色, 则它的两个子节点都是黑色的
5. 从根节点触发到所有叶节点路径上, 黑色节点数量相同 (最长是最短路径的2倍 : 长边红黑相间, 短边黑色)

认识 :

平衡条件 4 和 5 限制了红黑树最长边和最短边的2倍长度关系. 本质上, 红黑树也是通过控制树高来保证平衡. 红黑树相比AVL树控制条件更弱, 因此插入删除调整的频次也会低. AVL树更适用于插入删除较少但是访问较多的情况.