整体来说左倾红黑树的插入就是这3种情况来回切换,最终达到平衡。
3.4 左倾红黑树删除删除思路是不删除目标数据,而是找到目标数据的前驱节点或后继节点,然后把数据拷贝一份到目标数据进行覆盖。然后转而去删除前驱或后继。删除后再去修补平衡。
从宏观上来看从根节点开始查找,全程利用2-3树思维逐层对红黑树调整,每次保证当前节点树2-3树中非2节点,如果是非2节点则看下一层,如果是2节点则根据兄弟节点调整。
- 兄弟节点是2节点,从父节点借个数据跟当前节点及兄弟节点形成临时4节点。
- 兄弟节点是非2节点,兄弟节点上升一个数据,父节点下降一个数据。
删除后就涉及到数据平衡修复了,还是根据2-3树来修复平衡,路上可能会碰到红色右倾节点,遇到就进行一次左旋即可。
3.5 工业级红黑树增加说下实际工程中红黑树的增删操作,增加主要有3种情况:
情况1:关注节点是 a,它的叔叔节点 d 是红色:
- 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色。
- 将关注节点 a 的祖父节点 c 的颜色设置成红色。
- 关注节点变成 a 的祖父节点 c,实现关注节点的迁移。
- 跳到情况2或情况3。