公告
| 一级分类 | 二级分类 | 三级分类 | 处理策略 | |
|---|---|---|---|---|
| case 1 |
x是根节点 |
(1) 根节点设为黑色 | ||
| case 2 |
x的父节点是黑色 |
|||
| case 3 |
x的父节点是红色 |
x的父节点是左孩子，叔节点是红色 |
(1) x的父节点和叔节点设为黑色 (2) x祖父节点设为红色 (3) x的祖父节点作为新节点（即x节点），循环对x节点执行上述操作 |
|
| case 4 | x的父节点是右孩子，叔节点是红色 | |||
| case 5 | x的父节点是左孩子，叔节点是黑色 | x是左孩子 |
(1) x的父节点设为黑色、叔父节点设为红色 (2) 以x的祖父节点进行右旋 |
|
| case 6 | x是右孩子 |
(1) x的父节点作为新的节点（即x节点） (2) 以x节点进行左旋 (3) 再按照x是左孩子情况继续处理 |
||
| case 7 | x的父节点是右孩子，叔节点是黑色 | x是左孩子 |
(1) x的父节点作为新的节点（即x节点） (2) 以x节点进行右旋 (3) 再按照x是右孩子情况继续处理 |
|
| case 8 | x是右孩子 |
(1)x的父节点设为黑色、叔父节点设为红色 (2)以x的祖父节点进行左旋 |
