张铭红黑树 2007年12月25日2时19分 插入算法 插入算法调整1:重构 ◆先调用BST的插入算法 ◆情况1:新增结点X的叔父结点是黑色 把新记录着色为红色 若父结点是展色,则算法结束 以祖结点为轴 旋转父结点 A ◆否则,双红调整 插入4 ◆每个结点的阶都保持原值,调整完成 2007年12月2日2时19分 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张铭心红黑树 4种形式的结构调整 插入算法调整2:换色 ◆原则:保持BST的中序性质 ◆情况2:新增结点X的叔父结点也是红色 只A 红红检查 Q⊙父祖换色 ◆需要继续检查平衡 2007年12月25日】时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张心红黑树 插入4 插入4 ◆情况2红红冲突 ◆情况2红红冲突 父和叔父也是红 父和叔父也是红 ◆父祖换色 ◆父祖换色 00?年12月25日2时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张铭红黑树张铭 红黑树 2007年12月25日2时19分 3 2007年12月25日2时19分 北京大学 张铭© 红黑树 13 插入算法 先调用BST的插入算法 „ 把新记录着色为红色 „ 若父结点是黑色，则算法结束 否则，双红调整 6 3 8 6 3 8 4 X A A X 插入4 2007年12月25日2时19分 北京大学 张铭© 红黑树 14 插入算法调整1：重构 情况1：新增结点X的叔父结点是黑色 每个结点的阶都保持原值，调整完成 X α 以祖结点为轴 旋转父结点 A X B B A C C α 2007年12月25日2时19分 北京大学 张铭© 红黑树 15 4种形式的结构调整 原则：保持BST的中序性质 2 4 6 6 2 4 6 4 2 2 6 4 2 6 4 2007年12月25日2时19分 北京大学 张铭© 红黑树 16 插入算法调整2：换色 情况2：新增结点X的叔父结点也是红色 需要继续检查平衡 X A 父祖换色 X B B C A C 对B继续 红红检查 α α 2007年12月25日2时19分 北京大学 张铭© 红黑树 17 插入4 情况2红红冲突 „ 父和叔父也是红 父祖换色 11 2 14 1 7 15 5 8 X 4 2007年12月25日2时19分 北京大学 张铭© 红黑树 18 插入4 情况2红红冲突 „ 父和叔父也是红 父祖换色 11 2 14 1 7 15 5 8 X 4 5 7 8