张铭红黑树 2007年12月25日2时19分 删除80 删除80(调整) ◆当前结点X变为65的右黑叶结点 ◆c是黑色,且左黑、右红:情况1(b)重构 ◆C是红色:情况3状态转换 2007年12月2日2时19分 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张铭心红黑树 删除80 删除操作时间代价 ◆完成调整 ◆其平均和最差检索o(log2m) 自底向根的方向调整 ◆红黑树构造 (数据,左指针,右指针,颜色,父指 ◆自顶向下的递归插入/删除调整方法 (数据,左指针,右指针,颜色 ■非递归,记录回溯路径 2007年12月25日】时 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张心红黑树 其他BST索引 红黑树是一种很好的索引结构 ◆AvL树 ◆AVL树要求完全平衡 平衡的BsT 左右子树高度整≤1 ◆伸展树与操作频率相关 ●伸展树 ◆RB-Tree局部平衡 随检宗面训數位量 ■统计性能好于AvL树 人△ ■且增删记录算法性能好、易实现 C++ST的set、 multiset、map multimap都应用了红黑树的变体 00?年12月25日2时 京大学张铭红更树 2007年12月25日2时19分 北京大学张铭红黑树 6张铭 红黑树 2007年12月25日2时19分 6 2007年12月25日2时19分 北京大学 张铭© 红黑树 31 删除80 当前结点X变为65的右黑叶结点 C 是红色：情况3状态转换 65 50 10 60 62 80 X B B C X C α β α β C X B 2007年12月25日2时19分 北京大学 张铭© 红黑树 32 删除80（调整） C 是黑色，且左黑、右红：情况1(b)重构 50 10 60 62 65 X C E D B B X E C D α β B C D X α E β 2007年12月25日2时19分 北京大学 张铭© 红黑树 33 删除80 完成调整 50 10 62 D 60 65 C B X 2007年12月25日2时19分 北京大学 张铭© 红黑树 34 删除操作时间代价 其平均和最差检索O(log2 n) „ 自底向根的方向调整 红黑树构造 （数据，左指针，右指针，颜色，父指 针） 自顶向下的递归插入/删除调整方法 „ （数据，左指针，右指针，颜色） „ 非递归，记录回溯路径 2007年12月25日2时19分 北京大学 张铭© 红黑树 35 其他BST索引 AVL树 „ 平衡的BST „ 左右子树高度差≤1 伸展树 „ 随检索而调整位置 A B C D x y z B C A D x y z 9 1 1 8 3 12 10 15 11 -1 0 0 0 -1 2007年12月25日2时19分 北京大学 张铭© 红黑树 36 红黑树是一种很好的索引结构 AVL树要求完全平衡 伸展树与操作频率相关 RB-Tree局部平衡 „ 统计性能好于AVL树 „ 且增删记录算法性能好、易实现 C++ STL的set、multiset、map、 multimap都应用了红黑树的变体