红黑树(Red-Black Tree)
1.来由
二叉搜索树在一般情况下,均可以以O(log n)的效率高效的维护查找,插入,删除这三个操作;
但是当数据本来就有序的极端情况下就会使得构建的二叉搜索树变成链表的状态,使得效率退化成O(n);
而平衡二叉树(AVL树)通过旋转的操作时刻使二叉搜索树保持平衡的状态以位置最佳的效率,从而避免二叉搜索树出现向上的极端情况;
而红黑树和AVL树一样都是一种二叉搜索树,是对二叉搜索树的平衡的另一种思想。
2.定义
2.1左根右
前提是其为二叉搜索树,也即左子树<根结点<右子树。
2.2根叶黑
根和叶子结点都是黑色。
2.3不红红
红色结点的左右孩子必须是黑色,也即从上到下不能出现两个连续的红色结点。
2.4黑路同
任意结点到叶所有路径中的黑色结点数量必须相同。
3.性质
最长路径绝对不会超过最短路径的两倍。
因为不能连续出现两个红色结点,所以必然在一条路径上是间隔出现黑红两种结点的,这样最长路径断然不可能超过最短路径的两倍。
可以看到AVL树对平衡控制的更加严格,这就导致了红黑树的查找速率略低于AVL树;
而正是因为这个原因,也导致AVL树在构建,插入,删除时需要进行旋转调整的次数更多。
也即:
AVL树 | 红黑树 |
查询高效 | 插入和删除高效 |
4.插入
4.1默认插入的结点为红色
插入结点的颜色为红色的影响更小,且只会违反“根叶黑”和“不红红”的性质。
4.2三种失衡情况
4.2.1插入的结点是根节点
直接变黑即可:
4.2.2插入的结点的叔叔是红色
叔父变色,爷爷变插入结点:
这个时候就继续判定和调整:
4.2.3插入的结点的叔叔是黑色
判断是需要(LL,RR,LR,RL)旋转,然后变色:
LL
旋转点和中心点变色:
RR
旋转点和中心点变色:
LR
旋转点和中心点变色:
RL
然后对旋转点和旋转中心点变色:
5.构建
……