为什么需要红黑树？
由于AVL树是以增加、删除节点来保证树的基本平衡，从而保证查询效率在O(logN)左右。
红黑树就是在不牺牲太大的增加、删除操作的代价，而且也能保证稳定高效的查找效率。
红黑树的特性
红黑树
- 每个节点要么是红色，要么是黑色
- 根节点是黑色
- 每个叶子节点（null）是黑色
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 没有一条路径会比其他路径长两倍(虽然不是AVL中高度差不能超过为2的严格平衡)
红黑树查找性能
- 查找性能：基本维持在O(logN)，但是最差的情况是最短路径的两倍减一，所以要比AVL树差一点。
- 插入性能：需要至多两次旋转和变色，也为O(logN)
- 删除性能：删除性能要比AVL树好很多，至多进行三次旋转操作。而不用像AVL树检查每一层的平衡因子可能涉及到多次旋转，所以删除性能要比AVL树好很多。
网友评论