张铭红黑树 2007年12月25日2时19分 插入4 插入4 ◆情况2红红冲突 ◆情况2红红冲突 父和叔父也是红 父和叔父也是红 ◆父祖换色 ◆父祖换色 ◆情况1红红冲突 ◆情况1红红冲突Q 叔父是黑 叔父是黑 ◆重构 ◆重构 2007年12月2日2时19分 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张铭心红黑树 插入算法和复杂度分析 删除算法 inserter(毳a ◆红晨树高度为O(ogn) 先调用BST的删除算法 B摘入,銅入新结点.0)●第1步时闸代价为gn) 特删除的结点有一个以上的外部空指汁,则宣接删除 ◆第2步时间代价为O(1) ◆v是被剽除的内结点,w是被删外结点X是v的兄弟 2把z标记为红色 ●第3步时间代价为Oogn 否则I标记为双根据其兄弟鳍点c进行工构调整 最多O1次工构着色 删除8 dst●红票结点插入时间代价 为O(ogn) 2007年12月25日】时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张心红黑树 根据双黑X的兄弟C进行调整 情况1(a)重构:侄子红结点八字 假设X是左子结点〔若X为右孩子,则对称) ◆将兄弟结点C提上去 ●情况1:c是黑色,且子结点有红色 ◆c继承原父结点的颜色 盒构,完成操作 ◆然后把B着为黑色,D着为黑色,其他颜色不变即可 ◆情况2:C是色,且有两个黑子结点 换色 父结点B原为红色,可能需要从B继续向上调整 ●情况3:c是红色 c转为父结点,调整为情况1或2继续处理 00?年12月25日2时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张铭红黑树张铭 红黑树 2007年12月25日2时19分 4 2007年12月25日2时19分 北京大学 张铭© 红黑树 19 插入4 情况2红红冲突 „ 父和叔父也是红 父祖换色 情况1红红冲突 „ 叔父是黑 重构 11 2 14 1 7 15 5 8 4 X 5 7 2007年12月25日2时19分 北京大学 张铭© 红黑树 20 插入4 情况2红红冲突 „ 父和叔父也是红 父祖换色 情况1红红冲突 „ 叔父是黑 重构 7 2 11 1 5 8 4 5 14 15 2007年12月25日2时19分 北京大学 张铭© 红黑树 21 插入算法和复杂度分析 红黑树高度为 O(log n) 第1步时间代价为 O(log n) „ 因为访问 O(log n) 个结点 第2步时间代价为O(1) 第3步时间代价为 O(log n) „ 最多 O(log n) 重着色 Š 每次 O(1) „ 最多 O(1) 次 重构着色 红黑树结点插入时间代价 为 O(log n) insertItem(k, o) 1. BST插入，插入新结点 z(k, o) 2. 把 z 标记为红色 3. while doubleRed(z) if isBlack(sibling(parent(z))) z ← restructure(z) return else { sibling(parent(z) is red } z ← recolor(z) 2007年12月25日2时19分 北京大学 张铭© 红黑树 22 删除算法 先调用BST的删除算法 „ 待删除的结点有一个以上的外部空指针，则直接删除 „ 否则在右子树中找到其后继结点进行值交换（着色不变）删除 v 是被删除的内结点, w 是被删外结点, X 是 w的兄弟 „ 如果 v 或者 X 是红色, 则把 X 标记为黑色即可 „ 否则, X 需要标记为双黑, 根据其兄弟结点 C 进行重构调整 6 3 8 4 v X w 6 3 4 删除 X 8 2007年12月25日2时19分 北京大学 张铭© 红黑树 23 根据双黑 X 的兄弟 C 进行调整 假设X是左子结点（若X为右孩子，则对称） 情况1： C 是黑色，且子结点有红色 „ 重构，完成操作 情况2：C 是黑色, 且有两个黑子结点 „ 换色 „ 父结点B原为红色，可能需要从B继续向上调整 情况3： C 是红色 „ 转换状态 „ C转为父结点，调整为情况1或2继续处理 2007年12月25日2时19分 北京大学 张铭© 红黑树 24 情况1(a)重构：侄子红结点八字 将兄弟结点C提上去 C继承原父结点的颜色 然后把B着为黑色，D着为黑色，其他颜色不变即可 B D X C α D X B C α