红黑树插入时
- 父节点是两叉节点(一个关键字):插入成三叉节点
- 父节点是三叉节点(两个关键字):插入成四叉节点
- 父节点是四叉节点(三个关键字):拆分成一个两叉节点,一个三叉节点,并向上递归插入
红黑树删除时
- 删除是三叉节点或四叉节点,直接删除
- 删除节点是黑色节点,兄弟节点是黑色节点且是B树的三叉节点或者四叉节点:从兄弟节点借一个节点
- 删除节点是黑色节点,兄弟节点是黑色节点且是B树的二叉节点,父节点是黑色节点:将兄弟节点归到父节点(即将兄弟节点染红)
- 删除节点是黑色节点,兄弟节点是黑色节点且是B树的二叉节点,父节点是红色节点:将父节点从祖父节点分离(即将父节点染黑),将兄弟节点归到父节点(即将兄弟节点染红)
- 删除节点是黑色节点,兄弟节点是红色节点(父节点必为黑色,侄子节点也必为黑色):将父节点从右倾(或左倾)改为左倾(或右倾),新的兄弟节点必为黑色,然后重复上述处理