红黑树¶
约 495 个字 预计阅读时间 2 分钟
基本原则¶
- 前提：二叉搜索树(左根右)
- 根和叶子(NULL)都是黑色(根叶黑)
- 叶子节点若为红色，那它的孩子一定是黑色(不红红)
- 任意节点到叶子的所有路径上黑色节点数量相同(黑路同)
- 红黑树最长路径不超过最短路径的两倍
插入¶
- 规定插入节点默认为红色
插入的是根节点¶
- 直接变黑就可以了
插入节点的叔叔是红色¶
- 对父亲，叔叔，爷爷三个节点变色，然后让爷爷变插入节点
- 继续判定属于哪种情况，继续调整
插入节点的叔叔是黑色¶
- (LL,RR,LR,RL)旋转，然后对最后一次的旋转点和被绕着转的点变色
删除¶
删除节点只有左/右孩子¶
- 代替后直接变黑
删除节点没有孩子¶
删除节点为红节点¶
- 无需任何调整
删除节点为黑节点¶
- 首先变成双黑节点，然后根据兄弟的情况进行变色、旋转，消除双黑节点
兄弟是黑色¶
兄弟至少有一个红孩子(记孩子为r,兄弟为s,父亲为p)¶
- LL型，r变s(颜色)，s变p，p变黑，然后进行旋转
- RR型，r变s(颜色)，s变p，p变黑，然后进行旋转
- LR型，r变p,p变黑，然后左旋再右旋
- RL型，r变p,p变黑，然后右旋再左旋
- 最后把双黑节点变回单黑
兄弟的孩子都是黑色¶
- 兄弟变红，双黑上移(如果父节点为黑色，父节点变为双黑;如果父节点为红色，双黑遇红直接变单黑)，然后再套用前面的情况继续调整.
如果双黑遇到根节点，直接变单黑就可以了
兄弟是红色¶
- 兄父变色,朝双黑旋转，然后根据兄弟的情况继续调整